廢話(huà)少說(shuō)，下面是大家都熟悉的kruskal算法，重點(diǎn)在于實(shí)現(xiàn)，時(shí)間復(fù)雜度為O(e*loge)，其中e為邊數(shù)。
1 // 這個(gè)算法用kruskal實(shí)現(xiàn)了
2 #include <iostream>
3 #include <algorithm>
4
5 using namespace std;
6
7 const int maxn=100;
8
9 int m[maxn];
10 // 邊的結(jié)構(gòu)體
11 struct node{
12 int u,v;
13 double cost;
14 bool operator <(node a)
15 {
16 return cost>a.cost;
17 }
18 }e[maxn];
19
20
21
22 // 邊數(shù)
23 int ce;
24 // 點(diǎn)數(shù)
25 int n;
26 int heap[maxn];
27 // 堆大小
28 int hsize;
29
30 void merge(int i,int j)
31 {
32 // i所代表的集合中元素?cái)?shù)小于j所代表的
33 if(m[i]>m[j]){
34 m[j]+=m[i];
35 m[i]=j;
36 }else{
37 m[i]+=m[j];
38 m[j]=i;
39 }
40 }
41
42 int find(int i)
43 {
44 int j,k,t;
45 // 從i回溯到根
46 for(j=i;m[j]>0;j=m[j]);
47 // 路徑壓縮，將從i到j(luò)路徑上所有點(diǎn)的父親設(shè)為j
48 for(k=i;k!=j;k=t){
49 t=m[k];
50 m[k]=j;
51 }
52 return j;
53 }
54
55 void init()
56 {
57 memset(m,-1,sizeof(m));
58 return;
59 }
60
61 void siftdown(int index)
62 {
63 heap[index]=heap[hsize];
64 hsize--;
65 int i=index,j,tmp;
66 while(2*i<=hsize){
67 j=2*i;
68 if(j+1<=hsize && e[heap[j+1]].cost>e[heap[j]].cost) j++;
69 if(e[heap[i]].cost>e[heap[j]].cost) break;
70 tmp=heap[i];
71 heap[i]=heap[j];
72 heap[j]=tmp;
73 i=j;
74 }
75 }
76
77 int extract()
78 {
79 int res=heap[1];
80 siftdown(1);
81 return res;
82 }
83
84 void siftup(int index)
85 {
86 int i=index,tmp;
87 while(i>1 && e[heap[i/2]].cost<e[heap[i]].cost){
88 tmp=heap[i/2];
89 heap[i/2]=heap[i];
90 heap[i]=tmp;
91 i/=2;
92 }
93 }
94
95
96 // 用kruskal求最大生成樹(shù)
97 void kruskal()
98 {
99 // 初始化并查集
100 init();
101 int i;
102 // 初始化堆
103 //sort(e+1,e+ce+1);
104 for(i=1;i<=ce;i++){
105 heap[i]=i;
106 siftup(i);
107 }
108 hsize=ce;
109 // 算法開(kāi)始
110 double total=0.0;
111 int mergeTime=0; // 只需合并n-1次
112 int a,b;
113 while(hsize>0 && mergeTime<n-1){
114 i=extract();
115 a=find(e[i].u);
116 b=find(e[i].v);
117 // 若a，b處在不同的集合中
118 if(a!=b){
119 merge(a,b);
120 total+=e[i].cost;
121 printf("merge edge(%d,%d) with cost %.2lf\n",e[i].u,e[i].v,e[i].cost);
122 }
123 }
124 printf("total cost %.2lf\n:",total);
125 return;
126 }
127
128 int main()
129 {
130 freopen("graph.txt","r",stdin);
131 scanf("%d%d",&n,&ce);
132 int i,j,k,c;
133 for(i=1;i<=ce;i++) scanf("%d%d%lf",&e[i].u,&e[i].v,&e[i].cost);
134 kruskal();
135 return 1;
136 }