數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--圖的遍歷和生成樹求解-閱讀頁
2025-01-31 14:20本頁面
【正文】 n OK。//初始化標(biāo)志數(shù)組Status BFS(ALGraph G,int v){//基于鄰接表，對(duì)無向圖G進(jìn)行廣度優(yōu)先搜索 int u, w。 InitQueue(Q)。 printf(%c\t,[v].data)。 while(!QueueEmpty(Q)) { DeQueue(Q,u)。w=0。 printf(%c\t,[w].data)。 } } } return OK。 Closedge closedge。 for(j=1。j++) { if(j!=k) { closedge[j].adjvex=u。// 輔助數(shù)組初始化 } }closedge[j].adjvex = 39。closedge[j].lowcost = 88。closedge[k].lowcost=0。for(i=2。++i){//k=minimum(closedge)。//輸出生成樹的邊closedge[k].lowcost=0。j=。 closedge[j].lowcost=GA[k][j].adj。}(ALGraph G)Status Kruskal(ALGraph G){ int i,j,min = INFINITY,k = 1。//用于判斷兩個(gè)點(diǎn)是否在同一集合里 ArcNode *p,*q,*s。 i = 。//初始化，將每個(gè)點(diǎn)自身作為一個(gè)集合 while(kamp。k= ) { for(i = 1。 ++i) { if([i].firstarc!=NULL) {//若第i+1個(gè)點(diǎn)沒有鄰邊，則下一循環(huán) for(p=[i].firstarc。p=pnextarc)//查找最小權(quán)值的邊 if(pweight min) { min = pweight。 j = i。 //ifelse用于刪除最小權(quán)值的邊 else { for(p = [j].firstarc。 p = pnextarc) s = p。 } if(set[j]!=set[qadjvex]) {//判斷兩點(diǎn)是否在同一集合,若不在，則輸出這條邊 printf((%c,%c) %d\n,[j].data,[qadjvex].data,qweight)。 /*int s2=set[j]。i=。 } min = INFINITY。}(MGraph G,VertexType u)，LocateVexG(ALGraph G,vertexType e)Status LocateVex(MGraph G,VertexType u){ int i。i=。 return 1。i=。} return 1。 MGraph G。 int n,v。 printf(用圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)建無向網(wǎng):\n)。 printf(輸出鄰接矩陣：\n)。 printf(用圖的鄰接表存儲(chǔ)結(jié)構(gòu)建無向網(wǎng)：\n)。 printf(輸出鄰接表：\n)。printf(\n)。 scanf(%d,%d,amp。v)。 DFS1(G,n,v)。 printf(對(duì)圖進(jìn)行深度優(yōu)先遍歷（鄰接表）：\n)。 printf(\n)。 BFS(A,v)。 printf(利用PRIM算法求最小生成樹\n)。 MiniSpanTree_PRIM(G,S,u)。 Kruskal(A)。 return OK。 typedef char VertexType。typedef char vertexType。typedef enum{DG,DN,UDG,UDN}GraphKind。4. 結(jié)果與結(jié)論：，錄入數(shù)據(jù)及錄入結(jié)果如下：4．測(cè)試基于鄰接表構(gòu)造圖函數(shù)5. 測(cè)試輸出鄰接表的函數(shù)6. 測(cè)試基于鄰接矩陣對(duì)圖進(jìn)行深度優(yōu)先遍歷的函數(shù)通過以上程序演示的結(jié)果，其測(cè)試功能包含本次課程設(shè)計(jì)所要求的圖的主要功能，包括對(duì)圖的深度遍歷、廣度遍歷、Prim求最小生成樹、Kruskal求最小生成樹等功能。2. 錄入數(shù)據(jù)能夠驗(yàn)證其效果。4. 鄰接表的建立，結(jié)果中鄰接表的輸出結(jié)果能驗(yàn)證其效果。7. Prim算法求得最小生成樹，可以有預(yù)期的結(jié)果。至此，本課程設(shè)計(jì)所提出的設(shè)計(jì)方法均得到有效的驗(yàn)證及證實(shí)，各個(gè)功能均能完成其設(shè)計(jì)需要，各部分功能之間能夠相互協(xié)調(diào)印證，整個(gè)設(shè)計(jì)的結(jié)果與預(yù)期相符。對(duì)于隨機(jī)生成無向連通圖，已有還不夠成熟的算法，由于時(shí)間有限，以后會(huì)對(duì)程序進(jìn)行改進(jìn)，已完成題目的要求。在對(duì)于編寫程序的上下連貫性有了進(jìn)一步的提高。本次實(shí)驗(yàn)中，由于變量及相關(guān)的功能函數(shù)比較多，需要全面考慮問題，使我對(duì)問題的分析能力有了很大的幫助，通過對(duì)程序的編程和測(cè)試，使我對(duì)于程序設(shè)計(jì)的周全思維提高很
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1