克魯斯卡爾算法，是每次選出權(quán)值最小的邊構(gòu)成最小生成樹，選出邊時(shí)，要避免形成環(huán)。最終選出結(jié)點(diǎn)數(shù)減一條邊即可。（避免形成環(huán)的問題，采用標(biāo)號(hào)法（并查集），一開始，每個(gè)結(jié)各自為一個(gè)集合，分別給出各自不同大小的標(biāo)號(hào)，選出的邊的兩端結(jié)點(diǎn)的標(biāo)號(hào)將大的那個(gè)改成小的，以后選出的邊的端點(diǎn)標(biāo)號(hào)不能相同。）

#include<iostream> #define N 100 int sum=0;//權(quán)值和 using namespace std; //邊節(jié)點(diǎn) typedef struct vexnode {int adjvex;char v;struct vexnode *nextarc;float info; }ArNode; typedef struct Vnode{ //頂點(diǎn)信息 char data;ArNode *firstarc; //指向第一個(gè)邊結(jié)點(diǎn) }Vonde,Adjust[100]; typedef struct {Adjust survice;//鄰接表 int vexnum,acrnum;//圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù) }ALgraph;//鄰接表查找int locate1(ALgraph&R, char v,int n){//找出字符為v的下標(biāo) int j,i;for(i=1;i<=n;i++){if(R.survice[i].data==v){j=i;}}return j;} void creatUND(ALgraph &R){char v1,v2;//頂點(diǎn)的數(shù)據(jù)值 int i1,i2;//輸入的兩個(gè)頂點(diǎn)的位置和權(quán)值 float i3;//權(quán)值 printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)："); cin>>R.vexnum>>R.acrnum; //輸入頂點(diǎn)數(shù)和邊數(shù) printf("請(qǐng)輸入各個(gè)頂點(diǎn)的值：\n"); for(int i=1;i<=R.vexnum;i++){cin>>R.survice[i].data;//輸入各個(gè)頂點(diǎn)的信息 R.survice[i].firstarc=NULL;}printf("請(qǐng)輸入每條邊依附的兩個(gè)結(jié)點(diǎn)和權(quán)值：\n");for(int i=1;i<=R.acrnum;i++){cin>>v1>>v2>>i3;i1=locate1(R,v1,R.vexnum);i2=locate1(R,v2,R.vexnum);ArNode *p=new ArNode;p->info=i3; //記錄權(quán)值 p->v=v1;//記錄邊點(diǎn)的值 p->adjvex=i2;// 記錄頂點(diǎn)的值 p->nextarc=R.survice[i2].firstarc; //利用頭插法把第i1個(gè)的頂點(diǎn)插入到第i2個(gè)鄰接表中 R.survice[i2].firstarc=p;//建立的鄰接表表示的圖為有向圖，所以只記錄一邊，所以下面的部分代碼給注釋掉了 /* ArNode *p1=new ArNode;p1->adjvex=i1;//記錄頂點(diǎn)的位置 p1->info=i3;//記錄權(quán)值 p1->v=v2;//記錄邊點(diǎn)的值 p1->nextarc=R.survice[i1].firstarc;R.survice[i1].firstarc=p1;// 將新節(jié)點(diǎn)*p2插入頂點(diǎn)Vi1的鄰接表中 */} /* ArNode *p2; //這部分是將鄰接表表示的圖輸出 for(int i=1;i<=R.vexnum;i++){p2=R.survice[i].firstarc;while(p2){printf("<%c , %c> : %.1f ",R.survice[i].data,p2->v,p2->info);p2=p2->nextarc;}printf("\n"); }*/ } //協(xié)助結(jié)構(gòu)體，用來(lái)記錄邊的起始點(diǎn)，終點(diǎn)，權(quán)值信息 typedef struct end{char start;//邊的起點(diǎn) char end;//變得終點(diǎn) int w;//邊的權(quán)值 }Edge[100]; //將邊按照權(quán)值大小進(jìn)行排序 void sort(Edge &E,ALgraph &R){char b;int num;int m=R.acrnum;for(int i=0;i<m ;i++){for(int j=0;j<m-i;j++){if(E[j+1].w<E[j].w){b=E[j+1].start;E[j+1].start=E[j].start;E[j].start=b;b=E[j+1].end;E[j+1].end=E[j].end;E[j].end=b;num=E[j+1].w;E[j+1].w=E[j].w;E[j].w=num;}}}} //找出兩結(jié)點(diǎn)的標(biāo)號(hào)最大的那個(gè) int max(int i,int j){if(i>j){return i;}else return j; } //找出兩結(jié)點(diǎn)的標(biāo)號(hào)的小的那個(gè) int min (int i,int j){if(i<j){return i;}else return j; } void minspantree_Kruskal(ALgraph &G,Edge &E){int u=0; //數(shù)組Edge的下標(biāo) int parent[G.vexnum+1];//標(biāo)號(hào)用的數(shù)組 for(int i=1;i<=G.vexnum;i++){//將他們分成不同的集合 parent[i]=i;}ArNode *p1; //臨結(jié)點(diǎn)的指針 for(int i=1;i<=G.vexnum;i++){ //將每條邊的起點(diǎn)和終點(diǎn)，權(quán)值賦予結(jié)構(gòu)體中EDGE中 p1=G.survice[i].firstarc; while(p1){ E[u].start=G.survice[i].data;E[u].end=p1->v;E[u].w=p1->info;u++;p1=p1->nextarc;}}sort(E,G); //將每條邊按照權(quán)值的大小排序int n=0;//要挑選出邊的下標(biāo) for(int i=0;i<=G.vexnum-1;i++){//邊的結(jié)構(gòu)體下標(biāo)是從零開始的 char head1 =E[n].start;//記錄選出邊的起始點(diǎn) char end1 =E[n].end;//記錄選出邊的終點(diǎn) if(parent[locate1(G,head1,G.vexnum)]!=parent[locate1(G,end1,G.vexnum)]){// 如果結(jié)點(diǎn)的標(biāo)號(hào)不相等的話，將權(quán)值加上 sum+=E[n].w; int maxv=max(parent[locate1(G,head1,G.vexnum)],parent[locate1(G,end1,G.vexnum)]);//得到邊兩端結(jié)點(diǎn)標(biāo)號(hào)的最大值 int minv=min(parent[locate1(G,head1,G.vexnum)],parent[locate1(G,end1,G.vexnum)]);//得到邊兩端結(jié)點(diǎn)標(biāo)號(hào)的最小值 parent[locate1(G,head1,G.vexnum)]=minv; parent[locate1(G,end1,G.vexnum)]=minv;//他倆選出后成為一個(gè)集合，將標(biāo)號(hào)都改為最小值 for (int j=1;j<=G.vexnum;j++){//將結(jié)點(diǎn)中所有標(biāo)號(hào)都為邊兩端標(biāo)號(hào)最大值的結(jié)點(diǎn)標(biāo)號(hào)都改為最小值 if(parent[j]==maxv){parent[j]=minv;}}printf("<%c ,%c> \n",head1,end1); //輸出找出變的兩個(gè)結(jié)點(diǎn) }n++;} printf("最小權(quán)值之和為：%d",sum); } int main (){ALgraph R;Edge E;//有關(guān)邊的結(jié)構(gòu)體 creatUND(R);minspantree_Kruskal(R,E);return 0; }

總結(jié)

以上是生活随笔為你收集整理的克鲁斯卡尔算法建立最小生成树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。