《图的最小生成树（c）》由会员分享，可在线阅读，更多相关《图的最小生成树（c）（6页珍藏版）》请在金锄头文库上搜索。
1、图的最小生成树(c) / /author: cqm / /date: 2004-9-23 / /description:Undigraph MST / / #include #include #include #define INFINITY INT_MAX /INT_MAX 表示最大整数，请参阅 C 的limits.h 文件 #define n 10 /图的顶点数，应由用户定义 typedef int AdjMatrixnn; /用二维数组作为邻接矩阵表示 /树边结点 typedef struct int fromvex,tovex; /边的起点和终点 int length; /边上的权 T
2、reeEdgeNode; typedef TreeEdgeNode MSTn-1; /最小生成树类型 AdjMatrix G; /连通网的带权邻接矩阵,作为 Prim 算法的输入 MST T; /存放 G 的最小生成树，作为 Prim 算法的输出 /打印错误信息 void Error(char *msg) printf(%cn,msg); / void CreateGraph(AdjMatrix G) int i,j; int start,end,weight; for(i=0;in;i+) /n 为图的顶点数 for(j=0;jn;j+) Gij = INFINITY; /INFINITY
3、代表无穷大 printf(输入弧和其权值，格式：弧尾，弧头，权值 n); for(i=0;in-1;i+) scanf(%d %d %d, getchar(); Gstartend=weight; Gendstart=weight; void DefaultCreateGraph(AdjMatrix G) int i,j; for(i=0;in;i+) /n 为图的顶点数 for(j=0;jn;j+) Gij = INFINITY; /0-9 G01=4; G10=4; G12=2; G21=2; G03=3; G30=3; G15=1; G51=1; G36=10; G63=10; G69=
4、5; G96=5; G97=2; G79=2; G78=6; G87=6; G34=8; G43=8; G45=1; G54=1; G25=2; G52=2; G47=4; G74=4; G58=4; G85=4; /构造初始的时候选轻边集 T0.n-2，树边集 TE!=Null,红点集 U=r void InitCandidateSet(AdjMatrix G,MST T,int r) int i,k=0; for(i=0;in;i+) /依次行成每个蓝点 i 初始的最短紫边存放在 Tk中 if(i!=r) /i 是蓝点(r,i) 是紫边 Tk.fromvex = r; /紫边的起点为红点
5、Tk.tovex = i; /紫边的终点为蓝点 Tk+.length= Gri; /紫边长度,注: 先取 k 然后再加一 /endif /在当前候选轻边集中选择一条轻边, 即选择长度最短的紫边 int SelectLightEdge(MST T,int k) /在当前候选轻边集 Tk.n-2中选择最短紫边,k=n-2 int min = INFINITY,i,minpos; for(i=k;in-1;i+) /遍历当前候选轻边集,找一轻边 if(Ti.length min) min = Ti.length; minpos = i; /记录当前最短紫边位置 /endif if(min=INFIN
6、ITY) /表示图不连通,不能求 MST Error(Graph is disconnected!); return minpos; /返回找到的轻边 Tminpos的位置 /end SelectLightEdge /调整候选边集 void ModifyCandidateSet(AdjMatrix G,MST T,int k,int v) int i,d; for(i=k;in-1;i+) /遍历当前候选轻边集 Tk.n-2 d = GvTi.tovex; /d 是新紫边(v,Ti.tovex)的长度 if(dTi.length)/新紫边长度小于蓝点 Ti.tovex 原来关联的最短紫边的长度
7、 Ti.length = d; Ti.fromvex= v; /新紫边取代原最短紫边 /endif /end for /ModifyCandidateSet /求图 G 的以 r 为根的 MST,r 为开始的结点 void PrimMST(AdjMatrix G,MST T,int r) int k,m,v; TreeEdgeNode e; InitCandidateSet(G,T,r); /设置初始的轻边候选集 T0.n-2 for(k=0;kn-1;k+) /依次求 MST 的第 k 条树边 m = SelectLightEdge(T,k); /在当前候选轻边集 Tk.n-2中选取轻边 T
8、m /轻边 Tm和紫边 Tk交换，即把轻边扩充到树中 e = Tm; Tm= Tk; Tk= e; v = Tk.tovex; /交换后红色树边集为 T0.k候选边集为 Tk+1.n-2 ModifyCandidateSet(G,T,k+1,v); /根据新红点 v 调整候选轻边集 Tk+1.n-2扩充 /endfor /PrimMST void PrintMST(MST T) int i; for(i=0;in-1;i+) printf(%d,%d)=%dn,Ti.fromvex,Ti.tovex,Ti.length); /测试主函数 void main() int u; char j=y;
9、 printf(本程序将演示构造图的最小代价生成树。 n); printf(首先输入图的顶点数和弧数.n 格式：顶点数，弧数；例如:4,4n); printf(接着输入各条弧(弧尾,弧头)和弧的权值。n); printf(格式:弧尾，弧头，权值；例如 n1,2,1n1,3,2n2,4,3n3,4,4n); printf(程序将会构造该图的最小代价生成树。n); printf(并显示该最小生成树。 n1,2n1,3n2,4n); while(j!=N&j!=n) printf(请输入图的顶点和弧数:); DefaultCreateGraph(G); /CreateGraph(G);/生成邻接矩阵结构的图 printf(从哪一顶点开始:); scanf(%d, /输入普里姆算法中的起始顶点 PrimMST(G,T,u); /普里姆算法求最小生成树 PrintMST(T); /打印最小生成树 printf(最小代价生成树构造完毕，继续进行吗?(Y/N); scanf(%c,
