導航:首頁 > 源碼編譯 > 鄰接表的prim演算法

鄰接表的prim演算法

發布時間:2022-11-30 11:17:30

❶ C語言演算法求解:對任意給定的網路(頂點數和邊數自定),設計演算法生成它的最小生成樹。

上一個圖和代碼:

圖1為要創建的圖,圖2為對應的最小生成樹

代碼為:

//圖論之最小生成樹:prim演算法實現

#include"stdio.h"

#include"malloc.h"

//聲明

voidoutput(structadjacentlisthead*alh,intmapsize);

structadjacentlistson//鄰接表項結構體

{

intsonelement;

intquanvalue;

structadjacentlistson*next;

};

structadjacentlisthead//鄰接表頭結構體

{

charflag;

intelement;

intcurqvalue;

structadjacentlisthead*previous;

structadjacentlistson*startson;

};

structadjacentlisthead*mapinitialnize(intmapsize)//初始化圖函數

{

structadjacentlisthead*alh=NULL;

structadjacentlistson*newnode=NULL;

inti,x,y,z;

alh=malloc(sizeof(structadjacentlisthead)*mapsize);

if(alh==NULL)

returnNULL;

for(i=0;i<mapsize;i++)

{

alh[i].flag=0;

alh[i].element=i+1;

alh[i].curqvalue=0;

alh[i].previous=NULL;

alh[i].startson=NULL;

}

scanf("%d%d%d",&x,&y,&z);

while(x&&y)//直到輸入的x,y中至少有一個0為止

{

newnode=malloc(sizeof(structadjacentlistson));

newnode->sonelement=y;

newnode->quanvalue=z;

newnode->next=alh[x-1].startson;

alh[x-1].startson=newnode;

scanf("%d%d%d",&x,&y,&z);

}

returnalh;

}

intfindminnode(structadjacentlisthead*alh,intmapsize)//找到最小權值對應的結點

{

inti,minvalue=~(1<<(sizeof(int)*8-1)),minplace=0;

for(i=0;i<mapsize;i++)

{

if(alh[i].flag==0&&alh[i].curqvalue!=0)

{

if(alh[i].curqvalue<minvalue)

{

minvalue=alh[i].curqvalue;

minplace=i+1;//

}

}

}

returnminplace;

}

voidfindthemintree(structadjacentlisthead*alh,intstartplace,intmapsize)//找到最小生成樹

{

structadjacentlistson*alstmp=NULL;

intcurplace=startplace;

while(curplace)

{

alstmp=alh[curplace-1].startson;

alh[curplace-1].flag=1;//正在訪問

while(alstmp)

{

if(alh[alstmp->sonelement-1].flag==0)

{

if(alh[alstmp->sonelement-1].curqvalue==0||(alh[alstmp->sonelement-1].curqvalue>alstmp->quanvalue))//比較方法與有權圖有一點不同

{

alh[alstmp->sonelement-1].curqvalue=alstmp->quanvalue;

alh[alstmp->sonelement-1].previous=&alh[curplace-1];

}

}

alstmp=alstmp->next;

}

curplace=findminnode(alh,mapsize);//通過函數找到最小的一個結點

}

}

voidoutput(structadjacentlisthead*alh,intmapsize)

{

inti;

for(i=0;i<mapsize;i++)

{

printf("%d點的權值為:%d ",i+1,alh[i].curqvalue);

}

printf("................................................... ");

}

intmain()

{

structadjacentlisthead*alh=NULL;

intmapsize=7,startplace=1;

alh=mapinitialnize(mapsize);

findthemintree(alh,startplace,mapsize);

output(alh,mapsize);

}

輸入數據對應第一圖:

122

134

141

212

243

2510

314

342

365

411

423

432

457

468

474

5210

547

576

635

648

671

744

756

761

000

閱讀全文

與鄰接表的prim演算法相關的資料

熱點內容
java繼承類實例 瀏覽:286
疫情期間程序員的工資 瀏覽:27
最好的python編譯器 瀏覽:187
安卓手機如何調分屏 瀏覽:729
安卓系統藍牙耳機如何用 瀏覽:719
為什麼微信不能給appstore充值 瀏覽:495
程序員的保護動物 瀏覽:274
程序員遇到問題去哪個網站 瀏覽:531
安卓手機空格鍵連續輸入怎麼取消 瀏覽:520
壓縮空氣管道流量計 瀏覽:564
ug編程高級教程 瀏覽:177
什麼叫做伺服器已滿 瀏覽:37
暑假哪有教演算法的 瀏覽:136
密碼學的根基是加密 瀏覽:662
stata方差檢驗命令 瀏覽:337
解壓後文件夾里的內容丟失 瀏覽:715
解壓無敵視頻 瀏覽:690
什麼是伺服器辨認不了 瀏覽:129
java如何調用類方法 瀏覽:483
管理孩子的app叫什麼 瀏覽:546