最小生成树
最小生成树(minimum spanning tree )是用n个顶点、n-1个边连接一个连接图，使权重最小的结构。
可以在Prim (预)算法或kruskal (pbdz )算法中确定最小生成树。
通过以下赋权连通图为例说明了这两种算法的实现。
注：由于测试输入数据较多，程序可以采用文件输入
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 MAXCOST0x7fffffff
int graph[MAX][MAX]；
voidprim(intgraph[][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 )
{
最小=最大；
minid=0；
for(j=2； j=n； j )
{
if(lowcost[j]minlowcost[j]！=0)
{
min=lowcost[j]； //找出权重最短的路径长度
minid=j； //找到最小的ID
}
}
printf(v%d-v%d=%dn )、mst[minid]、minid、min )；
sum =min； //合计
lowcost[minid]=0； //这里的最短路径为0
for(j=2； j=n； j )
{
graph [ minid ] [ j ] low cost [ j ] )//将此点直接更新为顶点
{
lowcost[j]=graph[minid][j]；
mst[j]=minid；
}
}
}
printf ('最小权重之和=%dn '，sum )；
}
具体代码如下。
#包含
#define MAX 100
#define MAXCOST0x7fffffff
int graph[MAX][MAX]；
voidprim(intgraph[][max]，int n ) )。
{
int lowcost[MAX]；
int mst[MAX]；
int i，j，min，minid，sum=0；
for(I=2； i=n； I )
{
/p>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=%dn",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("最小权值之和=%dn",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(pbdz)算法
时间复杂度：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算法需要按照权值大小顺序取边，所以应该事先对图按权值升序，这里我采用了快速排序算法，具体算法可以参照
while(k
{
m1=E[j].vex1;
m2=E[j].vex2;//取一条边的两个邻接点
sn1=vset[m1];
sn2=vset[m2];
//分别得到两个顶点所属的集合编号
if(sn1!=sn2)//两顶点分属于不同的集合，该边是最小生成树的一条边
{//防止出现闭合回路
printf("V%d-V%d=%dn",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("最小权值之和=%dn",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
{
m1=E[j].vex1;
m2=E[j].vex2;//取一条边的两个邻接点
sn1=vset[m1];
sn2=vset[m2];
//分别得到两个顶点所属的集合编号
if(sn1!=sn2)//两顶点分属于不同的集合，该边是最小生成树的一条边
{//防止出现闭合回路
printf("V%d-V%d=%dn",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("最小权值之和=%dn",sum);
}
int fun(Edge arr[],int low,int high)
{
int key;
Edge lowx;
lowx=arr[low];
key=arr[low].weight;
while(low
{
while(low=key)
high--;
if(low
arr[low++]=arr[high];
while(low
low++;
if(low
arr[high--]=arr[low];
}
arr[low]=lowx;
return low;
}
void quick_sort(Edge arr[],int start,int end)
{
int pos;
if(start
{
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
scanf("%d%d%d",&E[i].vex1,&E[i].vex2,&E[i].weight);
quick_sort(E,0,nume-1);
kruskal(E,numn,nume);
}
编译运行结果：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。