普里姆演算法例題
A. 普里姆演算法
你要先明白prim演算法的原理，明白原理後看下面的程序要點：
1.程序實現的時候將點分成兩部分，加入集合的和沒有加入集合的；
2.每次從沒有加入集合中找點；
3.對所有沒有加入到集合中的點中，找一個邊權最小的；
4.將邊權最小的點加入集合中，並且修改和加入點相連的沒有加入的點的權，重復第2步，知道所有的點都加入到集合中；
B. 已知一個無向圖如下，分別用普里姆和克魯斯卡爾演算法生成最小生成樹（假設以1為起點，試畫出構造過程）。
1)普里姆演算法思想
從圖中任意取出一個頂點， 把它當成棵樹，然後從與這棵樹相接的邊中選取一條最短(權值最小)的邊， 並將這條邊及其所連接的頂點也並入這棵樹中，此時得到了一棵有兩個頂點的樹。然後從與這棵樹相接的邊中選取一條最短的邊，並將這條邊及其所連頂點並入當前樹中，得到一棵有3個頂點的樹。以此類推，直到圖中所有頂點都被並入樹中為止，此時得到的生成樹就是最小生成樹。
2)克魯斯卡爾演算法思想
先將邊中的權值從小到大排序，每次找出候選邊中權值最小的邊，就將該邊並入生成樹中。重復此過程直到所有邊都被檢測完為止。其中要注意的是克魯斯卡爾演算法需要用到並查集，以此來判斷接下來要並入的邊是否會和已並入的邊構成迴路。這兩個圖分別用普里姆和克魯斯卡爾生成的最小生成樹見圖。
需要注意的是，在接下來要並入的最小權值不唯一的情況下，可以選取的邊是不唯一的，所以其最小生成樹也不唯一。(純手打，望採納，謝謝。)
C. 請問下下面這些關於數據結構的題怎麼做，請給出具體的解題過程
直接插入排序第四趟結果：25 35 45 48 48 78 52
簡單選擇排序第四趟結果：25 35 45 48 48 78 52
猜哪穗 2.孩子兄弟表示法：
我感覺應該都正確，費了我穗卜好大的勁才弄上去，一定採納哈，謝謝
D. 根據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;
}
E. 這是一道數據結構問題，問題如下：對於如下圖所示的帶權無向圖，給出利用普利姆（Prim)演算法和克魯斯卡爾
自己按下面的先後過程畫圖即是生成過程；說雀雀明（i,j）是一條連接頂點i和j的一條邊；
普利姆（Prim)演算法：從頂點0開始頃世早構造
（0,1），（0,2），（1,2），（2,5），（5,4）
克魯斯卡爾演算法：
（0,1），（0,2），（返或1,2），（4,5），（2,5）
F. 普里姆演算法(Prime)
普利姆(Prim)演算法求最小生成樹，也就是在包含 n 個頂點的連通圖中，找出只有(n-1)條邊包含所有 n 個頂點的連通子圖，也就是所謂的極小連通子圖
普利坦鬧仔姆的演算法如下:
1. 有七個站點 A,B,C,D,E,F,G，現在需要修線路把彎嘩七個站點聯通
2. 各個站點的距離用邊線表示(權)，比如 A->C 為7公里
問： 如讓汪何修線路使各個站點都能聯通， 同時修的線路里程最短？
G. 用普里姆演算法求最小生成樹（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;
H. 在N個城市之間鋪設煤氣管道,只需架設N-1條線路即可,如何以最低的經濟代價鋪設.(普里姆演算法)
此題可以用最小生成樹的辦法解決即普里姆如納演算法:把N個城市看作N個頂點,把可以鋪設管道的兩個城市間用線連起來,把相連的兩個城市之間的距離作為這一條邊的權(假設所有管道的單位造價相同).把所有邊的權按照大小排列起來,先選權最小的邊的兩個頂點納入集合S,再選第二條邊,把與這條邊關聯的頂點納入S,但前提是所選的邊不能與前面所選的邊構成迴路,就這樣依次選取.若有權相同的n條邊則任選一條,但前提是所選的邊不能與前面所選的邊構成迴路.接下來選的時候還是選n條邊中的一條前提依然和前面相同.當所粗察選的路的岩橡茄個數為N-1時就停止.此時的線路即為最優的鋪設線路.