prim演算法c
A. c++求最小生成樹prim演算法,我搗鼓2天了,真心不會改了,求指導感激不盡啊
這能給你一個源程序了，希望有所幫助。
/*==================================================*\
| Prim 求MST
| INIT: cost[][]耗費矩陣(inf為無窮大);
| CALL: prim(cost, n); 返回-1代表原圖不連通;
\*==================================================*/
#define typec int // type of cost
const typec inf = 0x3f3f3f3f; // max of cost
int vis[V]; typec lowc[V];
typec prim(typec cost[][V], int n) // vertex: 0 ~ n-1
{
int i, j, p;
typec minc, res = 0;
memset(vis, 0, sizeof(vis));
vis[0] = 1;
for (i=1; i<n; i++) lowc[i] = cost[0][i];
for (i=1; i<n; i++) {
minc = inf; p = -1;
for (j=0; j<n; j++)
if (0 == vis[j] && minc > lowc[j]) {
minc = lowc[j]; p = j;
}
if (inf == minc) return -1; // 原圖不連通
res += minc; vis[p] = 1;
for (j=0; j<n; j++)
if (0 == vis[j] && lowc[j] > cost[p][j])
lowc[j] = cost[p][j];
}
return res;
}
B. c++prim演算法是什麼
#include<bits/stdc++.h>
using namespace std;
const int N=510,I=1e9;
int n,m,k;
int d[N][N],dist[N],s[N];
int prim(){
memset(dist,0x3f,sizeof(dist));int res=0;
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++)
if(s[j]==0&&(t==-1||dist[j]<dist[t])) t=j;
if(i!=0&&dist[t]==0x3f3f3f3f) return -1;
s[t]=1;if(i!=0) res+=dist[t];
for(int j=1;j<=n;j++) dist[j]=min(dist[j],d[t][j]);
}
return res;
}
int main(){
cin>>n>>m;
memset(d,0x3f,sizeof(d));
for(int i=0;i<m;i++){
int a,b,c;cin>>a>>b>>c;
d[a][b]=d[b][a]=min(d[a][b],c);
}
int t=prim();
if(t==-1) cout<<"impossible";
else cout<<t;
return 0;
}
C. 用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調整候選輕邊集
}
}
D. 急！數據結構最小生成樹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;
}
}
}
E. 什麼是Prim演算法
Prim演算法
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](i=0,1,..,n-1),初始值為 0,代表對應頂點不在集合中（注意：頂點號與下標號差1）
（2）圖用鄰接陣表示，路徑不通用無窮大表示，在計算機中可用一個大整數代替。
參考程序
/* Prim.c
Copyright (c) 2002, 2006 by ctu_85
All Rights Reserved.
*/
/* The impact of the situation of articulation point exists can be omitted in Prim algorithm but not in Kruskal algorithm */
#include "stdio.h"
#define maxver 10
#define maxright 100
int main()
{
int G[maxver][maxver],in[maxver]=,path[maxver][2];
int i,j,k,min=maxright;
int v1,v2,num,temp,status=0,start=0;
restart:
printf("Please enter the number of vertex(s) in the graph:\n");
scanf("%d",&num);
if(num>maxver||num<0)
{
printf("Error!Please reinput!\n");
goto restart;
}
for(j=0;j<num;j++)
for(k=0;k<num;k++)
{
if(j==k)
G[j][k]=maxright;
else
if(j<k)
{
re:
printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1);
scanf("%d",&temp);
if(temp>=maxright||temp<-1)
{
printf("Invalid input!\n");
goto re;
}
if(temp==-1)
temp=maxright;
G[j][k]=G[k][j]=temp;
}
}
for(j=0;j<num;j++)
{
status=0;
for(k=0;k<num;k++)
if(G[j][k]<maxright)
{
status=1;
break;
}
if(status==0)
break;
}
do
{
printf("Please enter the vertex where Prim algorithm starts:");
scanf("%d",&start);
}while(start<0||start>num);
in[start-1]=1;
for(i=0;i<num-1&&status;i++)
{
for(j=0;j<num;j++)
for(k=0;k<num;k++)
if(G[j][k]<min&&in[j]&&(!in[k]))
{
v1=j;
v2=k;
min=G[j][k];
}
if(!in[v2])
{
path[i][0]=v1;
path[i][1]=v2;
in[v1]=1;
in[v2]=1;
min=maxright;
}
}
if(!status)
printf("We cannot deal with it because the graph is not connected!\n");
else
{
for(i=0;i<num-1;i++)
printf("Path %d:vertex %d to vertex %d\n",i+1,path[i][0]+1,path[i][1]+1);
}
return 1;
}
Prim演算法。
設圖G =（V，E），其生成樹的頂點集合為U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的邊(u，v)∈E中找一條最小權值的邊，加入生成樹。
③、把②找到的邊的v加入U集合。如果U集合已有n個元素，則結束，否則繼續執行②。
其演算法的時間復雜度為O(n^2)
參考程序
//Prim 演算法 讀入頂點數(n)、邊數(m)，邊的起始點和權值 用鄰接矩陣儲存
//例如
//7 12 (7個頂點12條邊)
//1 2 2
//1 4 1
//1 3 4
//2 4 3
//2 5 10
//3 4 2
//4 5 7
//3 6 5
//4 6 8
//4 7 4
//5 7 6
//6 7 1
#include <stdio.h>
#include <string.h>
int main()
{
int m , n;
int a[201][201] , mark[201] , pre[201] , dist[201];
int s , t , w;
int i , j , k , min , tot;
freopen("Prim.txt" , "r" , stdin);
//讀入數據
memset(a , 0 , sizeof(a));
scanf("%d %d" , &n , &m);
for (i = 0; i < m; i ++)
{
scanf("%d %d %d" , &s , &t , &w);
a[s][t] = w; a[t][s] = w;
}
//賦初值
memset(mark , 0 , sizeof(mark));
memset(pre , 0 , sizeof(pre));
memset(dist , 9999 , sizeof(dist));
dist[1] = 0;
//Prim
for (i = 1; i <= n; i ++)
{
min = 9999; k = 0;
for (j = 1; j <= n; j ++)
if ((mark[j] == 0) && (dist[j] < min)) {min = dist[j]; k = j;}
if (k == 0) break;
mark[k] = 1;
for (j = 1; j <= n; j ++)
if ((mark[j] == 0) && (a[k][j] < dist[j]) && (a[k][j] > 0))
{
dist[j] = a[k][j];
pre[j] = k;
}
}
tot = 0;
for (i = 1; i <= n; i ++) tot += dist[i];
printf("%d\n" , tot);
return 0;
}
F. Prim演算法，解釋一步就好！
到C時可以得到的結果是：到2的最短長度為5，到5的最短長度為6，所以選最小的那個長度為5，即選擇下一個連接節點為2，即得到了D圖
G. 用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'留地方。
H. 對任意的網和起點,用PRIM演算法的基本思想求解出所有的最小生成樹(C語言編寫)
prim基本思想就是貪心，每次加最短的邊
既然要求所有的
那就判斷如果有兩條或更多條都是最小，那就分支出多種情況。
I. prim演算法是貪心演算法嗎
是prim演算法
普里姆演算法(Prim演算法)，圖論中的一種演算法，可在加權連通圖里搜索最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中，不但包括了連通圖里的所有頂點(英語：Vertex(graphtheory))，且其所有邊的權值之和亦為最小。
該演算法於1930年由捷克數學家沃伊捷赫·亞爾尼克(英語：VojtěchJarník)發現；並在1957年由美國計算機科學家羅伯特·普里姆(英語：RobertC.Prim)獨立發現；1959年，艾茲格·迪科斯徹再次發現了該演算法。因此，在某些場合，普里姆演算法又被稱為DJP演算法、亞爾尼克演算法或普里姆-亞爾尼克演算法。