最小生成树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;i<n;i++) vset[i]=i; //初始化辅助数组
k=1; //k表示当前构造最小生成树的第几条边,初值为1
j=0; //E中边的下标,初值为0
while (k<n) //生成的边数小于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;i<n;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;i<n;i++) //给lowcost[]和closest[]置初值
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<n;i++) //找出n-1个顶点
{
min=INF;
for (j=0;j<n;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;j<n;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语言 最小生成树问题

普里姆算法描述：
假设 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中的顶点。

③ C语言算法求解：对任意给定的网络（顶点数和边数自定），设计算法生成它的最小生成树。

上一个图和代码：

图1为要创建的图，图2为对应的最小生成树

代码为：

//图论之最小生成树：prim算法实现

#include"stdio.h"

#include"malloc.h"

//声明

voidoutput(structadjacentlisthead*alh,intmapsize);

structadjacentlistson//邻接表项结构体

{

intsonelement;

intquanvalue;

structadjacentlistson*next;

};

structadjacentlisthead//邻接表头结构体

{

charflag;

intelement;

intcurqvalue;

structadjacentlisthead*previous;

structadjacentlistson*startson;

};

structadjacentlisthead*mapinitialnize(intmapsize)//初始化图函数

{

structadjacentlisthead*alh=NULL;

structadjacentlistson*newnode=NULL;

inti,x,y,z;

alh=malloc(sizeof(structadjacentlisthead)*mapsize);

if(alh==NULL)

returnNULL;

for(i=0;i<mapsize;i++)

{

alh[i].flag=0;

alh[i].element=i+1;

alh[i].curqvalue=0;

alh[i].previous=NULL;

alh[i].startson=NULL;

}

scanf("%d%d%d",&x,&y,&z);

while(x&&y)//直到输入的x,y中至少有一个0为止

{

newnode=malloc(sizeof(structadjacentlistson));

newnode->sonelement=y;

newnode->quanvalue=z;

newnode->next=alh[x-1].startson;

alh[x-1].startson=newnode;

scanf("%d%d%d",&x,&y,&z);

}

returnalh;

}

intfindminnode(structadjacentlisthead*alh,intmapsize)//找到最小权值对应的结点

{

inti,minvalue=~(1<<(sizeof(int)*8-1)),minplace=0;

for(i=0;i<mapsize;i++)

{

if(alh[i].flag==0&&alh[i].curqvalue!=0)

{

if(alh[i].curqvalue<minvalue)

{

minvalue=alh[i].curqvalue;

minplace=i+1;//

}

}

}

returnminplace;

}

voidfindthemintree(structadjacentlisthead*alh,intstartplace,intmapsize)//找到最小生成树

{

structadjacentlistson*alstmp=NULL;

intcurplace=startplace;

while(curplace)

{

alstmp=alh[curplace-1].startson;

alh[curplace-1].flag=1;//正在访问

while(alstmp)

{

if(alh[alstmp->sonelement-1].flag==0)

{

if(alh[alstmp->sonelement-1].curqvalue==0||(alh[alstmp->sonelement-1].curqvalue>alstmp->quanvalue))//比较方法与有权图有一点不同

{

alh[alstmp->sonelement-1].curqvalue=alstmp->quanvalue;

alh[alstmp->sonelement-1].previous=&alh[curplace-1];

}

}

alstmp=alstmp->next;

}

curplace=findminnode(alh,mapsize);//通过函数找到最小的一个结点

}

}

voidoutput(structadjacentlisthead*alh,intmapsize)

{

inti;

for(i=0;i<mapsize;i++)

{

printf("%d点的权值为：%d ",i+1,alh[i].curqvalue);

}

printf("................................................... ");

}

intmain()

{

structadjacentlisthead*alh=NULL;

intmapsize=7,startplace=1;

alh=mapinitialnize(mapsize);

findthemintree(alh,startplace,mapsize);

output(alh,mapsize);

}

输入数据对应第一图：

122

134

141

212

243

2510

314

342

365

411

423

432

457

468

474

5210

547

576

635

648

671

744

756

761

000

④ 用prim算法求最小生成树:c语言

把main函数改成：

main(){
GraphMatrix graph = {
"abcd",

{{7,8,Max,15},{12,100,6,20},{Max,100,4,13},{Max,4,8,10}},

};

Edge mst[Max];
int i,j;

prim(graph,mst);
for(j=0;j<Max;j++)
{
printf("%c\t",mst[j].stop_vex);
printf("%c\t",mst[j].start_vex);
printf("%d\n",mst[j].weight);
}
}

还有GraphMatrix结构体里的vexs数组最好定义为vexs[VN+1]给字符串末尾的‘\0'留地方。

⑤ 求最小生成树 利用Kruskal算法求图G的一棵最小生成树T，用c语言

#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 并查集存储结构
// Tags: 值为-1则表示为根节点
struct DisjointSet
{
int *arr;// 值为父节点下标
int number;// arr元素个数
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化并查集结构
// Input: number - 元素的个数
// Output:s - number个元素自成一集的并查集
void InitSet(DisjointSet &s, int number)
{
s.number = number;
s.arr = new int[number];
memset(s.arr, -1, sizeof(int) * number);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 删除并查集结构
// Input: s - 并查集存储结构
// Output:s - 回收内存后的结构
void FreeSet(DisjointSet &s)
{
if (s.arr)
{
delete []s.arr;
s.number = 0;
}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 获得某个结点的根节点
// Input: s - 并查集; index - 结点下标
// Output: return - 根节点下标
int GetRoot(DisjointSet &s, int index)
{
while (s.arr[index] != -1)
index = s.arr[index];

return index;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 合并index1和index2所在的两个集合
// Input: index1 - 结点1下标, index2 - 结点2下标
// Output: s - 并查集
void Union(DisjointSet &s, int index1, int index2)
{
int root1 = GetRoot(s, index1);
int root2 = GetRoot(s, index2);

s.arr[root1] = root2;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 判断两个结点是否在同一个集合中
// Input: s - 并查集, index1 - 结点1下标, index2 - 结点2下标
// Output: return - true: 在 false: 不在
bool Find(DisjointSet &s, int index1, int index2)
{
return GetRoot(s, index1) == GetRoot(s, index2);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 图的邻接矩阵
struct Graph
{
int **value;// 权值,-1表示无法到达
int number;
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化一个图
// Input: g - 图的存储结构, number - 结点个数
// Output: g - 图
void InitGraph(Graph &g, int number)
{
int i = 0;

g.value = new int *[number];
for (i = 0; i < number; i++)
g.value[i] = new int[number];

g.number = number;
memset(*g.value, -1, sizeof(int) * number * number);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 回收一个图
// Input: g - 图, number - 结点个数
// Output: g - 图的存储结构
void FreeGraph(Graph &g)
{
int i = 0;

for (i = 0; i < g.number; i++)
delete []g.value[i];

delete []g.value;

g.value = 0;
g.number = 0;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 为图在a，b间添加一条边
// Input:e1, e2 - 两个结点, value - 权值
// Output: graph - 加边后的图
void AddEdge(Graph &graph, int e1, int e2, int value)
{
graph.value[e1][e2] =value;
graph.value[e2][e1] = value;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 显示一条边
struct OneEdge
{
OneEdge(int _a = 0, int _b = 0, int _value = 0):
a(_a), b(_b), value(_value){}

int a, b;// 边的两个结点
int value; // 边的权值
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 根据权值判断两个边的大小
// Tags: 由于priority_queue是最大堆，所以这里小于号变成大于号，从而使priority_queue变成最小堆
bool operator <(OneEdge e1, OneEdge e2)
{
if (e1.value > e2.value) return true;
else return false;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 用户输入图的边
// Input: n - 加边的个数
// Output: graph - 加边后的图
// Tags: Console下用户输入点对(a, b, v)
void InputEdge(Graph &graph, int n)
{
int i = 0, a, b, v;
for (i = 0; i < n; i++)
{
scanf("%d %d %d", &a, &b, &v);
AddEdge(graph, a, b, v);
}
}

int main()
{
const int NODE_NUMBER = 6;
const int EDGE_NUMBER = 9;

Graph graph;// 图
DisjointSet set;// 并查集
priority_queue<OneEdge> edge;// 2叉堆

InitGraph(graph, NODE_NUMBER);// 初始化图
InputEdge(graph, EDGE_NUMBER);
InitSet(set, NODE_NUMBER); // 初始化并查集

int i = 0, j = 0;// 初始化堆
for (i = 0; i < NODE_NUMBER; i++)
for (j = i; j < NODE_NUMBER; j++)
if (graph.value[i][j] > 0)
edge.push(OneEdge(i, j, graph.value[i][j]));

int min_pay = 0;// 最小耗费值
int add_num = 0;// 已经添加了几个边
OneEdge min_value_edge;// 当前权值最小边

while (add_num < NODE_NUMBER - 1)
{
min_value_edge = edge.top();
// 这里是因为了STL中2叉堆的结构中有一个缓冲区
// 需要将缓冲区中的每一个元素弹出来
if(min_value_edge.value > 0 && !Find(set, min_value_edge.a, min_value_edge.b))
{
Union(set, min_value_edge.a, min_value_edge.b);
min_pay += min_value_edge.value;
add_num++;
}
edge.pop();
}

printf("%d", min_pay);
return 0;
}

这个是c++语言的，最小权值存储在min_pay中，树存储在并查集set中，且在获取最小权值路径的时候用了STL中的2叉堆，算法复杂度为O(|V| * lgE)
不知是否满足您的要求

⑥ C语言数据结构的最小生成树不是唯一的吗

生成树是一个包含n个结点的连通图G的一个子图。该子图必须包含G中的所有n个结点以及G中的n-1条边并且保持连通性。
最小生成树是G的所有可能的生成树中，n-1条边的权值总和最小的那一个（或多个）生成树。

⑦ C语言（关于图最小生成树方法）

/*
邻接矩阵存储图
测试数据
610
126
131
145
235
253
345
356
364
462
566
*/

#include<stdio.h>
#include<limits.h>
#defineN100

intp[N],key[N],tb[N][N];

voidprim(intv,intn)
{
inti,j;
intmin;

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];
}
}

intmain()
{
intn,m;
inti,j;
intu,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("
");
}
return0;
}

⑧ C语言，最小生成树代码，求修改

#include<stdlib.h>
#include<stdio.h>
#defineMaxVertexNum10
#defineMaxEdgeNum45

typedefstructEdgeNode
{
	intFrontVertex;
	intRearVertex;
	intWeight;
}EdgeSet[MaxEdgeNum];

typedefintAdjmatrix[MaxVertexNum][MaxVertexNum];
intPrim();
voidInsitAdj_Prim(AdjmatrixGA);
voidSetAdj_Prim(AdjmatrixGA,intn);
voidFun_Prim(AdjmatrixGA,EdgeSetGT,intn);
voidDisplay_Prim(EdgeSetGT,intn);
voidInsit_Prim(EdgeSetGT,intn,AdjmatrixGA);
voidInsitAdj_Prim(AdjmatrixGA)
{
	inti,j;
	for(i=0;i<MaxVertexNum;i++)
	{
		for(j=0;j<MaxVertexNum;j++)
		{
			GA[i][j]=20000;
		}
	}
}

voidSetAdj_Prim(AdjmatrixGA,intn)
{
	inti,j,y,w;
	for(i=0;i<=n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			y=i+1;
			w=j+1;
			printf("第%d个点到第%d个点的权值:",y,w);
			scanf("%d",&GA[i][j]);
		}
	}
	for(i=0;i<=n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			GA[j][i]=GA[i][j];
		}
	}
}

voidFun_Prim(AdjmatrixGA,EdgeSetGT,intn)
{
	inti,j,min=10000,m;
	for(i=0;i<n-1;i++)
	{
		m=i;
		for(j=i;j<n-1;j++)
		{
			if(GT[j].Weight<min)
			{
				min=GT[j].Weight;
				m=j;
			}
		}
		EdgeNodetemp=GT[i];
		GT[i]=GT[m];
		GT[m]=temp;
		intk=GT[m].RearVertex;
		for(j=i;j<n-1;j++)
		{
			intt=GT[j].RearVertex;
			intw=GA[k][t];
			if(w<GT[j].Weight)
			{
				GT[j].Weight=w;
				GT[j].FrontVertex=k;
			}
		}
	}
}

voidDisplay_Prim(EdgeSetGT,intn)
{
	inti;
	printf("保留如下弧
");
	for(i=0;i<n-1;i++)
	{
		inte,r;
		e=GT[i].FrontVertex+1;
		r=GT[i].RearVertex+1;
		printf("第%d个结点到第%d个结点！
",e,r);
	}
	printf("可得到最小生成树");
}

voidInsit_Prim(EdgeSetGT,intn,AdjmatrixGA)
{
	inti;
	for(i=0;i<n-1;i++)
	{
		GT[i].FrontVertex=0;
		GT[i].RearVertex=i+1;
		GT[i].Weight=GA[0][i+1];
	}
}

intPrim()
{
	intn;
	printf("结点数
");
	scanf("%d",&n);
	EdgeSetGT;
	AdjmatrixGA;
	InsitAdj_Prim(GA);
	SetAdj_Prim(GA,n);
	Insit_Prim(GT,n,GA);
	Fun_Prim(GA,GT,n);
	Display_Prim(GT,n);
	return0;
}

intmain(){
	Prim();
}

⑨ 用prim算法的思想，用C语言编写出最小生成树的方法的代码

PrimMST(G，T，r){
//求图G的以r为根的MST，结果放在T=(U，TE)中
InitCandidateSet(…)；//初始化：设置初始的轻边候选集，并置T=({r}，￠)
for(k=0；k<n-1；k++){
//求T的n-1条树边
(u，v)=SelectLiShtEdge(…)；//选取轻边(u，v)；
T←T∪{(u，v)}；//扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U
ModifyCandidateSet(…)；
//根据新红点v调整候选轻边集
}
}