最小生成樹和最短路徑-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-展示頁
2025-07-02 20:11本頁面
【正文】 =0,j,k,min。 VRType lowcost。 return OK。 [i][j].adj=[j][i].adj=w。 /* %*c吃掉回車符 */ i=LocateVex(G,va)。++k) { scanf(%s%s%d%*c,va,vb,amp。 for(k=0。++j) { [i][j].adj=INFINITY。++i) /* 初始化鄰接矩陣 */ for(j=0。 for(i=0。i。用空格隔開):\n,MAX_NAME)。)。 scanf(%d,%d,amp。 VertexType va,vb。 }Status CreateAN(MGraph amp。++i) if(strcmp(u,[i])==0) return i。 for(i=0。 int LocateVex(MGraph G,VertexType u) { /* 初始條件:圖G存在,u和G中頂點(diǎn)有相同特征 */ /* 操作結(jié)果:若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中位置。 /* 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) */ GraphKind kind。 /* 頂點(diǎn)向量 */ AdjMatrix arcs。 /* 該弧相關(guān)信息的指針(可無) */}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。 /* 頂點(diǎn)關(guān)系類型。/*圖的數(shù)組(鄰接矩陣)存儲表示 */define INFINITY INT_MAX /* 用整型最大值代替∞ */define MAX_VERTEX_NUM 20 /* 最大頂點(diǎn)個數(shù) */typedef enum{DG,DN,AG,AN}GraphKind。typedef char InfoType。typedef int Boolean。b. 依次從E中取出一條邊(i,j)，檢查頂點(diǎn)i和j是否屬于同一連通分量，如是，則重取下一條邊；否則，該邊即為生成樹的一條邊，輸出該邊，同時將所有與j處于同一連通分量的頂點(diǎn)的Vset值都修改為與i的相同。(2) 對于上圖，采用克魯斯卡爾算法輸出該圖的最小生成樹。實(shí)驗(yàn)報(bào)告六月 182015姓名：陳斌 學(xué)號：E11314079 專業(yè)：13計(jì)算機(jī)科學(xué)與技術(shù)數(shù)據(jù)結(jié)構(gòu) 第八次實(shí)驗(yàn) 學(xué)號 E11314079 專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 姓名 陳 斌 實(shí)驗(yàn)日期 教師簽字 成績 實(shí) 驗(yàn) 報(bào) 告【實(shí)驗(yàn)名稱】 最小生成樹和最短路徑 【實(shí)驗(yàn)?zāi)康摹?(1) 掌握最小生成樹以及最短路徑的相關(guān)概念；(2) 掌握Prim算法和Kruskal算法；(3) 掌握Dijkstra算法【實(shí)驗(yàn)內(nèi)容】l 采用普里姆算法求最小生成樹(1) 編寫一個算法，(a)所示的無向帶權(quán)圖G采用普里姆算法輸出從頂點(diǎn)V1出發(fā)的最小生成樹。圖的存儲結(jié)構(gòu)自選。（提示：，得有序邊集E；為所有頂點(diǎn)輔設(shè)一個數(shù)組Vset，標(biāo)記各頂點(diǎn)所處的連通分量，初始時各不相同。） 源代碼：: includeincludeinclude //malloc( )include // INT ,MAXinclude //EOF,NULLinclude //atoi( )include //eof( )include //floor( ),ceil( ),abs( )include //exit( )include //cout,cin//函數(shù)結(jié)果狀態(tài)代碼define TRUE 1define FALSE 0define OK 1define ERROR 0define INFEASIBLE 1//OVERFLOW 在 中已定義為3typedef int Status。 // 布爾類型:includetypedef int VRType。define MAX_NAME 3 /* 頂點(diǎn)字符串的最大長度+1 */define MAX_INFO 20 /* 相關(guān)信息字符串的最大長度+1 */typedef char VertexType[MAX_NAME]。 /* {有向圖,有向網(wǎng),無向圖,無向網(wǎng)} */typedef struct{ VRType adj。對無權(quán)圖，用1(是)或0(否)表示相鄰否； */ /* 對帶權(quán)圖，c則為權(quán)值類型 */ InfoType *info。typedef struct{ VertexType vexs[MAX_VERTEX_NUM]。 /* 鄰接矩陣 */ int vexnum,arum。 /* 圖的種類標(biāo)志 */}MGraph。否則返回1 */ int i。i。 return 1。G) { /* 采用數(shù)組(鄰接矩陣)表示法,構(gòu)造無向網(wǎng)G*/ int i,j,k,w。 printf(請輸入無向網(wǎng)G的頂點(diǎn)數(shù) 邊數(shù)(用逗號隔開):)。,amp。 printf(請輸入%d個頂點(diǎn)的值(%d個字符。 for(i=0。++i) /* 構(gòu)造頂點(diǎn)向量 */ scanf(%s,[i])。i。j。 /* 網(wǎng) */ } printf(
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1