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

熱點內容
用洗碗海綿解壓玩具 瀏覽:855
thinkphp5php54 瀏覽:467
冰箱壓縮機啟動器損壞後故障現象 瀏覽:815
伺服器管理器如何取消每次都打開 瀏覽:611
編程兵書pdf 瀏覽:414
益盟伏擊活躍股指標公式源碼 瀏覽:868
搏擊解壓球的訓練方法 瀏覽:799
很解壓的小游戲超級好玩哦 瀏覽:97
高光譜圖像壓縮 瀏覽:700
新天堂伺服器什麼時候開 瀏覽:79
ios用什麼app玩雲頂 瀏覽:518
teslaapp如何更新 瀏覽:711
app去哪裡可以做 瀏覽:888
php技術選型方案 瀏覽:586
win7如何開啟oa精靈伺服器 瀏覽:613
三菱plc編程怎麼編輯fb塊 瀏覽:280
程序員怎麼用網站的圖片 瀏覽:29
梅花app緩存文件在哪裡 瀏覽:979
android動態換圖標 瀏覽:719
從程序員到跨國上市公司 瀏覽:895