⑴ 構造可以使n個城市連接的最小生成樹
/*普里姆演算法構造最小生成樹*/
#define MAXVEX 30
#define MAXCOST 1000
void prim(int c[MAXVEX][MAXVEX],int n)
/*己知圖的頂點為{1,2,...,n},c[i][j]和c[j][i]為邊(i,j)的權,列印最小生成樹
的每條邊*/
{
int i,j,k,min,lowcost[MAXVEX],closest[MAXVEX];;
for (i=2;i<=n;i++) /*從頂點1開始*/
{
lowcost[i]=c[1][i];
closest[i]=1;
}
closest[1]=0;
for (i=2;i<=n;i++) /*從U之外求離U中某一頂點最近的頂點*/
{
min=MAXCOST;
j=1;k=i;
while (j<=n)
{
if (lowcost[j]<min && closest[j]!=0)
{
min=lowcost[j];
k=j;
}
j++;
}
printf("(%d,%d) ",closest[k],k); /*列印邊*/
closest[k]=0; /*k加入到U中*/
for (j=2;j<=n;j++)
if (closest[j]!=0 && c[k][j]<lowcost[j])
{
lowcost[j]=c[k][j];
closest[j]=k;
}
}
}
main()
{
int n=7,i,j,mx[MAXVEX][MAXVEX];
for (i=0;i<=n;i++)
for (j=0;j<=n;j++)
mx[i][j]=MAXCOST;
mx[1][2]=50;
mx[1][3]=60;
mx[2][4]=65;
mx[2][5]=40;
mx[3][4]=52;
mx[3][7]=45;
mx[4][5]=50;
mx[5][6]=70;
mx[4][6]=30;
mx[4][7]=42;
printf("最小生成樹邊集:\n ");
prim(mx,n);
}
數據結構導學上的，
/*克魯斯卡爾演算法構造最小生成樹*/
#define MAXEDGE 30 /*MAXEDGE為最大的邊數*/
struct edges /*邊集類型,存儲一條邊的起始頂點bv、終止頂點tv和權w*/
{
int bv,tv,w;
};
typedef struct edges edgeset[MAXEDGE];
int seeks(int set[],int v)
{
int i=v;
while (set[i]>0) i=set[i];
return(i);
}
kruskal(edgeset ge,int n,int e)
/*ge表示的圖是按權值從小到大排列的*/
{
int set[MAXEDGE],v1,v2,i,j;
for (i=1;i<=n;i++) set[i]=0; /*給set中的每個元素賦初值*/
i=1; /*i表示待獲取的生成樹中的邊數,初值為1*/
j=1; /*j表示ge中的下標,初值為1*/
while (j<n && i<=e) /*按邊權遞增順序,逐邊檢查該邊是否應加入到生成樹中*/
{
v1=seeks(set,ge[i].bv); /*確定頂點v所在的連通集*/
v2=seeks(set,ge[i].tv);
if (v1!=v2) /*當v1,v2不在同一頂點集合,確定該邊應當選入生成樹*/
{
printf("(%d,%d) ",ge[i].bv,ge[i].tv);
set[v1]=v2;
j++;
}
i++;
}
}
main()
{
int n=7,e=10;
edgeset mx;
mx[1].bv=4;mx[1].tv=6;mx[1].w=30;
mx[2].bv=2;mx[2].tv=5;mx[2].w=40;
mx[3].bv=4;mx[3].tv=7;mx[3].w=42;
mx[4].bv=3;mx[4].tv=7;mx[4].w=45;
mx[5].bv=1;mx[5].tv=2;mx[5].w=50;
mx[6].bv=4;mx[6].tv=5;mx[6].w=50;
mx[7].bv=3;mx[7].tv=4;mx[7].w=52;
mx[8].bv=1;mx[8].tv=3;mx[8].w=60;
mx[9].bv=2;mx[9].tv=4;mx[9].w=65;
mx[10].bv=5;mx[10].tv=6;mx[10].w=70;
printf("最小生成樹邊集:\n ");
kruskal(mx,n,e);
}
⑵ 根據Prim演算法，求圖示的最小代價生成樹。 設①為起點，要求畫出構造過程。
#include <iostream>
#include <iomanip>
using namespace std;
#define MAX_VERTEX_NUM 10 //最大頂點個數
#define INFINITY 1000 //定義最大值為1000
typedef char VerType;//定點向量
typedef int VRType;//定點之間的關系（即權值）
typedef struct
{
VerType vexs[MAX_VERTEX_NUM]; //頂點向量
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //鄰接矩陣
int vexnum,arcnum; //圖的當前頂點數和弧數
}mgraph, * MGraph;
typedef struct
{
VerType adjvex;
VRType lowcost;
}closedge[MAX_VERTEX_NUM];//記錄從頂點集U到V-U的代價最小的邊的輔助數組定義
//初始化圖
void init_mgraph(MGraph &g)
{
g=(MGraph)malloc(sizeof(mgraph));
g->vexnum=0;
g->arcnum=0;
for(int i=0;i<MAX_VERTEX_NUM;i++)
g->vexs[i]=0;
for(i=0;i<MAX_VERTEX_NUM;i++)
for(int j=0;j<MAX_VERTEX_NUM;j++)
g->arcs[i][j]=INFINITY;
}
void add_vexs(MGraph &g) //增加頂點
{
cout<<"請輸入頂點的個數:"<<endl;
cin>>g->vexnum;
cout<<"請輸入頂點的值"<<endl;
for(int i=0;i<g->vexnum;i++)
{
cin>>g->vexs[i];
}
}
void add_arcs(MGraph &g) //增加邊
{
cout<<"請輸入邊的個數:"<<endl;
cin>>g->arcnum;
VerType ch1,ch2;
int weight;
int row,col;
for(int i=0;i<g->arcnum;i++)
{
cin>>ch1>>ch2>>weight;
for(int j=0;j<g->vexnum;j++)
{
if(g->vexs[j]==ch1)
{
row=j;
}
if(g->vexs[j]==ch2)
{
col=j;
}
}
g->arcs[row][col]=weight; //有向帶權圖只需把1改為weight
g->arcs[col][row]=weight;
}
}
void creat_mgraph(MGraph &g) //創建圖
{
add_vexs(g); //增加頂點
add_arcs(g); //增加邊
}
void print_mgraph(MGraph &g) //列印圖
{
for(int i=0;i<g->vexnum;i++)
cout<<" "<<g->vexs[i]<<" ";
cout<<endl;
for(i=0;i<g->vexnum;i++)
{
cout<<g->vexs[i];
for(int j=0;j<g->vexnum;j++)
{
cout<<setw(5)<<g->arcs[i][j]<<" ";
}
cout<<endl;
}
}
//返回頂點v在頂點向量中的位置
int LocateVex(MGraph &g, VerType v)
{
int i;
for(i = 0; v != g->vexs[i] && i < g->vexnum; i++)
;
if(i >= g->vexnum)
return -1;
return i;
}
//求出T的下一個節點，第k節點
int minimun(MGraph &g, closedge closedge)
{
int min=INFINITY,k=0,i;
for(i=0;i<g->vexnum;i++)
{
if(closedge[i].lowcost != 0 && closedge[i].lowcost < min)
{
min = closedge[i].lowcost;
k = i;
}
}
return k;
}
//普里姆演算法
void MiniSpanTree_Prim(MGraph &g, VerType u) //普里姆演算法從頂點u出發構造G的最小生成樹T，輸出T的各條邊。
{
closedge closedge;
int i,j;
int k=LocateVex(g,u);
for(j=0;j<g->vexnum;j++) //輔助數組初始化
{
if(j!=k)
{
closedge[j].adjvex=u;
closedge[j].lowcost=g->arcs[k][j];
}
}
closedge[k].lowcost = 0; //初始，U={u}
for(i=1;i<g->vexnum;i++) //選擇其餘g.vexnum-1個頂點
{
k=minimun(g,closedge); //求出T的下一個節點，第k節點
cout<<closedge[k].adjvex<<" "<<g->vexs[k]<<" "<<closedge[k].lowcost<<endl; //輸出生成樹的邊
closedge[k].lowcost=0; //第k頂點並入U集
for(j=0;j<g->vexnum;j++)
{
if(g->arcs[k][j] < closedge[j].lowcost) //新頂點並入集後，選擇新的邊，將小的邊放到輔助數組中
{
closedge[j].adjvex = g->vexs[k];
closedge[j].lowcost = g->arcs[k][j];
}
}
}
}//MiniSpanTree_Prim
int main()
{
MGraph G;
init_mgraph(G); //初始化圖
creat_mgraph(G); //創建圖
print_mgraph(G); //列印圖
MiniSpanTree_Prim(G,G->vexs[0]); //最小生成樹
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;
⑷ 關於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演算法的證明
令 為一個帶權連通圖，T為G的一生成樹。對任一不在T中的邊 ，如果將 加入T中, 產生一條迴路，且 是迴路中權值最大的邊,那麼樹T具有MST性質。
引理1：如果生成樹 都具有MST性質，那他們的總代價相同。
proof （採用歸納法）：假設 有k條邊不相同，下面對k進行歸納：
引理2：生成樹T為最小生成樹 T具有MST性質
proof:
設邊 加入T以後產生迴路，且迴路中存在邊 ,則我們將 刪除，得到新的生成樹 ，則有 , 這與T是最小生成樹矛盾，因此 是迴路中權重最大的邊。
不妨設 是最小生成樹，由必要性證明知 有MST性質，再由引理1知道 和 總代價相同，則 也是最小生成樹。
proof（反證）:
假設構造的生成樹為 ，且不具有MST性質，不妨設 E(G)-E(T) ，即不在T中的、最小的一條邊，將 加入T中形成一個環，由於T不具有MST性質，則環中一定存在一條邊 ，且 ，接下來分情況討論：
綜上所述，prim演算法產生的生成樹具有MST性質。
⑹ 利用PRIM演算法生成最小生成樹
普里姆演算法. 普里姆演算法在找最小生成樹時，將頂點分為兩類，一類是在查找的過程中已經包含在樹中的（假設為 A 類），剩下的是另一類（假設為 B 類）。. 對於給定的連通網，起始狀態全部頂點都歸為 B 類。. 在找最小生成樹時，選定任意一個頂點作為起始點，並將之從 B 類移至 A 類；然後找出 B 類中到 A 類中的頂點之間權值最小的頂點，將之從 B 類移至 A 類，如此重復，直到 B 類中沒有頂點為止。. 所走過的頂點和邊就是該連通圖的最小生成樹
⑺ Prim演算法的實現過程
G=（V,E）
①初始化：讀入的數據用鄰接矩陣x存儲，一個一維布爾型數組chosen，記錄第i個節點是否已選，初始值除1外全部設為false，記錄權值的變數cost賦值為0；
以下②到④循環執行v-1次（每次生成一條邊，運行（點的個數減1）次後，生成一棵最小生成樹）：
②臨時變數p賦值為無限大，用於記錄當前最小值；
③二重循環（外循環i，內循環j）掃描鄰接矩陣：如果chosen[i]=true（也就是說第i個點已選），那麼掃描x[i]，如果not(chosen[j])（也就是說第j個點未選），那麼如果x[i,j]<p，那麼p賦值為x[i,j],臨時變數q賦值為j;
④把cost賦值為cost+o，把chosen[q]賦值為true（也就是說第j個點已選）；
⑤輸出cost。
一、以上給出具體的運行過程。這個演算法的策略就是貪心，和dijkstra差不多，每次都選擇未選的邊中權值最小的那一條，直到生成最小生成樹。用chosen的目的就是保證生成過程中沒有環出現，也就是說保證選擇的邊不會通向一個已經包含在生成樹中的點。
二、這個只輸出最小生成樹的每條邊權值之和，如果要輸出整棵最小生成樹，加一個[1..n,1..2]的數組，在第④步的時候把每次選的邊記錄下來就可以了。
三、用小頂堆在第③步優化一下的話就不用每次都掃描那麼多邊了，只不過建堆維護堆代碼寫起來很麻煩。
四、prim適合用於比較稠密的網，點數和邊數差不多的時候效率很惡心，一般都用kruskal。
⑻ 已知圖G如下所示，根據Prim演算法，構造最小生成樹。（要求給出生成過程）
①將帶權連通圖G=的各邊按權從小到大依次排列，如e1,e2,…,em,其中e1的權最小，em的權最大，m為邊數。 ②取權最小的兩條邊構成邊集T0，即T0={e1,e2},從e3起，按次序逐個將各邊加進集合T0中去，若出現迴路則將這條邊排除（不加進去），按此法一直進行到em，最後得到n-1條邊的集合T0={e1,e2,…,en-1}，則T0導出的子圖就是圖G的最小生成樹。
⑼ 利用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）圖用鄰接陣表示，路徑不通用無窮大表示，在計算機中可用一個大整數代替。
{先選定一個點，然後從該點出發，與該點相連的點取權值最小者歸入集合，然後再比較在集合中的兩點與其它各點的邊的權值最小者，再次進入集合，一直到將所有的點都歸入集合為止。}