这篇文章主要为大家详细介绍了C语言实现最小生成树构造算法，利用Prim算法或kruskal算法求解，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
最小生成树
最小生成树（minimum spanning tree）是由n个顶点，n-1条边，将一个连通图连接起来，且使权值最小的结构。
最小生成树可以用Prim（普里姆）算法或kruskal（克鲁斯卡尔）算法求出。
我们将以下面的带权连通图为例讲解这两种算法的实现：
注：由于测试输入数据较多，程序可以采用文件输入
Prim（普里姆）算法
时间复杂度：O（N^2）（N为顶点数）
prim算法又称“加点法”，用于边数较多的带权无向连通图
方法：每次找与之连线权值最小的顶点，将该点加入最小生成树集合中
注意：相同权值任选其中一个即可，但是不允许出现闭合回路的情况。
代码部分通过以下步骤可以得到最小生成树：
1.初始化：
lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0表示i点加入了MST。
mst[i]:表示对应lowcost[i]的起点，当mst[i]=0表示起点i加入MST。
由于我们规定最开始的顶点是1，所以lowcost[1]=0，MST[1]=0。即只需要对2~n进行初始化即可。
#define MAX 100 #define MAXCOST 0x7fffffff int graph[MAX][MAX]; void prim(int graph[][MAX], int n) { int lowcost[MAX]; int mst[MAX]; int i, j, min, minid, sum = 0; for (i = 2; i <= n; i++) { lowcost[i] = graph[1][i];//lowcost存放顶点1可达点的路径长度 mst[i] = 1;//初始化以1位起始点 } mst[1] = 0;
2.查找最小权值及路径更新
定义一个最小权值min和一个最小顶点ID minid，通过循环查找出min和minid，另外由于规定了某一顶点如果被连入，则lowcost[i]=0，所以不需要担心重复点问题。所以找出的终点minid在MST[i]中可以找到对应起点，min为权值，直接输出即可。
我们连入了一个新的顶点，自然需要对这一点可达的路径及权值进行更新，所以循环中还应该包括路径更新的代码。
for (i = 2; i <= n; i++) { min = MAXCOST; minid = 0; for (j = 2; j <= n; j++) { if (lowcost[j] </div><p>具体代码如下：</p><div class="gaodaimacode"><pre class="prettyprint linenums"> #include #define MAX 100 #define MAXCOST 0x7fffffff int graph[MAX][MAX]; void prim(int graph[][MAX], int n) { int lowcost[MAX]; int mst[MAX]; int i, j, min, minid, sum = 0; for (i = 2; i <= n; i++) { lowcost[i] = graph[1][i];//lowcost存放顶点1可达点的路径长度 mst[i] = 1;//初始化以1位起始点 } mst[1] = 0; for (i = 2; i <= n; i++) { min = MAXCOST; minid = 0; for (j = 2; j <= n; j++) { if (lowcost[j] </div><p>编译运行结果：</p><p style="text-align: center"></p><p><strong>kruskal（克鲁斯卡尔）算法 </strong></p><p>时间复杂度：O（NlogN）（N为边数）<br /> kruskal算法又称<span style="color: #800000"><strong>“加边法”，</strong></span>用于边数较少的稀疏图 <br /> 方法：每次找图中权值最小的边，将边连接的两个顶点加<div style="color:transparent">来源gaodai.ma#com搞##代!^码网</div>入最小生成树集合中 <br /> 注意：相同权值任选其中一个即可，但是<strong><span style="color: #800000">不允许出现闭合回路</span></strong>的情况。</p><p style="text-align: center"></p><p>代码部分通过以下步骤可以得到最小生成树：</p><p>1.初始化：</p><p>构建边的结构体，包括起始顶点、终止顶点，边的权值 <br /> 借用一个辅助数组vset[i]用来判断某边是否加入了最小生成树集合</p><div class="gaodaimacode"><pre class="prettyprint linenums"> #define MAXE 100 #define MAXV 100 typedef struct{ int vex1; //边的起始顶点 int vex2; //边的终止顶点 int weight; //边的权值 }Edge; void kruskal(Edge E[],int n,int e) { int i,j,m1,m2,sn1,sn2,k,sum=0; int vset[n+1]; for(i=1;i<=n;i++) //初始化辅助数组 vset[i]=i; k=1;//表示当前构造最小生成树的第k条边，初值为1 j=0;//E中边的下标，初值为0
2.取边和辅助集合更新
按照排好的顺序依次取边，若不属于同一集合则将其加入最小生成树集合，每当加入新的边，所连接的两个点即纳入最小生成树集合，为避免重复添加，需要进行辅助集合更新
注：由于kruskal算法需要按照权值大小顺序取边，所以应该事先对图按权值升序，这里我采用了快速排序算法，具体算法可以参照快速排序（C语言）
while(k=n) break; for(i=1;i<=n;i++) //两个集合统一编号 if (vset[i]==sn2) //集合编号为sn2的改为sn1 vset[i]=sn1; } j++; //扫描下一条边 } printf("最小权值之和=%d\n",sum); }
具体算法实现：
#include #define MAXE 100 #define MAXV 100 typedef struct{ int vex1; //边的起始顶点 int vex2; //边的终止顶点 int weight; //边的权值 }Edge; void kruskal(Edge E[],int n,int e) { int i,j,m1,m2,sn1,sn2,k,sum=0; int vset[n+1]; for(i=1;i<=n;i++) //初始化辅助数组 vset[i]=i; k=1;//表示当前构造最小生成树的第k条边，初值为1 j=0;//E中边的下标，初值为0 while(k=n) break; for(i=1;i<=n;i++) //两个集合统一编号 if (vset[i]==sn2) //集合编号为sn2的改为sn1 vset[i]=sn1; } j++; //扫描下一条边 } printf("最小权值之和=%d\n",sum); } int fun(Edge arr[],int low,int high) { int key; Edge lowx; lowx=arr[low]; key=arr[low].weight; while(low<high) { while(low=key) high--; if(low<high) arr[low++]=arr[high]; while(low<high && arr[low].weight<=key) low++; if(low<high) arr[high--]=arr[low]; } arr[low]=lowx; return low; void quick_sort(edge arr[],int start,int end) { int pos; if(start编译运行结果：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持gaodaima搞代码网。
以上就是C语言实现最小生成树构造算法的详细内容，更多请关注gaodaima搞代码网其它相关文章！
转载请注明原文链接：C语言实现最小生成树构造算法
