最小生成樹的prim演算法代碼

❶ 用普里姆演算法求最小生成樹（C++）

求最小生成樹的譜里姆演算法
#include <iostream>
using namespace std;

const int n=6;
const int e=10;
class edgeset
{public :
int front;
int end;
int weight;};

class tree
{public :
int s[n+1][n+1];
edgeset ct[n+1];

void prim(tree &t)
{
int i,j,k,min,t1,m,w;
for(i=1;i<n;i++)
{t.ct[i].front=1;
t.ct[i].end=i+1;
t.ct[i].weight=t.s[1][i+1];}

for(k=2;k<=n;k++)
{min=32767;
m=k-1;

for(j=k-1;j<n;j++)
if(t.ct[j].weight<min)
{min=t.ct[j].weight;
m=j;}
edgeset temp=t.ct[k-1];
t.ct[k-1]=t.ct[m];
t.ct[m]=temp;
j=t.ct[k-1].end;
for(i=k;i<n;i++)
{t1=t.ct[i].end;
w=t.s[j][t1];
if(w<t.ct[i].weight)
{t.ct[i].weight=w;
t.ct[i].front=j;}}}}
};

void main ()
{int j,w;tree t;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j)t.s[i][j]=0;
else t.s[i][j]=32767;

for(int k=1;k<=e;k++)
{cout<<"輸入一條邊及邊上的權值 ";
cin>>i>>j>>w;
cout<<endl;
t.s[i][j]=w;
t.s[j][i]=w;}

t.prim(t);
for(i=1;i<n;i++)
{cout<<t.ct[i].front<<" "<<t.ct[i].end<<" "<<t.ct[i].weight<<endl;}
}
我們的實驗上機做了的
運行結果
輸入一條邊及邊上的權值 1 2 6

輸入一條邊及邊上的權值 1 3 1

輸入一條邊及邊上的權值 1 4 6

輸入一條邊及邊上的權值 2 3 5

輸入一條邊及邊上的權值 2 5 3

輸入一條邊及邊上的權值 3 4 7

輸入一條邊及邊上的權值 3 5 5

輸入一條邊及邊上的權值 3 6 4

輸入一條邊及邊上的權值 4 6 2

輸入一條邊及邊上的權值 5 6 6

1 3 1
3 6 4
6 4 2
3 5 5
5 2 3
Press any key to continue
你有的圖不一樣就該頂點和邊就是
const int n=6;
const int e=10;

❷ 關於PRIM演算法求最小生成樹的問題（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;
}

要求出所有的最小生成樹。。貌似有點麻煩。。

❸ 用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調整候選輕邊集
}
}

❹ c++求最小生成樹prim演算法,我搗鼓2天了,真心不會改了,求指導感激不盡啊

你的代碼太亂，給你這個，添加了注釋，容易看懂：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>

usingnamespacestd;

#defineMAX_VERTEX_NUM20
#defineOK1
#defineERROR0
#defineMAX1000
typedefstructArcell
{
	doubleadj;
}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
	charvexs[MAX_VERTEX_NUM];//節點數組
	AdjMatrixarcs;//鄰接矩陣
	intvexnum,arcnum;//圖的當前節點數和弧數
}MGraph;
typedefstructPnode//用於普利姆演算法
{
	charadjvex;//節點
	doublelowcost;//權值
}Pnode,Closedge[MAX_VERTEX_NUM];//記錄頂點集U到V-U的代價最小的邊的輔助數組定義
typedefstructKnode//用於克魯斯卡爾演算法中存儲一條邊及其對應的2個節點
{
	charch1;//節點1
	charch2;//節點2
	doublevalue;//權值
}Knode,Dgevalue[MAX_VERTEX_NUM];
//-------------------------------------------------------------------------------
intCreateUDG(MGraph&G,Dgevalue&dgevalue);
intLocateVex(MGraphG,charch);
intMinimum(MGraphG,Closedgeclosedge);
voidMiniSpanTree_PRIM(MGraphG,charu);
voidSortdge(Dgevalue&dgevalue,MGraphG);
//-------------------------------------------------------------------------------
intCreateUDG(MGraph&G,Dgevalue&dgevalue)//構造無向加權圖的鄰接矩陣
{
	inti,j,k;
	cout<<"請輸入圖中節點個數和邊/弧的條數：";
	cin>>G.vexnum>>G.arcnum;
	cout<<"請輸入節點：";
	for(i=0;i<G.vexnum;++i)
		cin>>G.vexs[i];
	for(i=0;i<G.vexnum;++i)//初始化數組
	{
		for(j=0;j<G.vexnum;++j)
		{
			G.arcs[i][j].adj=MAX;
		}
	}
	cout<<"請輸入一條邊依附的定點及邊的權值："<<endl;
	for(k=0;k<G.arcnum;++k)
	{
		cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;
		i=LocateVex(G,dgevalue[k].ch1);
		j=LocateVex(G,dgevalue[k].ch2);
		G.arcs[i][j].adj=dgevalue[k].value;
		G.arcs[j][i].adj=G.arcs[i][j].adj;
	}
	returnOK;
}
intLocateVex(MGraphG,charch)//確定節點ch在圖G.vexs中的位置
{
	inta;
	for(inti=0;i<G.vexnum;i++)
	{
		if(G.vexs[i]==ch)
			a=i;
	}
	returna;
}
voidMiniSpanTree_PRIM(MGraphG,charu)//普利姆演算法求最小生成樹
{
	inti,j,k;
	Closedgeclosedge;
	k=LocateVex(G,u);
	//將該頂點到其他所有的頂點權值賦值給closedge
	for(j=0;j<G.vexnum;j++)
	{
		if(j!=k)
		{
			closedge[j].adjvex=u;
			closedge[j].lowcost=G.arcs[k][j].adj;
		}
	}
	closedge[k].lowcost=0;
	for(i=1;i<G.vexnum;i++)
	{
		//找到權值最小的頂點，記錄到k
		k=Minimum(G,closedge);
		cout<<"("<<closedge[k].adjvex<<","<<G.vexs[k]<<","<<closedge[k].lowcost<<")"<<endl;
		//清零，方便尋找下一個頂點
		closedge[k].lowcost=0;
		for(j=0;j<G.vexnum;++j)
		{
			//依次比較上個頂點和當前頂點與剩餘頂點的權值，將小的賦值給closedge
			if(G.arcs[k][j].adj<closedge[j].lowcost)
			{
				closedge[j].adjvex=G.vexs[k];
				closedge[j].lowcost=G.arcs[k][j].adj;
			}
		}
	}
}
intMinimum(MGraphG,Closedgeclosedge)//求closedge中權值最小的邊，並返回其頂點在vexs中的位置
{
	inti,j;
	doublek=1000;
	for(i=0;i<G.vexnum;i++)
	{
		if(closedge[i].lowcost!=0&&closedge[i].lowcost<k)
		{
			k=closedge[i].lowcost;
			j=i;
		}
	}
	returnj;
}

voidmain()
{
	inti,j;
	MGraphG;
	charu;
	Dgevaluedgevalue;
	CreateUDG(G,dgevalue);
	cout<<"圖的鄰接矩陣為："<<endl;
	for(i=0;i<G.vexnum;i++)
	{
		for(j=0;j<G.vexnum;j++)
			cout<<G.arcs[i][j].adj<<"";
		cout<<endl;
	}
	cout<<"=============普利姆演算法===============
";
	cout<<"請輸入起始點：";
	cin>>u;
	cout<<"構成最小代價生成樹的邊集為：
";
	MiniSpanTree_PRIM(G,u);
}

❺ 用Prim演算法求最小生成樹

❻ 用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'留地方。

❼ 按prim演算法求最小生成樹

rew

❽ 急！數據結構最小生成樹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;
}
}
}

❾ 利用Prim（普里姆）演算法 構造最小生成樹 程序

演算法同樣是解決最小生成樹的問題。

其演算法為：在這n個點中的相通的邊進行排序，然後不斷地將邊添加到集合中（體現了貪心的演算法特點），在並入集合之前，必須檢查一下這兩點是不是在一個集合當中，這就用到了並查集的知識。直到邊的集合達到了n-1個。

與prim演算法的不同：prim演算法為單源不斷尋找連接的最短邊，向外擴展，即單樹形成森林。而Kruskal演算法則是不斷尋找最短邊然後不斷將集合合並，即多樹形成森林。

復雜度的不同：prim演算法的復雜度是O(n^2),其中n為點的個數。Kruskal演算法的復雜度是O(e*loge)，其中e為邊的個數。兩者各有優劣，在不同的情況下選擇不同的演算法。

Prim演算法用於求無向圖的最小生成樹

設圖G =（V，E），其生成樹的頂點集合為U。

①、把v0放入U。

②、在所有u∈U，v∈V-U的邊(u，v)∈E中找一條最小權值的邊，加入生成樹。

③、把②找到的邊的v加入U集合。如果U集合已有n個元素，則結束，否則繼續執行②。

其演算法的時間復雜度為O(n^2)

Prim演算法實現：

（1）集合：設置一個數組set(i=0,1,..,n-1),初始值為 0,代表對應頂點不在集合中（注意：頂點號與下標號差1）

（2）圖用鄰接陣表示，路徑不通用無窮大表示，在計算機中可用一個大整數代替。
{先選定一個點，然後從該點出發，與該點相連的點取權值最小者歸入集合，然後再比較在集合中的兩點與其它各點的邊的權值最小者，再次進入集合，一直到將所有的點都歸入集合為止。}

❿ 用c語言描述prim演算法求最小生成樹.... 求高人指點啊，給出完整的代碼，那個鄰接矩陣是要要一次全部輸入的

#include <cstdio>
#include <iostream>
#include <memory.h>
using namespace std;
const int maxn=102;
const int inf=1<<30;
int map[maxn][maxn];
int dis[maxn];
bool flag[maxn];
int a,b,c,n,m,ans;

void init()
{
memset(map,-1,sizeof(map));
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(map[a][b]==-1 || c< map[a][b])
{
map[a][b]=map[b][a]=c;
}
}
}

void prim()
{
memset(flag,false,sizeof(flag));
for(int i=1;i<=n;i++)dis[i]=inf;
dis[1]=0;
ans=0;
for(int j=1;j<=n;j++)
{
int now,value=inf;
for(int i=1;i<=n;i++)
{
if(flag[i]==false && dis[i]<value)
{
value=dis[i];
now=i;
}
}
if(value==inf)
{
cout << "-1" <<endl;
return;
}
flag[now]=true;
ans+=dis[now];
for(int i=1;i<=n;i++)
{
if(!flag[i] && map[now][i]!=-1 && dis[i]>map[now][i])
dis[i]=map[now][i];
}
}
cout << ans <<endl;
}

int main()
{
//'freopen("in.txt","r",stdin);
while(cin >> n >> m)
{
init();
prim();
}
return 0;
}

測試數據：
Sample Input
3 3
1 2 1
1 3 1
2 3 3
Sample Output
2
既然問到了prim演算法相信你能看懂測試數據是什麼意思~