//主要源代碼如下：
#include <stdio.h> #include <stdlib.h> #include <string.h> #define INF 999999 #define MAX_NAME 3 #define VERTEX_MAX_NUM 100 typedef char VertexType[MAX_NAME]; typedef int VRType; typedef struct { //建立鄰接矩陣int weight; }adjMatrix[VERTEX_MAX_NUM][VERTEX_MAX_NUM]; struct MGraph{VertexType vex[VERTEX_MAX_NUM];//建立頂點向量adjMatrix arcs; //圖中的鄰接矩陣int vrtnum,arcnum;//頂點，弧的個數 }; typedef struct Sort{int x,y,w; }weightValue[VERTEX_MAX_NUM*VERTEX_MAX_NUM]; typedef struct VRTFather{int fa; }Father[VERTEX_MAX_NUM]; int LocateVex(MGraph G,VertexType u){int i;for( i=0;i<G.vrtnum;i++)if(strcmp(u,G.vex[i])==0)return i;return -1; } void creatMGraph(MGraph &G){int i,j,w;VertexType va,vb;printf("請輸入無向圖G的頂點數、邊數：");scanf("%d %d",&G.vrtnum,&G.arcnum);printf("請輸入%d個頂點的值：\n",G.vrtnum);for(i=0;i<G.vrtnum;i++) //構造頂點向量,(其實就是將頂點的名字換成數字)scanf("%s",G.vex[i]);for(i=0;i<G.vrtnum;i++) //初始化鄰接矩陣，都賦為無窮for(j=0;j<G.vrtnum;j++)G.arcs[i][j].weight=INF;printf("請輸入%d條邊的頂點1 頂點2 權值(以空格為間隔):\n",G.vrtnum);for(int k=0;k<G.arcnum;k++){scanf("%s%s%d%*c",va,vb,&w);i=LocateVex(G,va);j=LocateVex(G,vb);G.arcs[i][j].weight=G.arcs[j][i].weight=w;} } void DisplayArc(MGraph g){printf("建立的鄰接矩陣如下：\n ");for(int i=0;i<g.vrtnum;i++)printf("%7s",g.vex[i]);printf("\n");for(int i=0;i<g.vrtnum;i++){printf("%s",g.vex[i]);for(int j=0;j<g.vrtnum;j++){if(g.arcs[i][j].weight==INF)printf(" ∞");elseprintf("%7d",g.arcs[i][j].weight);}printf("\n");} } int findFather(int x,Father &father) {int root;//找x頂點的父親while(x!=father[x].fa)x=father[x].fa;root=x;//用temp存儲x的最深根節點。即x的父親結點return root; } void MiniSpanTree_KRUSKAL(MGraph G){int min=INF,i,j,vx,vy;weightValue value,temp;Father father;for(i=0;i<G.vrtnum;i++)//初始化所有頂點的父親為他自己father[i].fa=i;int k=0;//將所有的邊(包括邊兩端頂點信息)，賦值到value結構體數組中for(i=0;i<G.vrtnum;i++)for(j=0;j<G.vrtnum;j++,k++){value[k].w=G.arcs[i][j].weight;value[k].x=i;value[k].y=j;}//對value數組中所有的邊進行從大到小排序for(i=0; i<G.vrtnum*G.vrtnum-1; i++)for(j=0; j<G.vrtnum*G.vrtnum-1-i; j++){if(value[j].w>value[j+1].w){temp[0]=value[j+1];value[j+1]=value[j];value[j]=temp[0];}}printf("克魯斯卡爾算法的最小生成樹為：\n");int allcost=0;for(i=0;i<2*G.arcnum-1;i+=2){//從value數組中每隔兩個點進行取邊的值，因為無向圖中每個頂點的值有兩個int a,b;a=value[i].x;b=value[i].y;if(findFather(a,father)!=findFather(b,father)){//當前邊和其他邊不構成環，就輸出這條邊printf("(%s-%s) %d\n",G.vex[a],G.vex[b],G.arcs[a][b].weight);//將此邊的右頂點的父親賦值為左頂點的父親father[father[b].fa].fa=findFather(a,father);allcost+=G.arcs[a][b].weight;//每輸出一次，累加此邊的權值}}printf("最小二叉樹的最小權值為：%d\n",allcost); }int main(){MGraph g;creatMGraph(g);DisplayArc(g);MiniSpanTree_KRUSKAL(g);return 0; } /* 測試樣例： v0 v1 v2 v3 v4 v5 v6 v0 v1 28 v1 v2 16 v2 v3 12 v3 v4 22 v4 v5 25 v5 v0 10 v1 v6 14 v3 v6 18 v4 v6 24 */

總結

以上是生活随笔為你收集整理的邻接矩阵实现克鲁斯卡尔算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。