數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--圖的遍歷和生成樹求解-wenkub.com
2025-05-30 14:11 本頁面
【正文】 與此同時，編寫程序會出現(xiàn)很多錯誤，對于調(diào)試程序，也使我進一步了解了算法，培養(yǎng)了編程思想。 但是，還存在需要改進的地方，課程要求是隨機生成一個無向連通圖，而此程序是先 人 為構(gòu)建一個無向連通圖，然后對圖進行遍歷和生成樹求解。 5. 基于鄰接矩陣對圖的深度優(yōu)先遍歷，可以有預(yù)期的結(jié)果 6. 基于鄰接表對圖的廣度優(yōu)先 遍歷，可以有 預(yù) 期的結(jié)果 。 2. 錄入數(shù)據(jù) 能夠驗證其效果。 typedef enum{DG,DN,UDG,UDN}GraphKind。 typedef char VertexType。 Kruskal(A)。 printf(利用 PRIM 算法求最小生成樹 \n)。 printf(\n)。 DFS1(G,n,v)。 scanf(%d,%d,amp。 printf(輸出鄰接表： \n)。 printf(輸出鄰接矩陣： \n)。 int n,v。 } return 1。 return 1。 } 13. 求 頂 點 在 圖 中 位 置 LocateVex(MGraph G,VertexType u) ，LocateVexG(ALGraph G,vertexType e) Status LocateVex(MGraph G,VertexType u) { int i。i=。 } if(set[j]!=set[qadjvex]) {//判斷兩點是否在同一集合 ,若不在，則輸出這條邊 printf((%c,%c) %d\n,[j].data,[qadjvex].data,qweight)。 //ifelse 用于刪除最小權(quán)值的邊 else { for(p = [j].firstarc。p=pnextarc)//查找最小權(quán)值的邊 if(pweight min) { min = pweight。k= ) { for(i = 1。 i = 。 } 求生成樹 Kruskal(ALGraph G) Status Kruskal(ALGraph G) { int i,j,min = INFINITY,k = 1。j=。++i) {//選擇其余的 個頂點 k=minimum(closedge)。 closedge[k].lowcost=0。// 輔助數(shù)組初始化 } 圖的遍歷和生成樹求解 12 } closedge[j].adjvex = 39。 for(j=1。 } } } return OK。w=0。 printf(%c\t,[v].data)。//初始化標志數(shù)組 Status BFS(ALGraph G,int v) {//基于鄰接表，對 無向圖 G 進行 廣度優(yōu)先搜索 int u, w。 if(==p) =。 if(!p) return ERROR。Q,int amp。 return OK。 pdata=e。Q,int e) Status EnQueue (LinkQueue amp。 return OK。Q) Status InitQueue (LinkQueue amp。amp。 visited[v]=1。 //初始化標志數(shù)組 Status DFS1(MGraph G,int n,int v) {//基于鄰接矩陣，對圖 G 進行深度優(yōu)先搜索 int j。 else printf([%d,%c,%d]/\\,padjvex,[padjvex].data,pweight)。 i=。 printf(\n)。i=。i=。 [j].firstarc=p。//將下標為 j 的結(jié)點連接在下標為 i 的結(jié)點 后面 p=(ArcNode*)malloc(sizeof(ArcNode))。 sadjvex=j。w)。k=。([i].data))。 printf(請輸入頂點信息： \n)。 scanf(%d,%d,amp。G) Status CreateALGraph(ALGraph amp。 j=LocateVex(G,v2)。v1,amp。 } } printf(請輸入 %d條邊的頂點 1頂點 2和權(quán)值 (以空格作為間隔 ):\n,)。i++) 圖的遍歷和生成樹求解 6 { for(j=1。[i])。 printf(請輸入 %d 個頂點的值 :\n,)。 printf(請輸入無向網(wǎng) G 的頂點數(shù) ,邊數(shù) :\n)。GA) Status CreateUDN(MGraph amp。 VRType lowcost。 typedef struct { QueuePtr front。 int vexnum,arum。 typedef struct VNode{//鄰接表頭結(jié)點的類型 vertexType data。//該弧所指向的頂點的位置 int weight。//鄰接矩陣 int vexnum,arum。 //VRType 是頂點關(guān)系類型，對無權(quán)圖，用 0 和 1；對有權(quán)圖，則為權(quán)值類型 圖的遍歷和生成樹求解 4 InfoType *info。Q) QueueEmpty (LinkQueue Q) EnQueue (LinkQueue amp。 CreateUDN(MGraph amp。 2)建立圖的存儲類型 MGraph,以及頂點向量 vexs[]。 圖的遍歷和生成樹求解 2 3）基于鄰接矩陣 存儲結(jié)構(gòu) ，用 prim 算法求圖的最小生成樹。 5）選擇適當 的變量，來表示
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1