算法概述:一個帶權(quán)的連通圖， 有V個點，E個邊，去掉所有的邊，得到一個新圖，將E個邊按權(quán)值從小到大排列，然后從權(quán)值最小的邊<u,v>開始加入,重復(fù)下去，但每次加入之前要判斷u，v是否連通，若連通則不加入，直到全部連通為止，結(jié)束循壞。

代碼：

struct Edge {int u;//邊起點int v;//邊終點int w;//權(quán)值 }E[N]; int V;//點數(shù) int E;//邊數(shù) bool cmp(const Edge *a ,const Edge *b) { return *(Edge *)a.w - *(Edge *)b.w ; //從小到大排序，把a，b位置反過來就是從大到小 } void kruskal() {int i,j,p,q,k;int _set[N];sort(E,E+N);for(i=0;i<E;i++){_set[i]=i;}k=1;j=0;while (k<E) { p=_set[E[j].u]; q=_set[E[j].v]; if (p!=q) {k++; for (i=0;i<E;i++) { if (_set[i]==q) { vset[i]=p; } } } j++; } }

?

總結(jié)

以上是生活随笔為你收集整理的算法学习之路|最小生成树—kruskal的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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