rtex set: ); for (i = 1; i <= MG.vexnum; i++) printf(%c , MG.vexs[i]); printf( Adjacency Matrix: ); for (i = 1; i <= MG.vexnum; i++) { j = 1; for (; j < MG.vexnum; j++) { printf(%d , MG.arcs[i][j]); } printf(%d , MG.arcs[i][j]); } } // 定义边结构体 typedef struct{ int start; int end; int cost; }Edge; /* * * 由邻接矩阵得到边的信息 * * */ void init_edge(MGraph MG,Edge edge[]){ int i,j; int count = 0; if(MG.type == 0){ for(i = 1; i <= MG.vexnum;i++){ for (j = 1;j <= MG.vexnum;j++){ if(MG.arcs[i][j] != 0 && MG.arcs[i][j] != UN_REACH){ edge[count].start = i; edge[count].end = j; edge[count].cost = MG.arcs[i][j]; count++; } } } } else{ for(i = 1; i <= MG.vexnum;i++){ for (j = i;j <= MG.vexnum;j++){ if(MG.arcs[i][j] != 0 && MG.arcs[i][j] != UN_REACH){ edge[count].start = i; edge[count].end = j; edge[count].cost = MG.arcs[i][j]; count++; } } } } } /* * * 将边按权值从大到小排序 * */ void sort_edge(Edge edge[],int arcnum){ int i,j; Edge temp; for(i = 0; i < arcnum - 1;i++){ for (j = i+1;j < arcnum;j++){ if(edge[i].cost > edge[j].cost){ temp = edge[i]; edge[i] = edge[j]; edge[j] = temp; } } } } /* * * 输出边的信息 * */ void print_edge(Edge edge[],int arcnum){ int i = 0; while(i < arcnum){ printf(%d,%d,%d ,edge[i].start,edge[i].end,edge[i].cost); i++; } } /** * 找出指定节点的所属的连通分量，这里是找出其根节点在father数组中下标。 **/ int findFather(int father[],int v){ int t = v; while(father[t] != -1) t = father[t]; return t; } /* * *Kruskal算法求最小生成树 * */ void Kruskal_MG(MGraph MG,Edge edge[]){ int father[MAX_VEX_NUM]; int i,count,vf1,vf2; // 初始化father数组 for(i = 0;i < MAX_VEX_NUM;i++){ father[i] = -1; } i = 0; count = 0; // 统计加入最小生树中的边数 // 遍历任意两个结点之间的边 while(i < MG.arcnum && count < MG.arcnum){ vf1 = findFather(father,edge[i].start); vf2 = findFather(father,edge[i].end); // 如果这两个节点不属于同一个连通分量，则加入同一个连通分量 if (vf1 != vf2){ father[vf2] = vf1; count++; printf(%c,%c,%d ,MG.vexs[edge[i].start],MG.vexs[edge[i].end],edge[i].cost); } i++; } } /** * 主函数 */ int main(void) { MGraph MG; Edge edge[MAX_ARC_NUM]; create_MG(&MG); print_MG(MG); init_edge(MG,edge); sort_edge(edge,MG.arcnum); printf(the result of Kruskal: ); Kruskal_MG(MG,edge); return EXIT_SUCCESS; }
?
运行演示：
?
jesson@jesson-K43SV:~/develop/worksapce/c_learning/最小生成树$ gcc -o Kruskal Kruskal.c
jesson@jesson-K43SV:~/develop/worksapce/c_learning/最小生成树$ ./Kruskal
Please input graph type DG(0) or UDG(1) :0
Please input vexmun : 4
Please input arcnum : 5
Please input 1th vex(char):a
Please input 2th vex(char):b
Please input 3th vex(char):c
Please input 4th vex(char):d
Please input 1th arc v1(char) v2(char) weight(int): a b 1
Please input 2th arc v1(char) v2(char) weight(int): a c 3
Please input 3th arc v1(char) v2(char) weight(int): a d 4
Please input 4th arc v1(char) v2(char) weight(int): b c 2
Please input 5th arc v1(char) v2(char) weight(int): c d 3
Graph type: Direct graph
Graph vertex number: 4
Graph arc number: 5
Vertex set:
a b c d
Adjacency Matrix:
0 1 3 4
1000 0 2 1000
1000 1000 0 3
1000 1000 1000 0
the result of Kruskal:
a,b,1
b,c,2
c,d,3
?
?
?
|