kruskal演算法java

『壹』 KRUSKAL演算法，提點改進的意見

很謙虛的學習精神哈，我覺得已經很好了（可能是我初學的緣故？），如果你說的更好使要求時間的話，可以把冒泡排序改成別的排序，比如O(nlgn)的

『貳』 kruskal演算法 如何判環

kruskal需要用並查集。
每次從邊集中找權值最小的，如果兩頂點不在同一集合，就加上邊權，並合並兩個點。

『叄』 kruskal演算法是什麼

克魯斯卡爾演算法。

克魯斯卡爾演算法是求連通網的最小生成樹的另一種方法。與普里姆演算法不同，它的時間復雜度為O（eloge）（e為網中的邊數），所以，適合於求邊稀疏的網的最小生成樹。

克魯斯卡爾演算法基本思想：

克魯斯卡爾（Kruskal）演算法從另一途徑求網的最小生成樹。其基本思想是：假設連通網G=（V，E），令最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖T=（V，{}），概述圖中每個頂點自成一個連通分量。

在E中選擇代價最小的邊，若該邊依附的頂點分別在T中不同的連通分量上，則將此邊加入到T中；否則，捨去此邊而選擇下一條代價最小的邊。依此類推，直至T中所有頂點構成一個連通分量為止。

『肆』 kruskal演算法

給每個子樹一個不同的編號，對每一個頂點引入一個標記t，表示這個頂點所在的子樹編號。當加入一條紅色邊，就會使該邊兩端點所在的兩個子樹連接起來，成為一個子樹，從而兩個子樹中的頂點標記要改變成一樣。綜上，可將Kruskal演算法細化使其更容易計算機實現。

kruskal應該是遞歸演算法吧，在定義圖中各端點時，可以多設一個標記，把圖遞歸遍歷一遍，在同一連同子圖上的點，標記為一樣的整型數值即可。

參考：http://ke..com/view/580403.htm

『伍』 求kruskal演算法的C語言程序 越簡單越好a

對於c語言，指針是靈魂，特別是在稍微高級點的程序中，指針是必不可少的。以下程序沒有用到鏈表，結構體用到了。當然如果你一定要用二維數組代替結構體去存儲也行，代碼會變得相當麻煩而且可讀性差，維護困難。
另外注釋加上了。代碼臨時寫成，自帶個人風格呵呵。

#include <stdio.h>
#include <stdlib.h>
#define TURE 1
#define FALSE 0
#define MAX 1000
#define abs(a) a > 0 ? a : -a
//圖相關----------------------
typedef struct Tnode
{
int loc;
struct Tnode *next;
} Tnode; //頂點存放結點
typedef struct Ttable
{
Tnode *head;
Tnode *rear;
int length;
} Ttable; //頂點鏈表結構
typedef int ArcCell; /*對於無權圖，用1或0表示是否相鄰；對帶權圖，則為權值類型*/
typedef int booleanType; //狀態變數
typedef struct
{
ArcCell **arcs; /*鄰接矩陣*/
int vexnum; /*圖的頂點數和弧數*/
} MGraph; /*（Adjacency Matrix Graph）*/
//----------------------------
//隊列相關（鏈式）-------------
typedef struct QNode //隊列結點
{
int data;
struct QNode *next;
} QNode;

typedef struct //隊列
{
QNode *front, *rear;
} LinkQueue;
//-----------------------------

MGraph G; //圖
ArcCell **steparcs; //輔助矩陣
Ttable TE; //頂點鏈表指針
booleanType *visited; //建立標志數組(全局量）
LinkQueue Q; //定義隊列

int GetGraph(MGraph *G); //建立圖結構
void Back(); //還原矩陣
int kruskalTravel(MGraph G); //克魯斯卡爾演算法建立最小生成樹
int MinSearch(MGraph G, int *i, int *j); //查找權值最小的邊，以i，j返回其兩端頂點。
int FirstAdjVex(int v);
int NextAdjVex(int v, int w);
int InitQueue(LinkQueue *Q); //初始化隊列
int EmptyQueue(LinkQueue Q); //判空
int EnQueue(LinkQueue *Q, int v); //入隊
int OutQueue(LinkQueue *Q); //出隊
int WFSTravel(MGraph *G, LinkQueue *Q, int x, int y); //廣度遍歷含有i的連通分量，如果含有j頂點，返回TRUE，否則返回FALSE
int main()
{
GetGraph(&G);
printf("Kruskal:\n");
kruskalTravel(G);
return 0;
}

int GetGraph(MGraph *G) //建立鄰接矩陣
{
int i, j;
scanf("%d", &(G->vexnum));
G->arcs = (ArcCell**)malloc(sizeof(ArcCell*) * G->vexnum);
for(i = 0; i < G->vexnum; i++)
{
G->arcs[i] = (ArcCell*)malloc(sizeof(ArcCell) * G->vexnum);
} //建立二維動態數組

for(i = 0; i < G->vexnum; i++)
{
for(j = 0; j < G->vexnum; j++)
{
scanf("%d", G->arcs[i] + j);
}
} //輸入數據
return 0;
}//GetGraph

int kruskalTravel(MGraph G) //克魯斯卡爾演算法建立最小生成樹
{
int i, j;
int N = G.vexnum;

steparcs = (ArcCell**)malloc(sizeof(ArcCell*) * G.vexnum); //建立二維動態數組
for(i = 0; i < G.vexnum; i++)
{
steparcs[i] = (ArcCell*)malloc(sizeof(ArcCell) * G.vexnum);
} //建立二維動態數組
for(i = 0; i < G.vexnum; i++) //初始化輔助矩陣
{
for(j = 0; j < G.vexnum; j++)
{
steparcs[i][j] = 0;
printf("%d ", steparcs[i][j]);
}
printf("\n");
}
printf("\n");

while(N > 1) //只要剩餘的連通分量大於一，就繼續鏈接各個連通分量
{
//查找權值最小的邊，以i，j返回其兩端頂點。如果兩個頂點屬於同一連通分量，則查找權次最小邊，標志矩陣為負
MinSearch(G, &i, &j);
if(!WFSTravel(&G, &Q, i, j)) //廣度遍歷含有i的連通分量，如果含有j頂點，返回TRUE，否則返回FALSE
{
steparcs[i][j] = steparcs[j][i] = G.arcs[i][j]; //將符合條件的邊和頂點並入到連通分量中
G.arcs[i][j] *= -1; //標志鄰接矩陣，表明此條邊已經查詢過
G.arcs[j][i] *= -1;
N--; //剩餘的連通分量
for(i = 0; i < G.vexnum; i++) //輸出本次步驟
{
for(j = 0; j < G.vexnum; j++)
{
printf("%d ", steparcs[i][j]);
}
printf("\n");
}
printf("\n");
} //if
} //while

return 0;
}

int MinSearch(MGraph G, int *i, int *j) //查找權值最小的邊，返回其值，並以i，j返回其兩端頂點。
{
int temp = MAX; //存放當前最小值
int m, n;
for(n = 0; n < G.vexnum; n++) //循環查找
{
for(m = 0; m < G.vexnum; m++)
{
if(G.arcs[n][m] > 0 && G.arcs[n][m] < temp) //找最小值
{
temp = G.arcs[n][m];
*i = n;
*j = m;
}
}
}
return temp;
}

int FirstAdjVex(int v)
{
int i;

for(i = 0; i < G.vexnum; i++)
if(steparcs[v][i] != 0)
return i;
return -1;
}

// 返回下一個鄰接頂點的序號。若頂點在G中沒有鄰接頂點,則返回-1
int NextAdjVex(int v, int w)
{
int i;
for(i = w + 1; i < G.vexnum; i++)
if(steparcs[v][i] != 0)
return i;
return -1;
}

int InitQueue(LinkQueue *Q) //初始化隊列
{
Q->front = Q->rear = (QNode*)malloc(sizeof(QNode)); //頭結點
return 0;
}

int EmptyQueue(LinkQueue Q) //判空
{
return Q.front == Q.rear ? 1 : 0;
}

int EnQueue(LinkQueue *Q, int v) //入隊
{
Q->rear->next = (QNode*)malloc(sizeof(QNode));
Q->rear = Q->rear->next;
Q->rear->data = v;
return 0;
}

int OutQueue(LinkQueue *Q) //出隊
{
int e;
QNode *p;
if(Q->front == Q->rear)
{
printf("Queue Empty\n");
exit(0);
}
p = Q->front;
Q->front = Q->front->next;
e = Q->front->data;
free(p);
return e; //返回隊頭元素
}

//廣度遍歷含有i的連通分量，如果含有j頂點，返回TRUE，否則返回FALSE
int WFSTravel(MGraph *G, LinkQueue *Q, int x, int y)
{
int v, vtop = x, i;
visited = (booleanType*)malloc(sizeof(booleanType) * G->vexnum);
InitQueue(Q);
for(v = 0; v < G->vexnum; v++) //初始化標志數組
{
visited[v] = FALSE;
}

v = vtop; //初始查詢頂點
if(!visited[v]) //如果沒有遍歷過，從此處開始遍歷
{
visited[v] = TURE; //遍歷該結點並標志結點狀態
EnQueue(Q, v);
while(!EmptyQueue(*Q)) //如果隊列中有元素，繼續訪問其鄰接點
{
i = OutQueue(Q);
for(v = FirstAdjVex(i); v >= 0; v = NextAdjVex(i, v)) //尋找一個頂點的所有鄰接點
{
if(!visited[v]) //訪問未訪問過的頂點
{
visited[v] = TURE;
if(v == y)
{
G->arcs[x][y] *= -1; //標志鄰接矩陣，表明此條邊已經查詢過
G->arcs[y][x] *= -1;
return 1;
}
EnQueue(Q, v);
}
} //尋找一個頂點的所有鄰接點
} //如果隊列中有元素，繼續訪問其鄰接點
} //如果沒有遍歷過，從此處開始遍歷
return 0;
}//WFSprint

『陸』 kruskal演算法的代碼實現

MST-KRUSKAL(G，w)
function Kruskal(w,MAX)
%此程序為最小支撐樹的Kruskal演算法實現
%w為無向圖的距離矩陣，故為對稱矩陣
%MAX為距離矩陣中∞的實際輸入值
%時間：2011年6月22日0:07:53
len=length(w); %圖的點數
edge=zeros(len*(len-1）,3）; %用於存儲圖中的邊
count=1; %圖中的邊數
for i=1:len-1 %循環距離矩陣，記錄存儲邊
for j=i+1:len
if w(i,j)~=MAX
edge(count,1）=w(i,j);
edge(count,2）=i;
edge(count,3）=j;
count=count+1;
end
end
end
edge=edge（1:count-1,:); %去掉無用邊
[tmp,index]=sort(edge(:,1）); %所有邊按升序排序
i=3; %其實測試邊數為3條（3條以下無法構成圈，即無需檢測）
while 1
x=findcycle(edge(index（1:i),:),len); %檢測這些邊是否構成圈
if x
index(i)=0; %若構成圈，則將該邊對應的index項標記為0，以便除去
else
i=i+1; %若沒有構成圈，則i加1，加入下一邊檢測
end
index=index(index>0); %將構成圈的邊從index中除去
if i==len
break; %找到符合條件的點數減一條的邊，即找到一個最小支撐樹
end
end
index=index（1:len-1）; %截短index矩陣，保留前len-1項
%%%%%%%%%%%% 結果顯示 %%%%%%%%%%%%%
s=sprintf(' %s %s %s ','邊端點','距離','是否在最小支撐樹');
for i=1:count-1
edge_tmp=edge(i,:);
if ~isempty(find(index==i,1）)
s_tmp=sprintf(' (%d,%d) %d %s ',edge_tmp（2）,edge_tmp（3）,edge_tmp（1）,'√');
else
s_tmp=sprintf(' (%d,%d) %d %s ',edge_tmp（2）,edge_tmp（3）,edge_tmp（1）,'×');
end
s=strcat(s,s_tmp);
end
disp(s);
end
function isfind=findcycle(w,N)
%本程序用於判斷所給的邊能否構成圈：有圈，返回1；否則返回0
%w：輸入的邊的矩陣
%N：原圖的點數
%原理：不斷除去出現次數小於2的端點所在的邊，最後觀察是否有邊留下
len=length(w(:,1）);
index=1:len;
while 1
num=length(index); %邊數
p=zeros（1,N); %用於存儲各點的出現的次數（一條邊對應兩個端點）
for i=1:num %統計各點的出現次數
p(w(index(i),2）)=p(w(index(i),2）)+1;
p(w(index(i),3）)=p(w(index(i),3）)+1;
end
index_tmp=zeros（1,num); %記錄除去出現次數小於2的端點所在的邊的邊的下標集合
discard=find(p<2）; %找到出現次數小於2的端點
count=0; %記錄剩餘的邊數
for i=1:num
%判斷各邊是否有僅出現一次端點——沒有，則記錄其序號於index_tmp
if ~(~isempty(find(discard==w(index(i),2）,1）) || ~isempty(find(discard==w(index(i),3）,1）))
count=count+1;
index_tmp(count)=index(i);
end
end
if num==count %當沒有邊被被除去時，循環停止
index=index_tmp（1:count); %更新index
break;
else
index=index_tmp（1:count); %更新index
end
end
if isempty(index) %若最後剩下的邊數為0，則無圈
isfind=0;
else
isfind=1;
end
end
%
% a =[
% 0 3 2 3 100 100 100
% 3 0 2 100 100 100 6
% 2 2 0 3 100 1 100
% 3 100 3 0 5 100 100
% 100 100 100 5 0 4 6
% 100 100 1 100 4 0 5
% 100 6 100 6 100 5 0];
%
% Kruskal(a,100） {
最小生成樹的Kruskal演算法。
Kruskal演算法基本思想：
每次選不屬於同一連通分量（保證不生成圈）且邊權值最小的頂點，將邊加入MST，並將所在的2個連通分量合並，直到只剩一個連通分量
排序使用Quicksort(O(eloge))
檢查是否在同一連通分量用Union-Find，每次Find和union運算近似常數
Union-Find使用rank啟發式合並和路徑壓縮
總復雜度O(eloge)=O(elogv) （因為e<n(n-1）/2）
} constmaxn=100;maxe=maxn*maxn;typeedge=recorda,b:integer;//邊的2個頂點len:integer;//邊的長度end;varedges:array[0..maxe]ofedge;//保存所有邊的信息p,r:array[0..maxn]ofinteger;//p保存i的父親節點，r用來實現Union-Find的rank啟發式n,e:integer;//n為頂點數，e為邊數procereswap(a,b:integer);//交換beginedges[0]:=edges[a];edges[a]:=edges[b];edges[b]:=edges[0];end;procerequicksort(l,r:integer);//快速排序varx,i,j:integer;beginx:=edges[random(r-l+1)+l].len;i:=l;j:=r;repeatwhileedges[i].len<xdoinc(i);whileedges[j].len>xdodec(j);ifi<=jthenbeginswap(i,j);inc(i);dec(j);enntili>j;ifl<jthenquicksort(l,j);ifi<rthenquicksort(i,r);end;procereinit;vari:integer;beginassign(input,'g.ini');reset(input);readln(n,e);fori:=1toedoreadln(edges[i].a,edges[i].b,edges[i].len);//從文件讀入圖的信息fori:=1tondop[i]:=i;//初始化並查集randomize;quicksort(1,e);//使用快速排序將邊按權值從小到大排列end;functionfind(x:integer):integer;//並查集的Find，用來判斷2個頂點是否屬於一個連通分量beginifx<>p[x]thenp[x]:=find(p[x]);find:=p[x]end;procereunion(a,b:integer);//如果不屬於且權值最小則將2個頂點合並到一個連通分量vart:integer;begina:=find(a);b:=find(b);ifr[a]>r[b]thenbegint:=a;a:=b;b:=tend;ifr[a]=r[b]theninc(r[a]);p[a]:=b;end;procerekruskal;//主過程varen:integer;//en為當前邊的編號count:integer;//統計進行了幾次合並。n-1次合並後就得到最小生成樹tot:integer;//統計最小生成樹的邊權總和begincount:=0;en:=0;tot:=0;whilecount<n-1dobegininc(en);withedges[en]dobeginiffind(a)<>find(b)thenbeginunion(a,b);writeln(a,'--',b,':',len);inc(tot,len);inc(count);end;end;end;writeln('TotalLength=',tot)end;{===========main==========}begininit;kruskal;end.Kruskal演算法適用於邊稀疏的情形，而Prim演算法適用於邊稠密的情形 importjava.util.ArrayList;importjava.util.Collections;classBianimplementsComparable//兩點之間的加權邊{privateintfirst,second;//表示一條邊的兩個節點privateintvalue;//權值publicBian(intfirst,intsecond,intvalue){this.first=first;this.second=second;this.value=value;}publicintgetFirst(){returnfirst;}publicintgetSecond(){returnsecond;}publicintgetValue(){returnvalue;}@OverridepublicintcompareTo(Objectarg0){returnvalue>((Bian)arg0).value1:(value==((Bian)arg0).value0:-1）;}@OverridepublicStringtoString(){returnBian[first=+first+,second=+second+,value=+value+];}}classShuZu{staticArrayList<ArrayList>list=newArrayList<ArrayList>();//存放每一個數組中的節點的數組staticArrayList<ArrayList>bianList=newArrayList<ArrayList>();//對應存放數組中的邊的數組publicstaticvoidcheck(Bianb)//檢查在哪個數組中{if(list.size()==0){ArrayList<Integer>sub=newArrayList<Integer>();sub.add(b.getFirst());sub.add(b.getSecond());list.add(sub);ArrayList<Bian>bian=newArrayList<Bian>();bian.add(b);bianList.add(bian);return;}intfirst=b.getFirst();intshuyu1=-1;intsecond=b.getSecond();intshuyu2=-1;for(inti=0;i<list.size();i++)//檢查兩個節點分別屬於哪個數組{for(intm=0;m<list.get(i).size();m++){if(first==(Integer)list.get(i).get(m))shuyu1=i;if(second==(Integer)list.get(i).get(m))shuyu2=i;}}if(shuyu1==-1&&shuyu2==-1）//表示這兩個節點都沒有需要新加入{ArrayList<Integer>sub=newArrayList<Integer>();sub.add(b.getFirst());sub.add(b.getSecond());list.add(sub);ArrayList<Bian>bian=newArrayList<Bian>();bian.add(b);bianList.add(bian);}if(shuyu1==-1&&shuyu2!=-1）//表示有一個點已經在數組中只把另一個加入就可以了{list.get(shuyu2).add(first);bianList.get(shuyu2）.add(b);}if(shuyu2==-1&&shuyu1!=-1）//表示有一個點已經在數組中只把另一個加入就可以了{list.get(shuyu1).add(second);bianList.get(shuyu1).add(b);}if(shuyu1==shuyu2&&shuyu1!=-1）//表述兩個在同一個組中會形成環{}if(shuyu1!=shuyu2&&shuyu1!=-1&&shuyu2!=-1）//表示兩個點在不同的組中需要合並{for(inti=0;i<list.get(shuyu2）.size();i++){list.get(shuyu1）.add(list.get(shuyu2）.get(i));}list.remove(shuyu2）;for(inti=0;i<bianList.get(shuyu2）.size();i++){bianList.get(shuyu1）.add(bianList.get(shuyu2）.get(i));}bianList.get(shuyu1）.add(b);bianList.remove(shuyu2）;}}publicstaticvoidshow(){for(inti=0;i<bianList.get(0).size();i++)System.out.println(bianList.get(0).get(i));}}publicclassTest{publicstaticvoidmain(String[]args){ArrayList<Bian>l=newArrayList<Bian>();l.add(newBian（1,3,1）);l.add(newBian（1,2,6）);l.add(newBian（1,4,5）);l.add(newBian（2,3,5）);l.add(newBian（2,5,3）);l.add(newBian（3,4,5）);l.add(newBian（3,5,6）);l.add(newBian（3,6,4）);l.add(newBian（4,6,2）);l.add(newBian（5,6,6）);Collections.sort(l);//for(inti=0;i<l.size();i++)//System.out.println(l.get(i));for(inti=0;i<l.size();i++)ShuZu.check(l.get(i));ShuZu.show();}}

『柒』 kruskal演算法java實現，哪位大神能幫忙調通這段代碼！

演算法如何，就不懂了。但，代碼已經正常編譯、運行 了

importjava.util.*;
importjava.io.*;

publicclassKruskalTest{
privatestaticfinalintm=3501981;//邊數
privatestaticfinalintn=2647;//頂點數
privatestaticint[]parent=newint[n];//parent數組,長度為頂點數
privatestaticArrayList<Edge>list;//序列
privatestaticfloatsum=0;//最小生成樹邊權總和
publicstaticvoidmain(String[]args)throwsFileNotFoundException{
newKruskalTest().test();
}
publicvoidtest()throwsFileNotFoundException{
Filefile=newFile(".\Euclideandistance.xlsx");
//讀取文件
Scannersc=newScanner(file);
doublenumber;
list=newArrayList<Edge>();
for(inti=1;i<=n;i++)
for(intj=i;j<=n;j++){
Edgeedge=newEdge();
edge.u=i;
edge.v=j;
if(sc.hasNext()){
number=sc.nextDouble();
edge.w=number;
}list.add(edge);
}
Collections.sort(list,newComparator<Edge>(){
@Override
publicintcompare(Edgeo1,Edgeo2){
return(int)(o1.w-o2.w);
}
});
//for(inti=0;i<list.size();i++){
//Edgeedge=list.get(i);
//System.out.println(edge.u+""+edge.v+""+edge.w);
//}
kruskal();
System.out.println("thelengthofMSTis"+sum);
}
staticvoipset(){
for(inti=0;i<n;i++)
parent[i]=-1;
}
intfind(intx){
ints;
for(s=x;parent[s]>=0;s=parent[s]);
while(s!=x){
inttmp=parent[x];
parent[x]=s;
x=tmp;
}returns;
}

voinion(intR1,intR2){
intr1=find(R1);
intr2=find(R2);
inttemp=parent[r1]+parent[r2];
if(parent[r1]>parent[r2]){
parent[r1]=r2;
parent[r2]=temp;
}else{
parent[r2]=r1;
parent[r1]=temp;
}
}
voidkruskal(){
intnum=0;
intu,v;
upset();
for(inti=0;i<m;i++){
Edgeedge=(Edge)list.get(i);
u=edge.u;
v=edge.v;
if(find(u)!=find(v)){
sum+=edge.w;
union(u,v);
num++;
}
if(num>=n-1)break;
}
}

classEdge{
intu,v;
doublew;
}
}

『捌』 用kruskal演算法實現最小生成樹寫出選邊的過程並編程實現，要寫程序

#include <stdio.h>
#include <stdlib.h>
#define N 10010
#define M 10010
typedef struct edge
{
int a,b,c;
}edge;
edge e[M];
int n,m;//n個結點，m條邊
int p[N];
void make_set()
{
for(int i=1;i<=n;i++) p[i]=i;
}
int find_set(int i)
{
if(i!=p[i]) p[i]=find_set(p[i]);
return p[i];
}
void union_set(int i,int j)
{
i=find_set(i);
j=find_set(j);
p[j]=i;
}
int cmp(const void*a,const void*b)
{
return (((edge*)a)->c)-(((edge*)b)->c);
}
int main()
{
//此處為文件讀寫操作
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int i,min;
while(~scanf("%d%d",&n,&m))
{
for(i=0;i<m;i++)
{
scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
}
qsort(e,m,sizeof(e[0]),cmp);
make_set();
min=0;
for(i=0;i<m;i++)
{
if(find_set(e[i].a)==find_set(e[i].b)) continue;
union_set(e[i].a,e[i].b);
min+=e[i].c;
}
printf("%d\n",min);
}
return 0;
}

『玖』 kruskal演算法的舉例描述

克魯斯卡爾演算法(Kruskal's algorithm)是兩個經典的最小生成樹演算法的較為簡單理解的一個。這裡面充分體現了貪心演算法的精髓。大致的流程可以用一個圖來表示。這里的圖的選擇借用了Wikipedia上的那個。非常清晰且直觀。
首先第一步，我們有一張圖，有若干點和邊
第一步我們要做的事情就是將所有的邊的長度排序，用排序的結果作為我們選擇邊的依據。這里再次體現了貪心演算法的思想。資源排序，對局部最優的資源進行選擇。
排序完成後，我們率先選擇了邊AD。這樣我們的圖就變成了
.
.
.
.
.
.
第二步，在剩下的邊中尋找。我們找到了CE。這里邊的權重也是5
.
.
.
.
.
.
依次類推我們找到了6,7,7。完成之後，圖變成了這個樣子。
.
.
.
.
.
.
下一步就是關鍵了。下面選擇那條邊呢？ BC或者EF嗎？都不是，盡管現在長度為8的邊是最小的未選擇的邊。但是他們已經連通了（對於BC可以通過CE,EB來連接，類似的EF可以通過EB,BA,AD,DF來接連）。所以我們不需要選擇他們。類似的BD也已經連通了（這里上圖的連通線用紅色表示了）。
最後就剩下EG和FG了。當然我們選擇了EG。最後成功的圖就是下圖：
.
.
.
.
.
.
到這里所有的邊點都已經連通了，一個最小生成樹構建完成。
Kruskal演算法的時間復雜度由排序演算法決定，若採用快排則時間復雜度為O(N log N)。

『拾』 kruskal演算法的java實現作為畢業設計是不是太簡單了 最後怕過不了

您好，提問者：
這要看你的思維跟練習程度了。多動腦，找找規律！