图之最小生成树Kruskal算法详解（C语言版）
Kruskal算法（克鲁斯卡尔算法）查找最小生成树的方法是：将连通网中所有的边按照权值大小做升序排序，从权值最小的边开始选择，只要此边不和已选择的边一起构成环路，就可以选择它组成最小生成树。对于 N 个顶点的连通网，挑选出 N-1 条符合条件的边，这些边组成的生成树就是最小生成树。
文章共15,377字 · 阅读需要大约52分钟
一键AI生成摘要，助你高效阅读
问答
·
一、Kruskal算法思想
Kruskal算法（克鲁斯卡尔算法）查找最小生成树的方法是：将连通网中所有的边按照权值大小做升序排序，从权值最小的边开始选择，只要此边不和已选择的边一起构成环路，就可以选择它组成最小生成树。对于 N 个顶点的连通网，挑选出 N-1 条符合条件的边，这些边组成的生成树就是最小生成树。
举个例子，下图是一个连通网有A、B、C、D、E、F六个顶点，它们的编号依次是0、1、2、3、4、5。使用克鲁斯卡尔算法查找最小生成树的过程如下所示，代价分别为1，2，3，4的 4 条边由于满足上述条件，则先后被加入到组成最小生成树的边中，代价为5的两条边(A，D)和(C，D)被舍去。因为它们依附的两顶点在同一连通分量上，它们若加入最小生成树的边中,则会使最小生成树产生回路，而下一条代价等于5的最小边(B，C)联结两个连通分量，则可加入组成最小生成树的边中。由此，构造成一棵最小生成树。
每当添加一条边<i，j>作为最小生成树的边时，都需要根据father数组判断一下，这条边加入后是否会造成环路，如果不会造成环路就将该边加入到father数组中，进行标记（father[顶点j的最终父顶点] = 顶点i的最终父顶点）。其中father数组判断是否形成环路的方式是：分别将构成边的两个顶点i、j，放到father数组中查找，查找两个顶点的最终父顶点，如果两者的父顶点相同则说明加入后会形成环，如果不同就不会形成环。
将各个边按权值升序排列，并根据图结构初始化father数组father[i] = i（即顶点的父顶点是自己）
father[0] = 0
father[1] = 1
father[2] = 2
father[3] = 3
father[4] = 4
father[5] = 5
取出第 1 条边<A，C>，将A、C两个顶点的编号 i = 0，j = 2放到father数组查找它们的父顶点编号，查找到的编号分别是0、2对应顶点A、C，两个父顶点不同，则说明这条边加入后不会形成环，所以将边加入更新father数组（father[2] = 0）
father[0] = 0
father[1] = 1
father[2] = 0
father[3] = 3
father[4] = 4
father[5] = 5
取出第 2 条边<D，F>，将D、F两个顶点的编号 i = 3，j = 5放到father数组查找它们的父顶点编号，查找到的编号分别是3、5对应顶点D、F，两个父顶点不同，则说明这条边加入后不会形成环，所以将边加入更新father数组（father[5] = 3）
father[0] = 0
father[1] = 1
father[2] = 0
father[3] = 3
father[4] = 4
father[5] = 3
取出第 3 条边<B，E>，将B、E两个顶点的编号 i = 1，j = 4放到father数组查找它们的父顶点编号，查找到的编号分别是1、4对应顶点B、E，两个父顶点不同，则说明这条边加入后不会形成环，所以将边加入更新father数组（father[4] = 1）
father[0] = 0
father[1] = 1
father[2] = 0
father[3] = 3
father[4] = 1
father[5] = 3
取出第 4 条边<C，F>，将C、F两个顶点的编号 i = 2，j = 5放到father数组查找它们的父顶点编号，查找到的编号分别是0、3对应顶点A、D，两个父顶点不同，则说明这条边加入后不会形成环，所以将边加入更新father数组（father[3] = 0）
father[0] = 0
father[1] = 1
father[2] = 0
father[3] = 0
father[4] = 1
father[5] = 3
取出第 5 条边<A，D>，将A、D两个顶点的编号 i = 0，j = 3放到father数组查找它们的父顶点编号，查找到的编号分别是0、0对应顶点A、A，两个父顶点相同，则说明这条边加入后会形成环，不能将该边作为最小生成树的边，将该边抛弃。
取出第 6 条边<B，C>，将B、C两个顶点的编号 i = 1，j = 2放到father数组查找它们的父顶点编号，查找到的编号分别是1、0对应顶点B、A，两个父顶点不同，则说明这条边加入后不会形成环，所以将边加入更新father数组（father[0] = 1）
father[0] = 1
father[1] = 1
father[2] = 0
father[3] = 0
father[4] = 1
father[5] = 3
由于该图有六个顶点，所以其最小生成树有5条边，到此已经找出其最小生成树的五条边，流程结束。
二、数据结构
1、图的存放结构：邻接矩阵
邻接矩阵的实现方式可查看：图之邻接矩阵详解（C语言版）
//设置默认的顶点个数
#define Default_Vertex_Size 10
//数据类型
#define T char
#define E int
#define MAX_COST 0x7FFFFFFF //代表无穷大
//邻接矩阵图结构
typedef struct GraphMtx
{
int MaxVertices; //最大顶点数
int NumVertices; //真实的顶点数
int NumEdges; //边数
T *VerticesList; //顶点列表
int **Edge; //边信息矩阵
}GraphMtx;
2、Kruskal算法所需的结构
//选取的边
typedef struct Edge
{
int x; // start 开始点
int y; // end 结束点
E cost; //边权值
}Edge;
//father数组，用来标记边的两个顶点是否在相同集合
int *father = (int*)malloc(sizeof(int) * n);
三、代码实现
1、领接矩阵实现
图初始化
//图的初始化
void InitGraph(GraphMtx *g)
{
g->MaxVertices = Default_Vertex_Size;//最大顶点数初始化
g->NumVertices = g->NumEdges = 0; //实际顶点数初始化
//分配顶点存储列表的空间
g->VerticesList = (T*)malloc(sizeof(T)*(g->MaxVertices));
assert(g->VerticesList != NULL);
//开辟边信息存储矩阵的空间（二维数组的动态开辟）
g->Edge = (int**)malloc(sizeof(int*) * g->MaxVertices); //总行数的开辟
assert(g->Edge != NULL);
for(int i=0; i<g->MaxVertices; ++i) //每一行内具体的空间开辟
{
g->Edge[i] = (int*)malloc(sizeof(int) * g->MaxVertices);
}
for(i=0; i<g->MaxVertices; ++i) //初始化
{
for(int j=0; j<g->MaxVertices; ++j)
{
if(i == j)
{
g->Edge[i][j] = 0;
}
else
{
g->Edge[i][j] = MAX_COST;
}
}
}
}
获取顶点的位置
//获取顶点的位置
int GetVertexPos(GraphMtx *g, T v)
{
for(int i=0; i<g->NumVertices; ++i) //对所有顶点进行遍历
{
//判断是否找到顶点v所在位置
if(g->VerticesList[i] == v)
return i;
}
return -1;
}
打印图信息
//打印图信息
void ShowGraph(GraphMtx *g)
{
printf(" ");
for(int i=0; i<g->NumVertices; ++i) //获取顶点，并打印
{
printf("%c ",g->VerticesList[i]);
}
printf("\n");
for(i=0; i<g->NumVertices; ++i) //打印顶点间边的信息
{
printf("%c ",g->VerticesList[i]);
for(int j=0; j<g->NumVertices; ++j)
{
if(g->Edge[i][j] == MAX_COST)
{
printf("%c ",'@');
}
else
{
printf("%d ",g->Edge[i][j]);
}
}
printf("\n");
}
printf("\n");
}
插入顶点
//插入顶点
void InsertVertex(GraphMtx *g, T v)
{
if(g->NumVertices >= g->MaxVertices) //判断顶点空间是否已满
return;
g->VerticesList[g->NumVertices++] = v; //还有空间，放入顶点
}
插入边：在v1和v2顶点间插入边
//插入边：在v1和v2顶点间插入边
void InsertEdge(GraphMtx *g, T v1, T v2, E cost)
{
int p1 = GetVertexPos(g,v1); //获取v1顶点位置
int p2 = GetVertexPos(g,v2); //获取v2顶点位置
if(p1==-1 || p2==-1)
return;
//无向图存储 需要双向的
g->Edge[p1][p2] = g->Edge[p2][p1] = cost;
g->NumEdges++; //记录实际边数
}
删除边：删除v1和v2顶点间的边
//删除边：删除v1和v2顶点间的边
void RemoveEdge(GraphMtx *g, T v1, T v2)
{
//求出两个顶点的下标位置
int p1 = GetVertexPos(g,v1);
int p2 = GetVertexPos(g,v2);
if(p1==-1 || p2==-1)
return;
if(g->Edge[p1][p2] == 0)
return;
//将边清空
g->Edge[p1][p2] = g->Edge[p2][1] = 0;
g->NumEdges--; //更新边数
}
删除顶点
//删除顶点
void RemoveVertex(GraphMtx *g, T v)
{
//获取顶点的位置
int p = GetVertexPos(g,v);
if(p == -1)
return;
//释放顶点
int numedges = 0;
for(int i=p; i<g->NumVertices-1; ++i)
{
//将要释放顶点之后的顶点逐一前移
g->VerticesList[i] = g->VerticesList[i+1];
}
//统计与要删除顶点相连的边条数
for(i=0; i<g->NumVertices; ++i)
{
if(g->Edge[p][i] != 0)
{
numedges++;
}
}
//删除与释放顶点相连的边（更改存放边信息的矩阵）
for(i=p; i<g->NumVertices-1; ++i)
{
//将要删除行之后的行逐一向前移动一行
for(int j=0; j<g->NumVertices; ++j)
{
g->Edge[i][j] = g->Edge[i+1][j];
}
}
for(i=p; i<g->NumVertices; ++i)//删除列
{
//将要删除列之后的列逐一向前移动一列
for(int j=0; j<g->NumVertices; ++j)
{
g->Edge[j][i] = g->Edge[j][i+1];
}
}
g->NumVertices--;
g->NumEdges -= numedges;
}
销毁图
//销毁图
void DestroyGraph(GraphMtx *g)
{
//释放顶点
free(g->VerticesList);
g->VerticesList = NULL;
//释放边存储结构的列
for(int i=0; i<g->NumVertices; ++i)
{
free(g->Edge[i]);
}
free(g->Edge);//释放存放行指针的空间
g->Edge = NULL;
g->MaxVertices = g->NumEdges = g->NumVertices = 0;
}
获取v第一个邻接顶点
//获取v第一个邻接顶点
int GetFirstNeighbor(GraphMtx *g, T v)
{
//获取顶点v所在位置
int p = GetVertexPos(g,v);
if(p == -1)
return -1;
//对顶点进行搜索，看那个顶点与v相连
for(int i=0; i<g->NumVertices; ++i)
{
//判断是否，找到
if(g->Edge[p][i] == 1)
return i; //找到即返回
}
return -1;
}
获取下一个邻接顶点：获取顶点v的邻接顶点（该邻接点的顺序在邻接点w之后）
//获取下一个邻接顶点：获取顶点v的邻接顶点（该邻接点的顺序在邻接点w之后）
int GetNextNeighbor(GraphMtx *g, T v, T w)
{
//获取v和w所在位置
int pv = GetVertexPos(g,v);
int pw = GetVertexPos(g,w);
if(pv==-1 || pw==-1)
return -1;
//从v的邻接顶点w的位置向后搜索，找到第一个与v相邻的顶点，即所求
for(int i=pw+1; i<g->NumVertices; ++i)
{
if(g->Edge[pv][i] == 1)
return i;
}
return -1;
}
获取边的权重
//获取边的权重
E GetWeight(GraphMtx *g, int v1, int v2)
{
if(v1==-1 || v2==-1)
return MAX_COST;
return g->Edge[v1][v2];
}
2、Kruskal算法实现
Kruskal算法获取最小生成树
//使用Kruskal算法获取最小生成树
void MinSpanTree_Kruskal(GraphMtx *g)
{
//申请存放边的空间（根据无向图的对称性只要存放邻接矩阵上三角就可以）
int n = g->NumVertices;
Edge *edge = (Edge *)malloc(sizeof(Edge) * (n*(n-1)/2));
assert(edge != NULL);
//获取邻接矩阵中的边（查找邻接矩阵上三角就可以）
int k = 0;
for(int i=0; i<n; ++i)
{
for(int j=i; j<n; ++j)
{
if(g->Edge[i][j]!=0 && g->Edge[i][j]!=MAX_COST)
{
edge[k].x = i;
edge[k].y = j;
edge[k].cost = g->Edge[i][j];
k++;
}
}
}
int v1,v2;
//将各个边根据边的排序规则（权值越大边越大）排序，升序
qsort(edge,k,sizeof(Edge),cmp);
//初始化father数组，用来标记边的两个顶点是否在相同集合
int *father = (int*)malloc(sizeof(int) * n);
assert(father != NULL);
for(i=0; i<n; ++i)
{
father[i] = i;//顶点i的父顶点为i
}
for(i=0; i<n; ++i)
{
//判断边的两个顶点是否在相同集合，如果在相同集合说明该边不能进行连接，会形成闭环
if(!Is_same(father,edge[i].x,edge[i].y))
{
//不在同一集合，将边加入，并将边在father中进行标注
//由于边根据权值进行升序排列，所以只需要按照顺序取出就可以
v1 = edge[i].x;
v2 = edge[i].y;
printf("%c-->%c : %d\n",g->VerticesList[v1],g->VerticesList[v2],edge[i].cost);
Mark_same(father,edge[i].x,edge[i].y);
}
}
}
边的比较规则：权值大就代表边大
//边的比较规则：权值大就代表边大
int cmp(const void*a, const void *b)
{
return (*(Edge*)a).cost - (*(Edge*)b).cost;
}
判断两个顶点在father中是否记录有相同父顶点
//判断编号为i、j对应的顶点是否同在father集合中(就是查找i、j顶点在father中是否有相同父顶点)
bool Is_same(int *father, int i, int j)
{
//查找顶点i的父顶点
while(father[i] != i)
{
i = father[i];
}
//查找顶点j的父顶点
while(father[j] != j)
{
j = father[j];
}
//判断i、j两个顶点的父顶点是否相同
return i==j;
}
将边的两个顶点i、j在father中进行标注
//将边的两个顶点i、j在father中进行标注
void Mark_same(int *father, int i, int j)
{
//查找顶点i的父顶点
while(father[i] != i)
{
i = father[i];
}
//查找顶点j的父顶点
while(father[j] != j)
{
j = father[j];
}
//合并：
father[j] = i;
}
3、运行结果
#include"GraphMtx.h"
void main()
{
GraphMtx gm;
InitGraph(&gm);
//插入顶点
InsertVertex(&gm,'A');
InsertVertex(&gm,'B');
InsertVertex(&gm,'C');
InsertVertex(&gm,'D');
InsertVertex(&gm,'E');
InsertVertex(&gm,'F');
//插入边
InsertEdge(&gm,'A','B',6);
InsertEdge(&gm,'A','C',1);
InsertEdge(&gm,'A','D',5);
InsertEdge(&gm,'B','C',5);
InsertEdge(&gm,'B','E',3);
InsertEdge(&gm,'C','D',5);
InsertEdge(&gm,'C','E',6);
InsertEdge(&gm,'C','F',4);
InsertEdge(&gm,'D','F',2);
InsertEdge(&gm,'E','F',6);
ShowGraph(&gm);
//MinSpanTree_Prim(&gm,'E');
//使用克鲁斯卡尔算法获取最小生成树
MinSpanTree_Kruskal(&gm);
}
运行结果
测试的图结构
获取的最小生成树
附录
Main.cpp
#include"GraphMtx.h"
void main()
{
GraphMtx gm;
InitGraph(&gm);
//插入顶点
InsertVertex(&gm,'A');
InsertVertex(&gm,'B');
InsertVertex(&gm,'C');
InsertVertex(&gm,'D');
InsertVertex(&gm,'E');
InsertVertex(&gm,'F');
//插入边
InsertEdge(&gm,'A','B',6);
InsertEdge(&gm,'A','C',1);
InsertEdge(&gm,'A','D',5);
InsertEdge(&gm,'B','C',5);
InsertEdge(&gm,'B','E',3);
InsertEdge(&gm,'C','D',5);
InsertEdge(&gm,'C','E',6);
InsertEdge(&gm,'C','F',4);
InsertEdge(&gm,'D','F',2);
InsertEdge(&gm,'E','F',6);
ShowGraph(&gm);
//MinSpanTree_Prim(&gm,'E');
//使用克鲁斯卡尔算法获取最小生成树
MinSpanTree_Kruskal(&gm);
}
GraphMtx.h
#pragma once
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#include<stdlib.h>
#define Default_Vertex_Size 10
#define T char
#define E int
#define MAX_COST 0x7FFFFFFF
typedef struct GraphMtx
{
int MaxVertices;
int NumVertices;
int NumEdges;
T *VerticesList;
int **Edge;
}GraphMtx;
void InitGraph(GraphMtx *g);
int GetVertexPos(GraphMtx *g, T v);
void ShowGraph(GraphMtx *g);
void InsertVertex(GraphMtx *g, T v);
void InsertEdge(GraphMtx *g, T v1, T v2, E cost);
void RemoveVertex(GraphMtx *g, T v);
void RemoveEdge(GraphMtx *g, T v1, T v2);
void DestroyGraph(GraphMtx *g);
int GetFirstNeighbor(GraphMtx *g, T v);
int GetNextNeighbor(GraphMtx *g, T v, T w);
E GetWeight(GraphMtx *g, int v1, int v2);
//
//选取的边
typedef struct Edge
{
int x; // start 开始点
int y; // end 结束点
E cost; //边权值
}Edge;
void MinSpanTree_Kruskal(GraphMtx *g);
GraphMtx.cpp
#include"GraphMtx.h"
//图的初始化
void InitGraph(GraphMtx *g)
{
g->MaxVertices = Default_Vertex_Size;//最大顶点数初始化
g->NumVertices = g->NumEdges = 0; //实际顶点数初始化
//分配顶点存储列表的空间
g->VerticesList = (T*)malloc(sizeof(T)*(g->MaxVertices));
assert(g->VerticesList != NULL);
//开辟边信息存储矩阵的空间（二维数组的动态开辟）
g->Edge = (int**)malloc(sizeof(int*) * g->MaxVertices); //总行数的开辟
assert(g->Edge != NULL);
for(int i=0; i<g->MaxVertices; ++i) //每一行内具体的空间开辟
{
g->Edge[i] = (int*)malloc(sizeof(int) * g->MaxVertices);
}
for(i=0; i<g->MaxVertices; ++i) //初始化
{
for(int j=0; j<g->MaxVertices; ++j)
{
if(i == j)
{
g->Edge[i][j] = 0;
}
else
{
g->Edge[i][j] = MAX_COST;
}
}
}
}
//获取顶点的位置
int GetVertexPos(GraphMtx *g, T v)
{
for(int i=0; i<g->NumVertices; ++i) //对所有顶点进行遍历
{
//判断是否找到顶点v所在位置
if(g->VerticesList[i] == v)
return i;
}
return -1;
}
//打印图信息
void ShowGraph(GraphMtx *g)
{
printf(" ");
for(int i=0; i<g->NumVertices; ++i) //获取顶点，并打印
{
printf("%c ",g->VerticesList[i]);
}
printf("\n");
for(i=0; i<g->NumVertices; ++i) //打印顶点间边的信息
{
printf("%c ",g->VerticesList[i]);
for(int j=0; j<g->NumVertices; ++j)
{
if(g->Edge[i][j] == MAX_COST)
{
printf("%c ",'@');
}
else
{
printf("%d ",g->Edge[i][j]);
}
}
printf("\n");
}
printf("\n");
}
//插入顶点
void InsertVertex(GraphMtx *g, T v)
{
if(g->NumVertices >= g->MaxVertices) //判断顶点空间是否已满
return;
g->VerticesList[g->NumVertices++] = v; //还有空间，放入顶点
}
//插入边：在v1和v2顶点间插入边
void InsertEdge(GraphMtx *g, T v1, T v2, E cost)
{
int p1 = GetVertexPos(g,v1); //获取v1顶点位置
int p2 = GetVertexPos(g,v2); //获取v2顶点位置
if(p1==-1 || p2==-1)
return;
//无向图存储 需要双向的
g->Edge[p1][p2] = g->Edge[p2][p1] = cost;
g->NumEdges++; //记录实际边数
}
//删除边：删除v1和v2顶点间的边
void RemoveEdge(GraphMtx *g, T v1, T v2)
{
//求出两个顶点的下标位置
int p1 = GetVertexPos(g,v1);
int p2 = GetVertexPos(g,v2);
if(p1==-1 || p2==-1)
return;
if(g->Edge[p1][p2] == 0)
return;
//将边清空
g->Edge[p1][p2] = g->Edge[p2][1] = 0;
g->NumEdges--; //更新边数
}
//删除顶点
void RemoveVertex(GraphMtx *g, T v)
{
//获取顶点的位置
int p = GetVertexPos(g,v);
if(p == -1)
return;
//释放顶点
int numedges = 0;
for(int i=p; i<g->NumVertices-1; ++i)
{
//将要释放顶点之后的顶点逐一前移
g->VerticesList[i] = g->VerticesList[i+1];
}
//统计与要删除顶点相连的边条数
for(i=0; i<g->NumVertices; ++i)
{
if(g->Edge[p][i] != 0)
{
numedges++;
}
}
//删除与释放顶点相连的边（更改存放边信息的矩阵）
for(i=p; i<g->NumVertices-1; ++i)
{
//将要删除行之后的行逐一向前移动一行
for(int j=0; j<g->NumVertices; ++j)
{
g->Edge[i][j] = g->Edge[i+1][j];
}
}
for(i=p; i<g->NumVertices; ++i)//删除列
{
//将要删除列之后的列逐一向前移动一列
for(int j=0; j<g->NumVertices; ++j)
{
g->Edge[j][i] = g->Edge[j][i+1];
}
}
g->NumVertices--;
g->NumEdges -= numedges;
}
//销毁图
void DestroyGraph(GraphMtx *g)
{
//释放顶点
free(g->VerticesList);
g->VerticesList = NULL;
//释放边存储结构的列
for(int i=0; i<g->NumVertices; ++i)
{
free(g->Edge[i]);
}
free(g->Edge);//释放存放行指针的空间
g->Edge = NULL;
g->MaxVertices = g->NumEdges = g->NumVertices = 0;
}
//获取v第一个邻接顶点
int GetFirstNeighbor(GraphMtx *g, T v)
{
//获取顶点v所在位置
int p = GetVertexPos(g,v);
if(p == -1)
return -1;
//对顶点进行搜索，看那个顶点与v相连
for(int i=0; i<g->NumVertices; ++i)
{
//判断是否，找到
if(g->Edge[p][i] == 1)
return i; //找到即返回
}
return -1;
}
//获取下一个邻接顶点：获取顶点v的邻接顶点（该邻接点的顺序在邻接点w之后）
int GetNextNeighbor(GraphMtx *g, T v, T w)
{
//获取v和w所在位置
int pv = GetVertexPos(g,v);
int pw = GetVertexPos(g,w);
if(pv==-1 || pw==-1)
return -1;
//从v的邻接顶点w的位置向后搜索，找到第一个与v相邻的顶点，即所求
for(int i=pw+1; i<g->NumVertices; ++i)
{
if(g->Edge[pv][i] == 1)
return i;
}
return -1;
}
//获取边的权重
E GetWeight(GraphMtx *g, int v1, int v2)
{
if(v1==-1 || v2==-1)
return MAX_COST;
return g->Edge[v1][v2];
}
///
//Kruskal
//边的比较规则：权值大就代表边大
int cmp(const void*a, const void *b)
{
return (*(Edge*)a).cost - (*(Edge*)b).cost;
}
//判断编号为i、j对应的顶点是否同在father集合中(就是查找i、j顶点在father中是否有相同父顶点)
bool Is_same(int *father, int i, int j)
{
//查找顶点i的父顶点
while(father[i] != i)
{
i = father[i];
}
//查找顶点j的父顶点
while(father[j] != j)
{
j = father[j];
}
//判断i、j两个顶点的父顶点是否相同
return i==j;
}
//将边的两个顶点i、j在father中进行标注
void Mark_same(int *father, int i, int j)
{
//查找顶点i的父顶点
while(father[i] != i)
{
i = father[i];
}
//查找顶点j的父顶点
while(father[j] != j)
{
j = father[j];
}
//合并：
father[j] = i;
}
//使用Kruskal算法获取最小生成树
void MinSpanTree_Kruskal(GraphMtx *g)
{
//申请存放边的空间（根据无向图的对称性只要存放邻接矩阵上三角就可以）
int n = g->NumVertices;
Edge *edge = (Edge *)malloc(sizeof(Edge) * (n*(n-1)/2));
assert(edge != NULL);
//获取邻接矩阵中的边（查找邻接矩阵上三角就可以）
int k = 0;
for(int i=0; i<n; ++i)
{
for(int j=i; j<n; ++j)
{
if(g->Edge[i][j]!=0 && g->Edge[i][j]!=MAX_COST)
{
edge[k].x = i;
edge[k].y = j;
edge[k].cost = g->Edge[i][j];
k++;
}
}
}
int v1,v2;
//将各个边根据边的排序规则（权值越大边越大）排序，升序
qsort(edge,k,sizeof(Edge),cmp);
//初始化father数组，用来标记边的两个顶点是否在相同集合
int *father = (int*)malloc(sizeof(int) * n);
assert(father != NULL);
for(i=0; i<n; ++i)
{
father[i] = i;//顶点i的父顶点为i
}
for(i=0; i<n; ++i)
{
//判断边的两个顶点是否在相同集合，如果在相同集合说明该边不能进行连接，会形成闭环
if(!Is_same(father,edge[i].x,edge[i].y))
{
//不在同一集合，将边加入，并将边在father中进行标注
//由于边根据权值进行升序排列，所以只需要按照顺序取出就可以
v1 = edge[i].x;
v2 = edge[i].y;
printf("%c-->%c : %d\n",g->VerticesList[v1],g->VerticesList[v2],edge[i].cost);
Mark_same(father,edge[i].x,edge[i].y);
}
}
}
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
6
0- 0
已为社区贡献3条内容
所有评论(0)