導航:首頁 > 源碼編譯 > 鄰接表的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演算法相關的資料

熱點內容
武漢python爬蟲培訓 瀏覽:396
微信伺服器連接失敗是什麼原因 瀏覽:694
命令行執行sql腳本亂碼 瀏覽:751
屬於三灣改編譯的視頻 瀏覽:165
仿射密碼演算法 瀏覽:859
如何用命令格式化系統盤 瀏覽:54
伺服器主板響怎麼解決 瀏覽:569
為什麼安卓手機要root許可權 瀏覽:520
一台伺服器如何配置多個域名 瀏覽:857
pdf導入多看 瀏覽:243
剪切一半取消了文件夾怎麼恢復 瀏覽:994
空氣壓縮機符號 瀏覽:279
吹氣打氣泵空氣壓縮機怎麼用 瀏覽:617
程序員面試通過後又拒絕接受offer 瀏覽:520
linux獲取進程的父進程 瀏覽:22
android文件編輯器 瀏覽:985
美東伺服器叫什麼 瀏覽:532
四年級平均值怎麼算簡單演算法 瀏覽:183
冷撲大師演算法 瀏覽:373
重復數據比對演算法 瀏覽:740