1、第1頁共5頁仲愷農業(yè)工程學院實驗報告紙仲愷農業(yè)工程學院實驗報告紙（院、系）專業(yè)班組課學號姓名實驗日期教師評定實驗四實驗四圖的建立及應用圖的建立及應用一、實驗目的1、掌握圖的存儲思想及其存儲實現。2、掌握圖的深度、廣度優(yōu)先遍歷算法思想及其程序實現。3、理解最小生成樹的有關概念以及普里姆算法和克魯斯卡爾算法的實現。4、理解最短路徑、拓樸排序、關鍵路徑算法及實現。二、實驗要求1、編寫程序實現圖的各種運算，并在此基礎上設計主函數，使其完成如下功

2、能：（1）建立無向圖（2）輸出無向圖對應的鄰接表。（3）實現深度遍歷和廣度遍歷。三、程序運算結果截圖四、程序源代碼#include#includeusingnamespacestd#defineN20typedefVertexTypetypedefstructArcNode第3頁共5頁voidvisit(VNG[]intv)coutadjdex查找頂點的第一條邊return1intNextAdj(VNG[]intv)ANpp=G[v].

3、firstarcwhile(pnext!=NULL)if(G[pnextadjdex].mark==true)查找頂點的下一條邊p=pnextelsereturnpnextadjdexreturn1voidVisit(VNG[]intn)intijwf(i=0ini)G[i].mark=falsef(i=0ini)cout“G[“i“]:“w=FirstAdj(Gi)while(w!=1)輸出鄰接表if(G[w].mark==false