普里姆演算法c語言

❶ 普里姆演算法的普里姆演算法的實現

為了便於在兩個頂點集U和V-U之間選擇權最小的邊，建立了兩個輔助數組closest和lowcost，它們記錄從U到V-U具有最小權值的邊，對於某個j∈V-U，closest[j]存儲該邊依附的在U中的頂點編號，lowcost[j]存儲該邊的權值。
為了方便，假設圖G採用鄰接矩陣g存儲，對應的Prim(g,v)演算法如下：
void Prim(MatGraph g,int v) //輸出求得的最小生樹的所有邊
{ int lowcost[MAXVEX]; //建立數組lowcost
int closest[MAXVEX]; //建立數組closest
int min,i,j,k;
for (i=0;i<g.n;i++) //給lowcost[]和closest[]置初值
{ lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<g.n;i++) //構造n-1條邊
{ min=INF; k=-1;
for (j=0;j<g.n;j++) //在(V-U)中找出離U最近的頂點k
if (lowcost[j]!=0 && lowcost[j]<min)
{ min=lowcost[j];
k=j; //k為最近頂點的編號
}
printf( 邊(%d,%d),權值為%d ,closest[k],k,min);
lowcost[k]=0; //標記k已經加入U
for (j=0;j<g.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;
}
}
}
普里姆演算法中有兩重for循環，所以時間復雜度為O(n2)，其中n為圖的頂點個數。由於與e無關，所以普里姆演算法特別適合於稠密圖求最小生成樹。

❷ 普里姆演算法是什麼

普里姆(Prim)演算法，和克魯斯卡爾演算法一樣，是用來求加權連通圖的最小生成樹的演算法。

普里姆演算法（Prim演算法），圖論中的一種演算法，可在加權連通圖里搜索最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中，不但包括了連通圖里的所有頂點（英語：Vertex (graph theory)），且其所有邊的權值之和亦為最小。

該演算法於1930年由捷克數學家沃伊捷赫·亞爾尼克（英語：Vojtěch Jarník）發現；並在1957年由美國計算機科學家羅伯特·普里姆（英語：Robert C. Prim）獨立發現；1959年，艾茲格·迪科斯徹再次發現了該演算法。因此，在某些場合，普里姆演算法又被稱為DJP演算法、亞爾尼克演算法或普里姆－亞爾尼克演算法。

基本思想：

對於圖G而言，V是所有頂點的集合；現在，設置兩個新的集合U和T，其中U用於存放G的最小生成樹中的頂點，T存放G的最小生成樹中的邊。

從所有uЄU，vЄ(V-U) (V-U表示出去U的所有頂點)的邊中選取權值最小的邊(u, v)，將頂點v加入集合U中，將邊(u, v)加入集合T中，如此不斷重復，直到U=V為止，最小生成樹構造完畢，這時集合T中包含了最小生成樹中的所有邊。

❸ 使用普里姆演算法求最小生成樹.

void minispantree_PRIM(int ad[][5],int n)
{ int i,j,k,p,q,wm;
q=p=n-1;
ad[q][q]=1;
for(k=0;k<(n-1);k++)
{ wm=MAX;
for(i=0;i<n;i++)
if(ad[i][i]==1)
for(j=0;j<岩豎纖n;j++)
if((ad[j][j]==0)&&(ad[i][j]<wm))
{ wm=ad[i][j];
p=i;
q=j;
}
ad[q][q]=1;
printf("%d %d %d\n"纖伍,p+1,q+1,ad[p][q]);
if(p>粗仿q) ad[p][q]=-ad[p][q];
else ad[q][p]=-ad[q][p];
}
}

main()
{
int m=6;
int ad[][5]={0,6,1,5,200,200,
6,0,5,200,3,200,
1,5,0,5,6,4,
5,200,5,0,200,2,
200,3,6,200,0,6,
200,200,4,2,6,0};
minispantree_PRIM(ad[5][5],m);

}

❹ 急！數據結構最小生成樹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++）

求最小生成樹的譜里姆演算法
#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;

❻ 普里姆演算法(Prime)

普利姆(Prim)演算法求最小生成樹，也就是在包含 n 個頂點的連通圖中，找出只有(n-1)條邊包含所有 n 個頂點的連通子圖，也就是所謂的極小連通子圖

普利坦鬧仔姆的演算法如下:

1. 有七個站點 A,B,C,D,E,F,G，現在需要修線路把彎嘩七個站點聯通

2. 各個站點的距離用邊線表示(權)，比如 A->C 為7公里

問： 如讓汪何修線路使各個站點都能聯通， 同時修的線路里程最短？

❼ 普里姆演算法

你要先明白prim演算法的原理，明白原理後看下面的程序要點：

1.程序實現的時候將點分成兩部分，加入集合的和沒有加入集合的；
2.每次從沒有加入集合中找點；
3.對所有沒有加入到集合中的點中，找一個邊權最小的；
4.將邊權最小的點加入集合中，並且修改和加入點相連的沒有加入的點的權，重復第2步，知道所有的點都加入到集合中；