普利姆演算法最小生成樹

❶ 無論用普里姆演算法或者是克魯斯卡爾演算法求最小生成樹，得出的結果應該一樣么

不總是一樣的，克魯斯卡爾演算法是精確演算法，即每次都能求得最優解，但對於規模較大的最小生成樹問題，求解速度較慢。而普里姆演算法是近似求解演算法，雖然對於大多數最小生成樹問題都能求得最優解，但相當一部分求得的是近似最優解。這是我個人見解。

❷ 已知一個無向圖如下，分別用普里姆和克魯斯卡爾演算法生成最小生成樹（假設以1為起點，試畫出構造過程）。

1)普里姆演算法思想
從圖中任意取出一個頂點， 把它當成棵樹，然後從與這棵樹相接的邊中選取一條最短(權值最小)的邊， 並將這條邊及其所連接的頂點也並入這棵樹中，此時得到了一棵有兩個頂點的樹。然後從與這棵樹相接的邊中選取一條最短的邊，並將這條邊及其所連頂點並入當前樹中，得到一棵有3個頂點的樹。以此類推，直到圖中所有頂點都被並入樹中為止，此時得到的生成樹就是最小生成樹。
2)克魯斯卡爾演算法思想
先將邊中的權值從小到大排序，每次找出候選邊中權值最小的邊，就將該邊並入生成樹中。重復此過程直到所有邊都被檢測完為止。其中要注意的是克魯斯卡爾演算法需要用到並查集，以此來判斷接下來要並入的邊是否會和已並入的邊構成迴路。這兩個圖分別用普里姆和克魯斯卡爾生成的最小生成樹見圖。

需要注意的是，在接下來要並入的最小權值不唯一的情況下，可以選取的邊是不唯一的，所以其最小生成樹也不唯一。(純手打，望採納，謝謝。)

❸ 求解用普里姆演算法畫下題最小生成樹！

{(0,2),(0,1),(1,5),(0,3),(3,6),(6,4),(5,7)}

❹ 最小生成樹 普里姆演算法有問

普里姆演算法構造最小生成樹演算法的思想是：選擇一個結點，然後從這個結點開始，選擇權值最小的邊，用一條邊連接，然後再以前面的那個結點開始，和你連接的那個結點作為根節點，再選擇權值最小的邊進行連接。
對權值給出解釋：以上圖為例，權值就是你第一個圖那幾條邊（弧）上，所標的數字。
對樓主所提出的問題：並不是連接那圓圈中最小的圓圈，如果沒錯的話，那圓圈中的數字表示的是V1---V6六個頂點，並不是代表數字，以3和6為頂點，找權值最小邊，顯然6——4為最小，即權值為2，頂點364相連接的時候各以364為頂點尋找最小邊，應該先從6連接到2，那麼現在加入頂點的為3642頂點，現在以3642為頂點尋找最小邊，應該從2連接到1，現在被連接的有63421，在以63421為頂點尋找最小邊
出現了問題：如果以5為權值的話，無論從2連接到4還是從3連接到4都出現了環，當然我們知道數中是不能出現環的，所以尋找次小的，剩餘5與13之間權值最小為13.所以將1連接5，即得到最小生成樹。
樓主可以按照我說的在紙上畫一下試試
從6連接到3因為有前提條件：從頂點V3開始用普里姆方法求其最小生成數，可見是從頂點3連接到6，而不是從6連接到3
希望可以解決樓主的疑惑，謝謝！

❺ 最小生成樹普里姆演算法，求指錯

我改了一下這些地方
程序成功運行並輸出邊了。
void CreatUDN(MGraph G) 改為void CreatUDN(MGraph &G)
原因，函數裡面進行處理的，實際上只是main函數中G的一個副本。這是函數調用時，「形參」與「實參」的區別。實際上處理輸入操作的，只是函數裡面的臨時變數，而不是main裡面真正的G。加上&，就表示每次對G的操作，都會去尋找G所在的存儲地址進行操作。故這樣可以實現直接訪問main中的G
printf("\tWelcom to use this program!\n");這句之前，我將G中各數據項全部置0。實際上需要置0的只有矩陣，因為另外那幾個數據都有輸入操作。原因是，G是main的局部變數。局部變數在創建的時候，若不賦初值，系統會給予一個隨機值，而不是0。這些隨機值會對生成樹演算法的計算造成影響。其實，就是沒邊時突然間「隨機」了一些邊上去。。。

❻ 利用普里姆演算法求解最小生成樹，寫出步驟或畫圖表示過程。

<1,6>邊長度未知，這里看成無窮大。
歷次循環中，選擇兩端點分別在U，V中的邊中長度最小者，
具體如下：
1. 將1加入U中，其餘點加入V中。
2. 選擇邊<1,7>，將7加入U中，從V中除去該點。
3. 選擇邊<7,6>，將6加入U中，從V中除去該點。
4. 選擇邊<1,2>，將2加入U中，從V中除去該點。
5. 選擇邊<2,3>，將3加入U中，從V中除去該點。
6. 選擇邊<2,4>，將4加入U中，從V中除去該點。
7. 選擇邊<2,5>，將5加入U中，從V中除去該點。
結束。由上述六條邊組成的樹為求得的最小生成樹。

❼ 數據結構問題。 怎麼用普里姆演算法求最小生成樹能詳細講解下並舉下例子嗎謝謝～

該演算法以貪心為基礎，每次保證了添加生成的樹一定是最小生成樹

❽ 最小生成樹 普里姆演算法和克魯斯卡爾演算法

kruskal演算法的時間復雜度主要由排序方法決定，其排序演算法只與帶權邊的個數有關，與圖中頂點的個數無關，當使用時間復雜度為O（eloge）的排序演算法時，克魯斯卡演算法的時間復雜度即為O（eloge），因此當帶權圖的頂點個數較多而邊的條數較少時，使用克魯斯卡爾演算法構造最小生成樹效果最好！

克魯斯卡爾演算法
假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，則按照克魯斯卡爾演算法構造最小生成樹的過程為：先構造一個只含 n 個頂點，而邊集為空的子圖，若將該子圖中各個頂點看成是各棵樹上的根結點，則它是一個含有 n 棵樹的一個森林。之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，也就是說，將這兩個頂點分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直至森林中只有一棵樹，也即子圖中含有 n-1條邊為止。

普里姆演算法
假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，TV 是 WN 上最小生成樹中頂點的集合，TE 是最小生成樹中邊的集合。顯然，在演算法執行結束時，TV=V，而 TE 是 E 的一個子集。在演算法開始執行時，TE 為空集，TV 中只有一個頂點，因此，按普里姆演算法構造最小生成樹的過程為：在所有「其一個頂點已經落在生成樹上，而另一個頂點尚未落在生成樹上」的邊中取一條權值為最小的邊，逐條加在生成樹上，直至生成樹中含有 n-1條邊為止。
--以上傳自http://hi..com/valyanprogramming/blog/item/1bc960e6095f9726b93820d9.html

1.Kruskal
//題目地址:http://acm.pku.e.cn/JudgeOnline/problem?id=1258

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
struct node
{
int v1;
int v2;
int len;
}e[10000];//定義邊集
int cmp(const void *a,const void *b)//快排比較函數
{
return ((node*)a)->len-((node*)b)->len;
}
int v[100],a[100][100];//v為點集
void makeset(int n)
{
for(int i=0;i<n;i++)
v[i]=i;
}
int find(int x)
{
int h=x;
while(h!=v[h])
h=v[h];
return h;
}
int main()
{
int n,i,j,r1,r2,p,total;
while(scanf("%d",&n)!=EOF)
{
p=0;
total=0;
makeset(n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
e[p].v1=i;
e[p].v2=j;
e[p].len=a[i][j];
p++;
}
}
qsort(e,p,sizeof(e[0]),cmp);
for(i=0;i<p;i++)
{
r1=find(e[i].v1);
r2=find(e[i].v2);
if(r1!=r2)
{
total+=e[i].len;
v[r1]=r2;
}
}
printf("%d\n",total);
}
system("pause");
return 0;
}

2.Prim
//題目地址同上

#include <iostream>
using namespace std;

#define M 101
#define maxnum 100001
int dis[M][M];

int prim(int n)
{
bool used[M]={};
int d[M],i,j,k;
for(i=1; i<=n; i++)
d[i] = dis[1][i];
used[1] = true;
int sum=0;
for(i=1; i<n; i++){
int temp=maxnum;
for(j=1; j<=n; j++){
if( !used[j] && d[j]<temp ){
temp = d[j];
k = j;
}
}
used[k] = true;
sum += d[k];
for(j=1; j<=n; j++){
if( !used[j] && dis[k][j]<d[j] )
d[j] = dis[k][j]; // 與Dijksta演算法的差別之處
}
}
return sum;
}

int main()
{
int n,i,j;
while( cin>>n ){

for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
scanf("%d",&dis[i][j]);
if( !dis[i][j] )
dis[i][j] = maxnum;
}
}

cout<<prim(n)<<endl;
}
return 0;
}

代碼來自網路

❾ 用普里姆演算法求最小生成樹（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;

❿ 用普里姆演算法構造如圖所示的圖G的一棵最小生成樹。

解：使用普里姆演算法構造出如下圖G的一棵最小生成樹。