最小生成树算法的相关变形题
由于吉大近几年的考试中，算法大题里频繁地出现最小生成树算法的变形题，因此在此整理一下。
PS：prim算法不管是画图还是代码题真的难用，kruskal算法才是永远滴神
目录
最小生成树
最大生成树
加入一条新边，求新的最小生成树
次小生成树
判断最小生成树是否唯一
最小生成树
#define maxsize 100
//并查集
int father[maxsize] = { 0 };
int Find(int x)
{
if (father[x] <= 0) return x;
return father[x] = Find(father[x]);
}
void Union(int x, int y)
{
int fx = Find(x);
int fy = Find(y);
if (fx == fy) return;
if (father[fx] < father[fy])
{
father[fy] = fx;
}
else
{
if (father[fx] == father[fy])
{
father[fy]--;
}
father[fx] = fy;
}
}
//对边进行排序，并存入edge数组中
int sort_edge(int graph[][6], int n, int edge[][3])
{
int edgenum = 0; //k为边的数量
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
if (graph[i][j])
{
edgenum++;
edge[edgenum][0] = i;
edge[edgenum][1] = j;
edge[edgenum][2] = graph[i][j];
}
}
}
for (int i = edgenum; i > 1; i--)
{
int flag = 0;
for (int j = 1; j < i; j++)
{
if (edge[j][2] > edge[j + 1][2])
{
flag = 1;
int temp = edge[j][0];
edge[j][0] = edge[j + 1][0];
edge[j + 1][0] = temp;
temp = edge[j][1];
edge[j][1] = edge[j + 1][1];
edge[j + 1][1] = temp;
temp = edge[j][2];
edge[j][2] = edge[j + 1][2];
edge[j + 1][2] = temp;
}
}
if (!flag) break;
}
printf("排序后的边为：");
for (int i = 1; i <= edgenum; i++)
{
printf("%d--%d:%d ", edge[i][0], edge[i][1], edge[i][2]);
}printf("\n\n");
return edgenum;
}
//kruskal算法
void kruskal(int graph[][6], int n)
{
int edge[maxsize][3];
int edgenum = sort_edge(graph, n, edge);
int T = n; //集合的个数
int k = 1;
int ans = 0;
printf("最小生成树：");
while (T > 1)
{
int a = edge[k][0];
int b = edge[k][1];
int w = edge[k][2];
k++;
if (Find(a) == Find(b)) continue;
Union(a, b);
T--;
ans += w;
printf("%d--%d:%d ", a, b, w);
}printf("\n\n");
printf("最小生成树的权值为：%d\n", ans);
}
int main()
{
int graph[6][6] = { 0 };
int n = 5;
graph[1][4] = 1; graph[4][1] = 1;
graph[1][3] = 2; graph[3][1] = 2;
graph[1][2] = 3; graph[2][1] = 3;
graph[3][4] = 4; graph[4][3] = 4;
graph[4][5] = 5; graph[5][4] = 5;
graph[2][5] = 6; graph[5][2] = 6;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
printf("%d ", graph[i][j]);
}printf("\n");
}printf("\n");
kruskal(graph, n);
return 0;
}对于下图来说：
其最小生成树为：
上述代码的结果为：
最大生成树
最简单的一个，就是把一开始的边排序改为降序排序而已，和上面的代码相比就是改了个大于号，其他的都一样
#define maxsize 100
int father[maxsize] = { 0 };
int Find(int x)
{
if (father[x] <= 0) return x;
return father[x] = Find(father[x]);
}
void Union(int x, int y)
{
int fx = Find(x);
int fy = Find(y);
if (fx == fy) return;
if (father[fx] < father[fy])
{
father[fy] = fx;
}
else
{
if (father[fx] == father[fy])
{
father[fy]--;
}
father[fx] = fy;
}
}
//对边进行排序，并存入edge数组中
int sort_edge(int graph[][6], int n, int edge[][3])
{
int edgenum = 0; //k为边的数量
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
if (graph[i][j])
{
edgenum++;
edge[edgenum][0] = i;
edge[edgenum][1] = j;
edge[edgenum][2] = graph[i][j];
}
}
}
for (int i = edgenum; i > 1; i--)
{
int flag = 0;
for (int j = 1; j < i; j++)
{
if (edge[j][2] < edge[j + 1][2]) //这里改为降序排序
{
flag = 1;
int temp = edge[j][0];
edge[j][0] = edge[j + 1][0];
edge[j + 1][0] = temp;
temp = edge[j][1];
edge[j][1] = edge[j + 1][1];
edge[j + 1][1] = temp;
temp = edge[j][2];
edge[j][2] = edge[j + 1][2];
edge[j + 1][2] = temp;
}
}
if (!flag) break;
}
printf("排序后的边为：");
for (int i = 1; i <= edgenum; i++)
{
printf("%d--%d:%d ", edge[i][0], edge[i][1], edge[i][2]);
}printf("\n\n");
return edgenum;
}
void kruskal(int graph[][6], int n)
{
int edge[maxsize][3];
int edgenum = sort_edge(graph, n, edge);
int T = n; //集合的个数
int k = 1;
int ans = 0;
printf("最小生成树：");
while (T > 1)
{
int a = edge[k][0];
int b = edge[k][1];
int w = edge[k][2];
k++;
if (Find(a) == Find(b)) continue;
Union(a, b);
T--;
ans += w;
printf("%d--%d:%d ", a, b, w);
}printf("\n\n");
printf("最小生成树的权值为：%d\n", ans);
}
int main()
{
int graph[6][6] = { 0 };
int n = 5;
graph[1][4] = 1; graph[4][1] = 1;
graph[1][3] = 2; graph[3][1] = 2;
graph[1][2] = 3; graph[2][1] = 3;
graph[3][4] = 4; graph[4][3] = 4;
graph[4][5] = 5; graph[5][4] = 5;
graph[2][5] = 6; graph[5][2] = 6;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
printf("%d ", graph[i][j]);
}printf("\n");
}printf("\n");
kruskal(graph, n);
return 0;
}对于下图来说：
其最大生成树为：
代码的结果为：
加入一条新边，求新的最小生成树
假设图G的最小生成树T已知，现给定一条加入G的新边e（G的点集不变），给出寻找G+e新图的最小生成树算法，时间复杂度O(n)，n为G的顶点数，G/T采用邻接表/矩阵存储即可。
大致思路：在最小生成树中加入一条新边 newa -- newb（权值为neww），肯定会构成一个环，然后找到环中除了新边 newa -- newb 之外最长的一条边的权值，也就是在原先的最小生成树中从节点newa到节点newb的路径上最长的一条边的权值maxw，如果新边的权值neww < maxw，那么我们就可以用这条新边代替原先的最长边，新的最小生成树的权值自然也会变小；如果neww >= maxw，那么不用替代，原先的最小生成树依旧是新的最小生成树。
实际上就是在原先的kruskal算法的基础上增加了两个函数：
int mintree[maxsize][maxsize] = { 0 }; //用邻接矩阵的方式存储最小生成树
int n = 5;
//用dfs找到形成的环中，除新加入的边 a-b 外，最长的一条边的权值
//即在原先的生成树中，从节点a到节点b的路径上最长的一条边的权值
void dfs(int v, int b, int visited[], int curw, int* maxw) //curw是从节点a到当前节点v的路径上最长的一条边的权值
{
visited[v] = 1;
if (v == b) //如果找到了b节点
{
*maxw = curw;
return;
}
for (int i = 1; i <= n; i++)
{
if (mintree[v][i] != 0 && !visited[i])
{
int temp = curw; //记录一下原先curw的值，用于回溯
if (mintree[v][i] > curw) curw = mintree[v][i];
dfs(i, b, visited, curw, maxw);
curw = temp; //回溯
}
}
}
//向图中加入一条新边后，求最小生成树
void Add_newedge(int newa, int newb, int neww, int ans)
{
int visited[maxsize] = { 0 };
int maxw; //存储最长边的权值
dfs(newa, newb, visited, 0, &maxw);
printf("在原先的最小生成树中，节点%d到节点%d的路径上的最长边的权值为：%d\n\n", newa, newb, maxw);
if (neww < maxw) //如果新加入的这条边的权值小于最长边的权值，那么就能够用这题新边代替原来的最长边
{
ans = ans - maxw + neww;
}
printf("加入边 %d--%d 后，新的最小生成树的权值为：%d\n",newa, newb, ans);
}完整的代码如下：
#define maxsize 100
int father[maxsize] = { 0 };
int Find(int x)
{
if (father[x] <= 0) return x;
return father[x] = Find(father[x]);
}
void Union(int x, int y)
{
int fx = Find(x);
int fy = Find(y);
if (fx == fy) return;
if (father[fx] < father[fy])
{
father[fy] = fx;
}
else
{
if (father[fx] == father[fy])
{
father[fy]--;
}
father[fx] = fy;
}
}
//对边进行排序，并存入edge数组中
int sort_edge(int graph[][6], int n, int edge[][3])
{
int edgenum = 0; //k为边的数量
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
if (graph[i][j])
{
edgenum++;
edge[edgenum][0] = i;
edge[edgenum][1] = j;
edge[edgenum][2] = graph[i][j];
}
}
}
for (int i = edgenum; i > 1; i--)
{
int flag = 0;
for (int j = 1; j < i; j++)
{
if (edge[j][2] > edge[j + 1][2])
{
flag = 1;
int temp = edge[j][0];
edge[j][0] = edge[j + 1][0];
edge[j + 1][0] = temp;
temp = edge[j][1];
edge[j][1] = edge[j + 1][1];
edge[j + 1][1] = temp;
temp = edge[j][2];
edge[j][2] = edge[j + 1][2];
edge[j + 1][2] = temp;
}
}
if (!flag) break;
}
printf("排序后的边为：");
for (int i = 1; i <= edgenum; i++)
{
printf("%d--%d:%d ", edge[i][0], edge[i][1], edge[i][2]);
}printf("\n\n");
return edgenum;
}
int mintree[maxsize][maxsize] = { 0 }; //用邻接矩阵的方式存储最小生成树
int n = 5;
//找到形成的环中，除新加入的边 a-b 外，最长的一条边的权值
//即在原先的生成树中，从节点a到节点b的路径上最长的一条边的权值
void dfs(int v, int b, int visited[], int curw, int* maxw) //curw是从节点a到当前节点v的路径上最长的一条边的权值
{
visited[v] = 1;
if (v == b) //如果找到了b节点
{
*maxw = curw;
return;
}
for (int i = 1; i <= n; i++)
{
if (mintree[v][i] != 0 && !visited[i])
{
int temp = curw; //记录一下原先curw的值，用于回溯
if (mintree[v][i] > curw) curw = mintree[v][i];
dfs(i, b, visited, curw, maxw);
curw = temp; //回溯
}
}
}
//向图中加入一条新边后，求最小生成树
void Add_newedge(int newa, int newb, int neww, int ans)
{
int visited[maxsize] = { 0 };
int maxw; //存储最长边的权值
dfs(newa, newb, visited, 0, &maxw);
printf("在原先的最小生成树中，节点%d到节点%d的路径上的最长边的权值为：%d\n\n", newa, newb, maxw);
if (neww < maxw) //如果新加入的这条边的权值小于最长边的权值，那么就能够用这题新边代替原来的最长边
{
ans = ans - maxw + neww;
}
printf("加入边 %d--%d 后，新的最小生成树的权值为：%d\n",newa, newb, ans);
}
int kruskal(int graph[][6], int n)
{
int edge[maxsize][3];
int edgenum = sort_edge(graph, n, edge);
int T = n; //集合的个数
int k = 1;
int ans = 0;
printf("最小生成树：");
while (T > 1)
{
int a = edge[k][0];
int b = edge[k][1];
int w = edge[k][2];
k++;
if (Find(a) == Find(b)) continue;
Union(a, b);
T--;
ans += w;
mintree[a][b] = mintree[b][a] = w;
printf("%d--%d:%d ", a, b, w);
}printf("\n\n");
printf("最小生成树的权值为：%d\n\n", ans);
return ans;
}
int main()
{
int graph[6][6] = { 0 };
int n = 5;
graph[1][4] = 1; graph[4][1] = 1;
graph[1][3] = 2; graph[3][1] = 2;
graph[1][2] = 3; graph[2][1] = 3;
graph[3][4] = 4; graph[4][3] = 4;
graph[4][5] = 5; graph[5][4] = 5;
graph[2][5] = 6; graph[5][2] = 6;
printf("原图：\n");
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
printf("%d ", graph[i][j]);
}printf("\n");
}printf("\n");
int ans = kruskal(graph, n);
printf("--------------------------------------------------------------------------\n\n");
printf("最小生成树的邻接矩阵表示：\n");
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
printf("%d ", mintree[i][j]);
}printf("\n");
}printf("\n");
printf("加入一条新边 2--4，权值为1\n\n");
//加入一条新边 2-4 ，权值为1
Add_newedge(2, 4, 1, ans);
return 0;
}对于下图来说：
加入一条新边后：
上述代码的打印结果为：
次小生成树
只要会了 “加入一条新边，求新的最小生成树” 这题的话，求次小生成树就不难了，思路基本一致，只是稍微改动一些地方。
大致思路：先求得最小生成树，然后枚举图中未加入最小生成树的各条边， 在最小生成树中加入一条新边 newa -- newb（权值为neww），肯定会构成一个环，然后找到环中除了新边 newa -- newb 之外最长的一条边的权值，也就是在原先的最小生成树中从节点newa到节点newb的路径上最长的一条边的权值maxw，我们就可以直接用这条新边代替原先的最长边（注意，如果求的是严格次小的话，需要比较neww和maxw的大小，只有neww ≠ maxw时才用新边代替原先的最长边），得到一棵新的生成树；在所有的新生成树中最小的那棵，就是次小生成树。
在main函数中枚举未加入最小生成树的边，调用Add_edge函数：
int newans = 999;
for (int i = 1; i <= edgenum; i++)
{
if (!isuse[i]) //枚举未加入最小生成树的边
{
int tmp = Add_newedge(edge[i][0], edge[i][1], edge[i][2], ans);
if (newans > tmp) newans = tmp;
}
}
printf("次小生成树的权值为：%d\n", newans);完整的代码如下：
#define maxsize 100
int father[maxsize] = { 0 };
int Find(int x)
{
if (father[x] <= 0) return x;
return father[x] = Find(father[x]);
}
void Union(int x, int y)
{
int fx = Find(x);
int fy = Find(y);
if (fx == fy) return;
if (father[fx] < father[fy])
{
father[fy] = fx;
}
else
{
if (father[fx] == father[fy])
{
father[fy]--;
}
father[fx] = fy;
}
}
//对边进行排序，并存入edge数组中
int sort_edge(int graph[][6], int n, int edge[][3])
{
int edgenum = 0; //k为边的数量
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
if (graph[i][j])
{
edgenum++;
edge[edgenum][0] = i;
edge[edgenum][1] = j;
edge[edgenum][2] = graph[i][j];
}
}
}
for (int i = edgenum; i > 1; i--)
{
int flag = 0;
for (int j = 1; j < i; j++)
{
if (edge[j][2] > edge[j + 1][2])
{
flag = 1;
int temp = edge[j][0];
edge[j][0] = edge[j + 1][0];
edge[j + 1][0] = temp;
temp = edge[j][1];
edge[j][1] = edge[j + 1][1];
edge[j + 1][1] = temp;
temp = edge[j][2];
edge[j][2] = edge[j + 1][2];
edge[j + 1][2] = temp;
}
}
if (!flag) break;
}
printf("排序后的边为：");
for (int i = 1; i <= edgenum; i++)
{
printf("%d--%d:%d ", edge[i][0], edge[i][1], edge[i][2]);
}printf("\n\n");
return edgenum;
}
int mintree[maxsize][maxsize] = { 0 }; //用邻接矩阵的方式存储最小生成树
int n = 5;
//找到形成的环中，除新加入的边 a-b 外，最长的一条边的权值
//即在原先的生成树中，从节点a到节点b的路径上最长的一条边的权值
void dfs(int v, int b, int visited[], int curw, int* maxw) //curw是从节点a到当前节点v的路径上最长的一条边的权值
{
visited[v] = 1;
if (v == b) //如果找到了b节点
{
*maxw = curw;
return;
}
for (int i = 1; i <= n; i++)
{
if (mintree[v][i] != 0 && !visited[i])
{
int temp = curw; //记录一下原先curw的值，用于回溯
if (mintree[v][i] > curw) curw = mintree[v][i];
dfs(i, b, visited, curw, maxw);
curw = temp; //回溯
}
}
}
//向图中加入一条新边后，求最小生成树
int Add_newedge(int newa, int newb, int neww, int ans)
{
int visited[maxsize] = { 0 };
int maxw; //存储最长边的权值
dfs(newa, newb, visited, 0, &maxw);
printf("在原先的最小生成树中，节点%d到节点%d的路径上的最长边的权值为：%d\n", newa, newb, maxw);
ans = ans - maxw + neww;
printf("加入边 %d--%d 后，新的最小生成树的权值为：%d\n\n", newa, newb, ans);
return ans;
}
int edge[maxsize][3]; //存储边的数组
int edgenum; //边数
int isuse[maxsize] = { 0 }; //标记某个边是否被用来加入最小生成树
int kruskal(int graph[][6], int n)
{
edgenum = sort_edge(graph, n, edge);
int T = n; //集合的个数
int k = 1;
int ans = 0;
printf("最小生成树：");
while (T > 1)
{
int a = edge[k][0];
int b = edge[k][1];
int w = edge[k][2];
k++;
if (Find(a) == Find(b)) continue;
Union(a, b);
T--;
ans += w;
mintree[a][b] = mintree[b][a] = w;
isuse[k - 1] = 1;
printf("%d--%d:%d ", a, b, w);
}printf("\n\n");
printf("最小生成树的权值为：%d\n\n", ans);
return ans;
}
int main()
{
int graph[6][6] = { 0 };
int n = 5;
graph[1][4] = 1; graph[4][1] = 1;
graph[1][3] = 2; graph[3][1] = 2;
graph[1][2] = 3; graph[2][1] = 3;
graph[3][4] = 4; graph[4][3] = 4;
graph[4][5] = 5; graph[5][4] = 5;
graph[2][5] = 6; graph[5][2] = 6;
printf("原图：\n");
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
printf("%d ", graph[i][j]);
}printf("\n");
}printf("\n");
int ans = kruskal(graph, n);
printf("--------------------------------------------------------------------------\n\n");
printf("最小生成树的邻接矩阵表示：\n");
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
printf("%d ", mintree[i][j]);
}printf("\n");
}printf("\n");
int newans = 999;
for (int i = 1; i <= edgenum; i++)
{
if (!isuse[i]) //枚举未加入最小生成树的边
{
int tmp = Add_newedge(edge[i][0], edge[i][1], edge[i][2], ans);
if (newans > tmp) newans = tmp;
}
}
printf("次小生成树的权值为：%d\n", newans);
return 0;
}对于下图来说：
其次小生成树为：
上述的代码的打印结果为：
判断最小生成树是否唯一
可以用求次小生成树的办法，如果次小生成树的权值与最小生成树的权值相同，就说明最小生成树不唯一，但是这题倒不用这么复杂。
原理： 如果无向图中各边的权值各不相同，那么用Kruskal算法构造的最小生成树是惟一的，因此在无向图中存在相同权值的边是最小生成树不唯一的必要非充分条件。
大致思路：在使用Kruskal算法时，如果有两条边的权值相同，并且都能将两个相同的连通块合并，那么这两条边选择哪个都行，于是最小生成树就不唯一了。
只要在kruskal算法的基础上，改一下kruskal函数即可：
//kruskal算法
void kruskal(int graph[][6], int n)
{
int edge[maxsize][3];
int edgenum = sort_edge(graph, n, edge);
int T = n; //集合的个数
int k = 1;
int ans = 0;
//printf("最小生成树：");
while (T > 1)
{
int a = edge[k][0];
int b = edge[k][1];
int w = edge[k][2];
k++;
if (Find(a) == Find(b)) continue;
//由于边是降序排序的，因此可以往后查找与当前的边权值相同的边
for (int i = k; i <= edgenum; i++)
{
if (edge[i][2] == edge[k][2])
{
int newa = edge[i][0];
int newb = edge[i][1];
//如果 a--b 和 newa--newb 这两边权值相同，并且所处的两个连通块都一样，就说明最小生成树不唯一
if (Find(a) == Find(newa) && Find(b) == Find(newb))
{
printf("最小生成树不唯一\n");
return;
}
}
}
Union(a, b);
T--;
ans += w;
//printf("%d--%d:%d ", a, b, w);
}printf("\n\n");
printf("最小生成树的权值为：%d\n", ans);
}
完整的代码如下：
#define maxsize 100
//并查集
int father[maxsize] = { 0 };
int Find(int x)
{
if (father[x] <= 0) return x;
return father[x] = Find(father[x]);
}
void Union(int x, int y)
{
int fx = Find(x);
int fy = Find(y);
if (fx == fy) return;
if (father[fx] < father[fy])
{
father[fy] = fx;
}
else
{
if (father[fx] == father[fy])
{
father[fy]--;
}
father[fx] = fy;
}
}
//对边进行排序，并存入edge数组中
int sort_edge(int graph[][6], int n, int edge[][3])
{
int edgenum = 0; //k为边的数量
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
if (graph[i][j])
{
edgenum++;
edge[edgenum][0] = i;
edge[edgenum][1] = j;
edge[edgenum][2] = graph[i][j];
}
}
}
for (int i = edgenum; i > 1; i--)
{
int flag = 0;
for (int j = 1; j < i; j++)
{
if (edge[j][2] > edge[j + 1][2])
{
flag = 1;
int temp = edge[j][0];
edge[j][0] = edge[j + 1][0];
edge[j + 1][0] = temp;
temp = edge[j][1];
edge[j][1] = edge[j + 1][1];
edge[j + 1][1] = temp;
temp = edge[j][2];
edge[j][2] = edge[j + 1][2];
edge[j + 1][2] = temp;
}
}
if (!flag) break;
}
printf("排序后的边为：");
for (int i = 1; i <= edgenum; i++)
{
printf("%d--%d:%d ", edge[i][0], edge[i][1], edge[i][2]);
}printf("\n\n");
return edgenum;
}
//kruskal算法
void kruskal(int graph[][6], int n)
{
int edge[maxsize][3];
int edgenum = sort_edge(graph, n, edge);
int T = n; //集合的个数
int k = 1;
int ans = 0;
//printf("最小生成树：");
while (T > 1)
{
int a = edge[k][0];
int b = edge[k][1];
int w = edge[k][2];
k++;
if (Find(a) == Find(b)) continue;
//由于边是降序排序的，因此可以往后查找与当前的边权值相同的边
for (int i = k; i <= edgenum; i++)
{
if (edge[i][2] == w) //如果 a--b 和 newa--newb 这两边权值相同
{
int newa = edge[i][0];
int newb = edge[i][1];
//并且两边所处的两个连通块都一样，就说明最小生成树不唯一
if (Find(a) == Find(newa) && Find(b) == Find(newb) || Find(a) == Find(newb) && Find(b) == Find(newa))
{
printf("边 %d--%d 与边 %d-- %d 可任意选，最小生成树不唯一\n", a, b, newa, newb);
return;
}
}
}
Union(a, b);
T--;
ans += w;
//printf("%d--%d:%d ", a, b, w);
}printf("\n\n");
printf("最小生成树的权值为：%d\n", ans);
}
int main()
{
int graph[6][6] = { 0 };
int n = 5;
graph[1][4] = 1; graph[4][1] = 1;
graph[1][3] = 2; graph[3][1] = 2;
graph[1][2] = 3; graph[2][1] = 3;
graph[3][4] = 4; graph[4][3] = 4;
graph[4][5] = 5; graph[5][4] = 5;
graph[2][5] = 6; graph[5][2] = 6;
graph[2][4] = 3; graph[4][2] = 3;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
printf("%d ", graph[i][j]);
}printf("\n");
}printf("\n");
kruskal(graph, n);
return 0;
}对于下图来说：
上述代码的打印结果为：
