最小生成樹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調整候選輕邊集
}
}