C语言实现最小生成树构造算法

最小生成树

最小生成树(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] < min && lowcost[j] != 0)

{

min = lowcost[j];//找出权值最短的路径长度

minid = j; //找出最小的ID

}

}

printf("V%d-V%d=%d\n",mst[minid],minid,min);

sum += min;//求和

lowcost[minid] = 0;//该处最短路径置为0

for (j = 2; j <= n; j++)

{

if (graph[minid][j] < lowcost[j])//对这一点直达的顶点进行路径更新

{

lowcost[j] = graph[minid][j];

mst[j] = minid;

}

}

}

printf("最小权值之和=%d\n",sum);

}

具体代码如下:

#include<stdio.h>

#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] < min && lowcost[j] != 0)

{

min = lowcost[j];//找出权值最短的路径长度

minid = j; //找出最小的ID

}

}

printf("V%d-V%d=%d\n",mst[minid],minid,min);

sum += min;//求和

lowcost[minid] = 0;//该处最短路径置为0

for (j = 2; j <= n; j++)

{

if (graph[minid][j] < lowcost[j])//对这一点直达的顶点进行路径更新

{

lowcost[j] = graph[minid][j];

mst[j] = minid;

}

}

}

printf("最小权值之和=%d\n",sum);

}

int main()

{

int i, j, k, m, n;

int x, y, cost;

//freopen("1.txt","r",stdin);//文件输入

scanf("%d%d",&m,&n);//m=顶点的个数,n=边的个数

for (i = 1; i <= m; i++)//初始化图

{

for (j = 1; j <= m; j++)

{

graph[i][j] = MAXCOST;

}

}

for (k = 1; k <= n; k++)

{

scanf("%d%d%d",&i,&j,&cost);

graph[i][j] = cost;

graph[j][i] = cost;

}

prim(graph, m);

return 0;

}

编译运行结果:

kruskal(克鲁斯卡尔)算法

时间复杂度:O(NlogN)(N为边数)

kruskal算法又称“加边法”,用于边数较少的稀疏图

方法:每次找图中权值最小的边,将边连接的两个顶点加入最小生成树集合中

注意:相同权值任选其中一个即可,但是不允许出现闭合回路的情况。

代码部分通过以下步骤可以得到最小生成树:

1.初始化:

构建边的结构体,包括起始顶点、终止顶点,边的权值

借用一个辅助数组vset[i]用来判断某边是否加入了最小生成树集合

#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<e)//生成的边数小于e时继续循环

{

m1=E[j].vex1;

m2=E[j].vex2;//取一条边的两个邻接点

sn1=vset[m1];

sn2=vset[m2];

//分别得到两个顶点所属的集合编号

if(sn1!=sn2)//两顶点分属于不同的集合,该边是最小生成树的一条边

{//防止出现闭合回路

printf("V%d-V%d=%d\n",m1,m2,E[j].weight);

sum+=E[j].weight;

k++; //生成边数增加

if(k>=n)

break;

for(i=1;i<=n;i++) //两个集合统一编号

if (vset[i]==sn2) //集合编号为sn2的改为sn1

vset[i]=sn1;

}

j++; //扫描下一条边

}

printf("最小权值之和=%d\n",sum);

}

具体算法实现:

#include <stdio.h>

#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<e)//生成的边数小于e时继续循环

{

m1=E[j].vex1;

m2=E[j].vex2;//取一条边的两个邻接点

sn1=vset[m1];

sn2=vset[m2];

//分别得到两个顶点所属的集合编号

if(sn1!=sn2)//两顶点分属于不同的集合,该边是最小生成树的一条边

{//防止出现闭合回路

printf("V%d-V%d=%d\n",m1,m2,E[j].weight);

sum+=E[j].weight;

k++; //生成边数增加

if(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<high && arr[high].weight>=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<end)

{

pos=fun(arr,start,end);

quick_sort(arr,start,pos-1);

quick_sort(arr,pos+1,end);

}

}

int main()

{

Edge E[MAXE];

int nume,numn;

//freopen("1.txt","r",stdin);//文件输入

printf("输入顶数和边数:\n");

scanf("%d%d",&numn,&nume);

for(int i=0;i<nume;i++)

scanf("%d%d%d",&E[i].vex1,&E[i].vex2,&E[i].weight);

quick_sort(E,0,nume-1);

kruskal(E,numn,nume);

}

编译运行结果:

以上是 C语言实现最小生成树构造算法 的全部内容, 来源链接: utcz.com/z/328692.html

回到顶部