C++示例詳解Prim算法與優(yōu)先隊列

第C++示例詳解Prim算法與優(yōu)先隊列目錄Prim算法prim代碼實現(xiàn)優(yōu)先隊列優(yōu)先隊列代碼實現(xiàn)自定義類型優(yōu)先序列貪心算法的本質(zhì)是：一個問題的局部最優(yōu)解，也是該問題的全局最優(yōu)解。

最小生成樹的最優(yōu)子結(jié)構(gòu)性質(zhì)：假設(shè)一個無向圖包含兩部分A,B，其中A為最小生成樹部分，B為剩余部分，則存在以下性質(zhì)：該無向圖中一個頂點在A部分，另一個頂點在B部分的邊中，權(quán)值最小的邊一定屬于整個無向圖的最小生成樹，即部分最小權(quán)值是整個最小生成樹的局部最有解，該性質(zhì)符合貪心算法的特點。

Prim算法

基于最小生成樹的該性質(zhì)，使用prim算法來求解最小生成樹。

貪心算法屬性：一個局部全優(yōu)解，也是全局全優(yōu)解

思想：設(shè)T是最小生成樹，A=V,(u,v)是連接著A到A補集（一個在A中，一個不在A中）最小權(quán)值的邊，則一定是最小生成樹邊。

prim代碼實現(xiàn)

#includestdio.h

#includemalloc.h

#defineVERTEXNUM6

voidcreateGraph(int(*edge)[VERTEXNUM],intstart,intend,intvalue);

voiddisplayGraph(int(*edge)[VERTEXNUM]);

voidprim(int(*edge)[VERTEXNUM],int(**tree)[VERTEXNUM],intstartVertex,int*vertexStatusArr);

intmain(void){

//動態(tài)創(chuàng)建存放邊的二維數(shù)組

int(*edge)[VERTEXNUM]=(int(*)[VERTEXNUM])malloc(sizeof(int)*VERTEXNUM*VERTEXNUM);

inti,j;

for(i=0;iVERTEXNUM;i++){

for(j=0;jVERTEXNUM;j++){

edge[i][j]=0;

//存放頂點的遍歷狀態(tài)，0：未遍歷，1：已遍歷

int*vertexStatusArr=(int*)malloc(sizeof(int)*VERTEXNUM);

for(i=0;iVERTEXNUM;i++){

vertexStatusArr[i]=0;

printf("afterinit:\n");

displayGraph(edge);

//創(chuàng)建圖

createGraph(edge,0,1,6);

createGraph(edge,0,3,5);

createGraph(edge,0,2,1);

createGraph(edge,1,2,5);

createGraph(edge,1,4,3);

createGraph(edge,2,4,6);

createGraph(edge,2,3,5);

createGraph(edge,2,5,4);

createGraph(edge,3,5,2);

createGraph(edge,4,5,6);

printf("aftercreate:\n");

displayGraph(edge);

//最小生成樹

int(*tree)[VERTEXNUM]=NULL;

prim(edge,tree,0,vertexStatusArr);

printf("aftergeneratetree:\n");

displayGraph(tree);

free(edge);

free(tree);

return0;

//創(chuàng)建圖

voidcreateGraph(int(*edge)[VERTEXNUM],intstart,intend,intvalue){

edge[start][end]=value;

edge[end][start]=value;

//打印存儲的圖

voiddisplayGraph(int(*edge)[VERTEXNUM]){

inti,j;

for(i=0;iVERTEXNUM;i++){

for(j=0;jVERTEXNUM;j++){

printf("%d",edge[i][j]);

printf("\n");

voidprim(int(*edge)[VERTEXNUM],int(**tree)[VERTEXNUM],intstartVertex,int*vertexStatusArr){

//申請存儲樹的內(nèi)存

*tree=(int(*)[VERTEXNUM])malloc(sizeof(int)*VERTEXNUM*VERTEXNUM);

inti,j;

for(i=0;iVERTEXNUM;i++){

for(j=0;jVERTEXNUM;j++){

(*tree)[i][j]=0;

//從頂點0開始，則頂點0就是已訪問的

vertexStatusArr[0]=1;

intleast,start,end,vNum=1;

//如果還頂點還沒有訪問完

while(vNumVERTEXNUM){

least=9999;

for(i=0;iVERTEXNUM;i++){

//選擇已經(jīng)訪問過的點

if(vertexStatusArr[i]==1){

for(j=0;jVERTEXNUM;j++){

//選擇一個沒有訪問過的點

if(vertexStatusArr[j]==0){

//選出一條value最小的邊

if(edge[i][j]!=0edge[i][j]least){

least=edge[i][j];

start=i;

end=j;

vNum++;

//將點設(shè)置為訪問過

vertexStatusArr[end]=1;

//將邊加到樹中

createGraph(*tree,start,end,least);

}

結(jié)果

優(yōu)先隊列

普通的隊列是一種先進先出的數(shù)據(jù)結(jié)構(gòu)，元素在隊列尾追加，而從隊列頭刪除。

優(yōu)先隊列中，元素被賦予優(yōu)先級。當(dāng)訪問元素時，具有最高優(yōu)先級的元素最先刪除。優(yōu)先隊列具有最高級先出（firstin,largestout）的行為特征。

優(yōu)先隊列代碼實現(xiàn)

基本類型優(yōu)先序列

#includeiostream

#includequeue

usingnamespacestd;

//方法1

structtmp1//運算符重載

intx;

tmp1(inta){x=a;}

booloperator(consttmp1a)const

returnxa.x;//大頂堆

//方法2

structtmp2//重寫仿函數(shù)

booloperator()(tmp1a,tmp1b)

returna.xb.x;//大頂堆

intmain()

tmp1a(1);

tmp1b(2);

tmp1c(3);

priority_queuetmp1

d.push(b);

d.push(c);

d.push(a);

while(!d.empty())

coutd.top().x'\n';

d.pop();

coutendl;

priority_queuetmp1,vectortmp1,tmp2

f.push(b);

f.push(c);

f.push(a);

while(!f.empty())

coutf.top().x'\n';

f.pop();

}

自定義類型優(yōu)先序列

#includeiostream

#includequeue

usingnamespacestd;

//方法1

structtmp1//運算符重載

intx;

tmp1(inta){x=a;}

booloperator(consttmp1a)const

returnxa.x;//大頂堆

//方法2

structtmp2//重寫仿函數(shù)

booloperator()(tmp1a,tmp1b)

returna.xb.x;//大頂堆

intmain()

tmp1a(1);

tmp1b(2);

tmp1c(3);

priority_queuetmp1

d.push(b);

d.push(c);

d.push(a);

while(!d.empty()