prime演算法最小生成樹

『壹』 prime演算法什麼意思

prime？如果真的是prime的話，那可能是指打素數表的方法。比如歐拉篩法之類的。
如果是prim演算法的話，是一種貪心的最小生成樹演算法。

『貳』 primt演算法求無向網的最小生成樹c++程序

網上一大把啊。。

我告訴你思路吧，prime演算法是貪心策略，每次選出可以連通的最短邊，直到生成樹形成

『叄』 prime演算法建立最小生成樹的代碼

這個我也不會,

『肆』 13.用Prim演算法和Kruskal演算法構造圖的最小生成樹,所得到的最小生成樹是否相同

如果原來的圖裡面任何兩條邊長都不相同,那麼最小生成樹是唯一的,此時不管用什麼方法算出來的都是一樣的
但是如果圖里有相等的邊,那麼最小生成樹可能會不唯一,這樣就無法保證不同的方法得到同一棵樹（即使是同一個演算法,只要圖的編號方式改變也可能得到不同的最小生成樹）

『伍』 杭電acm1233

同學，這個就是赤裸裸的最小生成樹演算法。prime演算法和kruskal演算法都可以順利通過，沒有一點陷阱。建議你用kruskal演算法來解。在學習kruskal演算法之前，學習一下並查集。這個問題一點也不難。
這里給出sruskal演算法的解：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

int pre[105];

struct node
{
int x1,x2;
int cost;
}D[5050];

void Init(int n)
{
int i;
for(i=1;i<=n;i++)
pre[i]=i;
}

int Find(int x)
{
int t,r=x;
while(x!=pre[x]) x=pre[x];
while(r!=x)
{
t=pre[r];
pre[r]=x;
r=t;
}
return x;
}

void Union(int a,int b)
{
a=Find(a);
b=Find(b);
pre[b]=a;
}

bool cmp(node a,node b)
{
return a.cost<b.cost;
}

int main()
{
int n,t,i,cnt,ans;
while(scanf("%d",&n)!=EOF,n)
{
Init(n);
t=n*(n-1)/2;
for(i=0;i<t;++i)
scanf("%d%d%d",&D[i].x1,&D[i].x2,&D[i].cost);
sort(D,D+t,cmp);
cnt=1;i=0;ans=0;
while(cnt<n&&i<t)
{
if(Find(D[i].x1)!=Find(D[i].x2))
{
++cnt;
Union(D[i].x1,D[i].x2);
ans+=D[i].cost;
}
++i;
}
printf("%d\n",ans);
}
return 0;
}

kruskal演算法的思路你可以在維基網路上找到，至於並查集，你可以看我的筆記http://whchen.net/blog/?p=259
這道題所有代碼就包含排序和並查集而已，沒什麼太復雜的，加油！

『陸』 分別給出下圖使用Prime演算法（從A開始）和kruskar找最小支撐樹的過程

最小生成樹：
Prime：從某點開始每次找鄰接的最小邊，忽略已經加入的頂點
AB，AD，DE，DC，DF
Kruskar：每次從剩餘邊集合里找最小邊，忽略已經加入的頂點
DE，AB，DC，AD，DF
兩者是一樣的，順序不同而已

『柒』 C語言中prime的作用

prime的作用就是判斷一個數是否為素數（也稱「質數」）。

例如：

#include<stdio.h>

intIsPrime(intn)

{

if(n<=1)return0;

if(n%2==0)returnn==2;

for(inti=3;;i+=2)

{

if(i>n/i)break;//等價於i*i>n,不用開方

if(n%i==0)return0;

}

return1;

}

intmain()

{

for(intn=100;n<=300;n++)

if(IsPrime(n))

printf("%4d",n);

return0;

}

(7)prime演算法最小生成樹擴展閱讀：

prime演算法

prime是以點為基礎出發進行檢索最小生成樹的一種貪心演算法。

思想：

將所有的點分成兩類，一類是已經放到碗里的，另一類是還沒有有放到碗里的，可以通過一個數組bool visit[]來記錄這個點到底是屬於第一類還是屬於第二類之後每一個周期索要進行的操作，找出一一定范圍內路徑的的范圍的最小值。

所有的從第一類點直接連接到第二類點的邊將最小的邊記錄下來（這個也就是生成樹中的一條邊）將這個新邊（這個一個連接第一類點和第二類點的邊）連到的那個第二類點歸類到第一類點中，之後重復這個操作，最終消滅所有的第二類點。

假設有n個節點，我最初給出一個點，以這個點開始進行搜索，這個時候該點為第一類點，其餘n-1個點為第二類點。之後進行n-1次操作，一共選出了n-1個邊（符合樹的性質），構成了最小生成樹。

『捌』 啊，求教prime演算法中我這個二維數組咋輸入

將一個圖的頂點分為兩部分，一部分是最小生成樹中的結點（A集合），另一部分是未處理的結點（B集合）。
2.首先選擇一個結點，將這個結點加入A中，然後，對集合A中的頂點遍歷，找出A中頂點關聯的邊權值最小的那個（設為v），將此頂點從B中刪除，加入集合A中。
3.遞歸重復步驟2，直到B集合中的結點為空，結束此過程。
4.A集合中的結點就是由Prime演算法得到的最小生成樹的結點，依照步驟2的結點連接這些頂點，得到的就是這個圖的最小生成樹。