本篇文章给大家谈谈c语言最小生成树原来，以及最小生成树csdn对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
1、急！数据结构最小生成树prim算法C语言实现2、C语言（关于图最小生成树方法）3、求救~！C语言 最小生成树问题4、用prim算法的思想，用C语言编写出最小生成树的方法的代码
急！数据结构最小生成树prim算法C语言实现
Kruskal算法：
void
Kruskal(Edge
E[],int
n,int
e)
{
int
i,j,m1,m2,sn1,sn2,k;
int
vset[MAXE];
for
(i=0;in;i++)
vset[i]=i;
//初始化辅助数组
k=1;
//k表示当前构造最小生成树的第几条边,初值为1
j=0;
//E中边的下标,初值为0
while
(kn)
//生成的边数小于n时循环
{
m1=E[j].u;m2=E[j].v;
//取一条边的头尾顶点
sn1=vset[m1];sn2=vset[m2];
//分别得到两个顶点所属的集合编号
if
(sn1!=sn2)
//两顶点属于不同的集合,该边是最小生成树的一条边
{
printf(“
(%d,%d):%d/n”,m1,m2,E[j].w);
k++;
//生成边数增1
for
(i=0;in;i++)
//两个集合统一编号
if
(vset[i]==sn2)
//集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++;
//扫描下一条边
}
}
Prim算法：
void
prim(MGraph
g,int
v)
{
int
lowcost[MAXV],min,n=g.vexnum;
int
closest[MAXV],i,j,k;
for
(i=0;in;i++)
//给lowcost[]和closest[]置初值
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for
(i=1;in;i++)
//找出n-1个顶点
{
min=INF;
for
(j=0;jn;j++)
//在(V-U)中找出离U最近的顶点k
if
(lowcost[j]!=0
lowcost[j]min)
{
min=lowcost[j];k=j;
}
printf(“
边(%d,%d)权为:%d/n”,closest[k],k,min);
lowcost[k]=0;
//标记k已经加入U
for
(j=0;jn;j++)
//修改数组lowcost和closest
if
(g.edges[k][j]!=0
g.edges[k][j]lowcost[j])
{
lowcost[j]=g.edges[k][j];closest[j]=k;
}
}
}
C语言（关于图最小生成树方法）
/*
邻接矩阵存储图
测试数据
6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
*/
#include stdio.h
#include limits.h
#define N 100
int p[N], key[N], tb[N][N];
void prim(int v, int n)
{
int i, j;
int min;
for (i = 1; i = n; i++)
{
p[i] = v;
key[i] = tb[v][i];
}
key[v] = 0;
for (i = 2; i = n; i++)
{
min = INT_MAX;
for (j = 1; j = n; j++)
if (key[j] 0 key[j] min)
{
v = j;
min = key[j];
}
printf(“%d%d “, p[v], v);
key[v] = 0;
for (j = 1; j = n; j++)
if (tb[v][j] key[j])
p[j] = v, key[j] = tb[v][j];
}
}
int main()
{
int n, m;
int i, j;
int u, v, w;
while (scanf(“%d%d”, n, m))
{
for(i = 1; i = n; i++)
{
for (j = 1; j = n; j++)
tb[i][j] = INT_MAX;
}
while (m–)
{
scanf(“%d%d%d”, u, v, w);
tb[u][v] = tb[v][u] = w;
}
prim(1, n);
printf(“\n”);
}
return 0;
}
求救~！C语言 最小生成树问题
普里姆算法描述：
假设 N＝(V，E)是一个带权图，TE是N上最小生成树中边的集合。算法从U＝{u0}(u0∈V)，TE＝{}开始，重复执行下述操作：在所有u∈U，v∈V-U的边(u，v) ∈E中找一条权值最小的边(u，v)并入集合TE，同时v并入U，直至U＝V为止。此时TE中必有n-1边，则T＝(V，{TE})为N的最小生成树。
为实现这个算法需附设一个辅助数组 closedge，以记录从U到V-U具有最小代价的边。对每个顶点vi∈V-U，在辅助数组中存在一个相应分量closedge[I-1]，它包括两个域，其中lowcost存储该边上的权：显然， closedge[I-1]．Lowcost＝Min{cost(u，vi)|uEU} vex域存储该边依附的在U中的顶点。
用prim算法的思想，用C语言编写出最小生成树的方法的代码
PrimMST(G，T，r){
//求图G的以r为根的MST，结果放在T=(U，TE)中
InitCandidateSet(…)；//初始化：设置初始的轻边候选集，并置T=({r}，￠)
for(k=0；kn-1；k++){
//求T的n-1条树边
(u，v)=SelectLiShtEdge(…)；//选取轻边(u，v)；
T←T∪{(u，v)}；//扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U
ModifyCandidateSet(…)；
//根据新红点v调整候选轻边集
}
}
c语言最小生成树原来的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于最小生成树csdn、c语言最小生成树原来的信息别忘了在本站进行查找喔。
微信扫一扫 
支付宝扫一扫 
