标题： Prim和Kruskal最小生成树
时 限：2000 ms
内存限制：15000 K
总时限：3000 ms
描述：给出一个矩阵，要求以矩阵方式单步输出生成过程。
要求先输出Prim生成过程，再输出Kruskal,每个矩阵输出后换行。
注意，题中矩阵表示无向图
输入：结点数
矩阵
输出：Prim:
矩阵输出
Kruskal:
矩阵输出
输入样例：
3
0 1 3
1 0 2
3 2 0
输出样例：
3
0 1 3
1 0 2
3 2 0
Prim:
0 0 0
0 0 0
0 0 0
0 1 0
1 0 0
0 0 0
0 1 0
1 0 2
0 2 0
Kruskal:
0 0 0
0 0 0
0 0 0
0 1 0
1 0 0
0 0 0
0 1 0
1 0 2
0 2 0
提示：Kruskal 中的边集合应用拓扑排序的想法排除环
来源：教材P170-179
1 //2016.10.25
2 #include <iostream>
3 #include <cstdio>
4 #include <cstring>
5 #include <algorithm>
6 #define N 200
7
8 using namespace std;
9
10 struct Edge
11 {
12 int u, v, c;
13 bool operator<(Edge x){
14 return c < x.c;
15 }
16 }edge[100005];
17 int G[N][N], T[N][N], n, cnt, fa[N];
18
19 void print(int T[][N])
20 {
21 for(int i = 1; i <= n; i++){
22 for(int j = 1; j <= n; j++){
23 printf("%d ", T[i][j]);
24 }
25 printf("\n");
26 }
27 printf("\n");
28 }
29
30 void init(int n)
31 {
32 for(int i = 1; i <= n; i++)
33 fa[i] = i;
34 }
35
36 int getfa(int x)
37 {
38 if(fa[x] == x) return x;
39 return fa[x] = getfa(fa[x]);
40 }
41
42 void myUnion(int a, int b)
43 {
44 int af = getfa(a);
45 int bf = getfa(b);
46 if(af != bf)fa[bf] = af;
47 }
48
49 void prim()
50 {
51 int book[N], uf, vf;
52 memset(T, 0, sizeof(T));
53 memset(book, 0, sizeof(book));
54 print(T);
55 sort(edge, edge+cnt);
56 init(n);
57 int cntv = 1;
58 int parent = edge[0].u;
59 while(cntv < n)
60 {
61 for(int i = 0; i < cnt; i++)
62 {
63 if(book[i])continue;
64 uf = getfa(edge[i].u);
65 vf = getfa(edge[i].v);
66 if((uf == parent || vf == parent) && uf != vf)
67 {
68 myUnion(parent, uf);
69 myUnion(parent, vf);
70 book[i] = 1;
71 T[edge[i].u][edge[i].v] = T[edge[i].v][edge[i].u] = edge[i].c;
72 print(T);
73 cntv++;
74 break;
75 }
76 }
77 }
78 return ;
79 }
80
81 void kruskal()
82 {
83 sort(edge, edge+cnt);
84 int book[N], uf, vf;
85 init(n);
86 memset(book, 0, sizeof(book));
87 memset(T, 0, sizeof(T));
88 print(T);
89 for(int i = 0; i < cnt; i++)
90 {
91 uf = getfa(edge[i].u);
92 vf = getfa(edge[i].v);
93 if(uf != vf)
94 {
95 T[edge[i].u][edge[i].v] = T[edge[i].v][edge[i].u] = edge[i].c;
96 myUnion(edge[i].u, edge[i].v);
97 book[edge[i].u] = book[edge[i].v] = 1;
98 print(T);
99 }
100 int sum = 0;
101 for(int i = 1; i <= n; i++){
102 if(fa[i] == i)sum++;
103 if(sum > 1)break;
104 }
105 if(sum==1)break;
106 }
107 return;
108 }
109
110 int main()
111 {
112 cnt = 0;
113 scanf("%d", &n);
114 for(int i = 1; i <= n; i++)
115 for(int j = 1; j <= n; j++)
116 {
117 scanf("%d", &G[i][j]);
118 if(i < j && G[i][j] != 0)
119 {
120 edge[cnt].u = i;
121 edge[cnt].v = j;
122 edge[cnt].c = G[i][j];
123 cnt++;
124 }
125 }
126 printf("Prim:\n");
127 prim();
128 printf("Kruskal:\n");
129 kruskal();
130
131 return 0;
132 }