普里姆算法生成最小生成樹課程設(shè)計(jì)(編輯修改稿)
2024-07-24 10:19 本頁面
【文章內(nèi)容簡(jiǎn)介】 第 9 頁 共 29 頁3 數(shù)據(jù)結(jié)構(gòu)分析 存儲(chǔ)結(jié)構(gòu)定義鄰接矩陣及鄰接表的結(jié)構(gòu)體（1）鄰接矩陣define MaxVertexNum 100define max 1000typedef int VertexType。typedef int EdgeType。typedef struct { VertexType vexs[MaxVertexNum]。 EdgeType edges[MaxVertexNum][MaxVertexNum]。 int n,e。 }MGraph。（2）鄰接表define MaxVertexNum 100typedef int vertextype。typedef struct node{ int adjvex。第 10 頁 共 29 頁 int weight。 struct node *next。 }edgenode。typedef struct vnode{ vertextype vertex。 edgenode *firstedges。 }vertexnode。typedef vertexnode AdjList[MaxVertexNum]。typedef struct { AdjList adjlist。 int n,e。}ALgraph。(3)鄰接表轉(zhuǎn)換成鄰接矩陣輔助結(jié)構(gòu)體typedef int edgetype 。typedef struct{ edgetype vexs[MaxVertexNum]。 edgetype edges[MaxVertexNum][MaxVertexNum]。 int n,e。 }graph。 /*鄰接表轉(zhuǎn)換成鄰接矩陣輔助結(jié)構(gòu)體*/第 11 頁 共 29 頁 算法描述1. 創(chuàng)建有向網(wǎng)圖鄰接矩陣存儲(chǔ)void CreateMGraph(MGraph *G){ int i,j,k,weight。 printf(\t==有向網(wǎng)圖鄰接矩陣==\n)。printf(請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：)。 scanf(%d,%d,amp。(Gn),amp。(Ge))。 printf(請(qǐng)輸入頂點(diǎn)信息:)。 for (i=0。iGn。i++) scanf(\n%d,amp。(Gvexs[i]))。 for (i=0。iGn。i++) for (j=0。jGn。j++){ if(i==j) Gedges[i][j]=0。 else Gedges[i][j]=max。} /*初始化鄰接矩陣*/ printf(輸入邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)的序號(hào)及權(quán)值：)。 for (k=0。kGe。k++){ scanf(\n%d,%d,%d,amp。i,amp。j,amp。weight)。 Gedges[i][j]=weight。第 12 頁 共 29 頁 } printf(輸出頂點(diǎn)信息及鄰接矩陣 :\n )。 OutPut(G)。 printf(輸出最小生成樹的信息 :\n)。 prim(Gedges,Gn,Gvexs)。}2. 創(chuàng)建無向網(wǎng)圖鄰接矩陣存儲(chǔ)void CreateGraph(MGraph *G){ int i,j,k,weight。 printf(\t==無向網(wǎng)圖鄰接矩陣==\n)。 printf(請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：)。 scanf(%d,%d,amp。(Gn),amp。(Ge))。 printf(請(qǐng)輸入頂點(diǎn)信息:)。 for (i=0。iGn。i++) scanf(\n%d,amp。(Gvexs[i]))。 for (i=0。iGn。i++) for (j=0。jGn。j++){ if(i==j) Gedges[i][j]=0。 else Gedges[i][j]=max。} /*初始化鄰接矩陣*/第 13 頁 共 29 頁 printf(輸入邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)的序號(hào)及權(quán)值：)。 for (k=0。kGe。k++){ scanf(\n%d,%d,%d,amp。i,amp。j,amp。weight)。 Gedges[i][j]=weight。 Gedges[j][i]=weight。 } printf(輸出頂點(diǎn)信息及鄰接矩陣:\n )。 OutPut(G)。 printf(輸出最小生成樹的信息:\n)。 prim(Gedges,Gn,Gvexs)。} 3. 創(chuàng)建有向網(wǎng)圖鄰接表存儲(chǔ)void createAgraph( ALgraph *g) /*創(chuàng)建有向網(wǎng)圖*/{ int i,j,k,w。 edgenode *s。 printf(\t==有向網(wǎng)圖鄰接表==\n)。 printf(輸入頂點(diǎn)數(shù)和邊數(shù):)。 scanf(%d,%d%*c,amp。(g
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1