参考书籍:数据结构(C语言版)嚴蔚敏吴伟民编著清华大学出版社
本文中的代码可从这里下载:
对于带权的连通图(连通网)G其生成树也是带权的,将权值之和最小的生成樹称为最小生成树算法数据结构
假设 N =(V,{E})是一个连通网,U是顶点集 V 的一个非空子集若(u,v)是一条具有最小权值(代价)的边,其中 u ∈Uv∈V-U,则必存在一棵包含边(u,v)的最小生成树算法数据结构
(2)从 V 中任取一个顶点(假定为 V1),将此顶点并入 U中此时最小生成树算法数据結构顶点集 U={V1};
(3)从那些其中一个端点已在 U 中,另一端点仍在 U 外的所有边中找一条最短(即权值最小)的边,设该边为(Vi,Vj)其中 Vi∈U,Vj∈V-U并把該边和顶点 Vj分别并入 T 的边集 TE 和顶点集 U;
(4)如此进行下去,每次往生成树里并入一个顶点和一条边直到 n-1 次后,把所有 n 个顶点都并入生成树 T 的頂点集 U 中此时 U=V,TE中包含有(n-1)条边;这样T 就是最后得到的最小生成树算法数据结构。
算法时间复杂度O(n^2)与边无关,适合求解边稠密的網的最小生成树算法数据结构
DG(有向图)或者DN(有向网):邻接矩阵、邻接表(逆邻接表--为求入度)、十字链表 UDG(无向图)或者UDN(无向網):邻接矩阵、邻接表、邻接多重表 //1.数组表示法(邻接矩阵):将以有向网为例 typedef int VRType;//顶点关系类型,对于无权图或网用0或1表示相邻否;对於带权图或网,则为相应权值
//若图G中存在顶点v则返回v在图中的位置信息,否则返回其他信息
//采用邻接矩阵表示法构慥无向网G
VRType w;//对于无权图或网用0或1表示相邻否;对于带权图或网,则为相应权值
printf("\n每行输入一条弧依附的顶点(先弧尾后弧头)和权值(如:v1 v2 3):\n");
//又因为是无向网所以邻接矩阵相对于对角线对称,所以还得对另外半边三角阵赋值!!!!!!!!!!重要
//用prim算法从第u个顶点出发構造网G的最小生成树算法数据结构T输出T的各个边,O(n^2)
printf("请输入构造最小生成树算法数据结构的出发点:");