數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--圖的遍歷和生成樹求解-資料下載頁
2025-06-03 14:11本頁面
【正文】 [i].data==e) return i。 } return 1。 } main() int main() { ALGraph A。 MGraph G。 圖的遍歷和生成樹求解 15 AdjMatrix S。 int n,v。 VertexType u。 printf(用圖的鄰接矩陣存儲結(jié)構(gòu)建無向網(wǎng) :\n)。 CreateUDN(G,S)。 printf(輸出鄰接矩陣： \n)。 Display(G,S)。 printf(用圖的鄰接表存儲結(jié)構(gòu)建無向網(wǎng)： \n)。 CreateALGraph(A)。 printf(輸出鄰接表： \n)。 DisplayG(A)。printf(\n)。 printf(輸入圖的結(jié)點(diǎn)個數(shù)以及訪問的起始結(jié)點(diǎn)的位序 (格式如： 2,1)： \n)。 scanf(%d,%d,amp。n,amp。v)。 printf(對圖進(jìn)行深度優(yōu)先遍歷（鄰接矩陣）： \n)。 DFS1(G,n,v)。 printf(\n)。 printf(對圖進(jìn)行深度優(yōu)先遍歷（鄰接表）： \n)。 DFS2(A,v)。 printf(\n)。 printf(對圖進(jìn)行廣度優(yōu)先遍歷（鄰接表）： \n)。 BFS(A,v)。 printf(\n)。 printf(利用 PRIM 算法求最小生成樹 \n)。 u=[1]。 MiniSpanTree_PRIM(G,S,u)。 printf(利用 Kruskal 算法求最小生成樹 \n)。 Kruskal(A)。 printf(\n)。 return OK。 圖的遍歷和生成樹求解 16 } 程序中需說明的地方，如用到的宏及代表的意義 define OK 1 define ERROR 0 define INFINITY 88 //最大值（表示無窮大） define MAX_VERTEX_NUM 20 //最大頂點(diǎn)個數(shù) define MAX_INFO 20 define MAX_NAME 5 typedef int Status。 typedef char VertexType。 typedef int VRType。 typedef char vertexType。 typedef char InfoType。 typedef enum{DG,DN,UDG,UDN}GraphKind。 //{有向圖 ,有向網(wǎng) ,無向圖 ,無向網(wǎng) } typedef int TElemType。 4. 結(jié)果與結(jié)論 ： ， 錄入數(shù)據(jù)及錄入結(jié)果如下： 圖的遍歷和生成樹求解 17 4．測試基于鄰接表構(gòu)造圖函數(shù) 5. 測試輸出鄰接表的函數(shù) 6. 測試基于鄰接矩陣對圖進(jìn)行深度優(yōu)先遍歷的函數(shù) 的函數(shù) Prim 算法求最小生成樹的函數(shù) 圖的遍歷和生成樹求解 18 Kruskal 算法求最小生成樹的函數(shù) 通 過以上程序演示的結(jié)果，其測試功能包含本次課程設(shè)計(jì)所要求的圖的主要功能，包括對圖的 深度遍歷、 廣度遍歷、 Prim 求最小生成樹、 Kruskal 求最小生成樹等功能。 1. 數(shù)據(jù)結(jié)構(gòu)的構(gòu)造及初始化無誤，能夠滿足對圖的遍歷和最小生成樹求解的要求。 2. 錄入數(shù)據(jù) 能夠驗(yàn)證其效果。 3. 鄰接矩陣的建立， 結(jié)果中鄰接矩陣的輸出結(jié)果能驗(yàn)證其效果。 4. 鄰接表的建立， 結(jié)果中鄰接表的輸出結(jié)果能驗(yàn)證其效果 。 。 5. 基于鄰接矩陣對圖的深度優(yōu)先遍歷，可以有預(yù)期的結(jié)果 6. 基于鄰接表對圖的廣度優(yōu)先 遍歷，可以有 預(yù) 期的結(jié)果 。 7. Prim 算法求 得 最小生成樹， 可以有預(yù)期的結(jié)果 。 8. Kruskal 算法求 得 最小生成樹， 可以有預(yù)期的結(jié)果 。 至此，本課程設(shè)計(jì)所提出的設(shè)計(jì)方法均得到有效的驗(yàn)證及證實(shí)，各個功能均能完成其設(shè)計(jì)需要，各部分功能之間能夠相互協(xié)調(diào)印證，整個設(shè)計(jì)的結(jié)果與預(yù)期相符。 但是，還存在需要改進(jìn)的地方，課程要求是隨機(jī)生成一個無向連通圖，而此程序是先 人 為構(gòu)建一個無向連通圖，然后對圖進(jìn)行遍歷和生成樹求解。 對于隨機(jī)生成無向連通圖，已有還不夠成熟的算法，由于時(shí)間有限，以后會對程序進(jìn)行改進(jìn)，已完成題目的要求。 圖的遍歷和生成樹求解 19 5. 收獲與致謝 本次實(shí)驗(yàn) 主要用到了數(shù)據(jù)結(jié)構(gòu)中 圖以及隊(duì)列 的相關(guān)知識，使我對數(shù)據(jù)結(jié)構(gòu)這門課程有了更加深入的學(xué)習(xí)和運(yùn)用，另外，在運(yùn)用數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問題的編程能力方面有了很大的提高，對于數(shù)據(jù)結(jié)構(gòu)的相關(guān)算法思想有了更深層次的理解，對于 C 語言程序設(shè)計(jì)的運(yùn)用有了進(jìn)一步第的鞏固和提高。 在對于編寫程序的上下連貫性有了進(jìn)一步的提高。與此同時(shí)，編寫程序會出現(xiàn)很多錯誤，對于調(diào)試程序，也使我進(jìn)一步了解了算法，培養(yǎng)了編程思想。 本次實(shí)驗(yàn)中，由于變量及相關(guān)的功能函數(shù)比較多，需要全面考慮問題，使我對問題的分析能力有了很大的幫助，通過對程序的編程和測試，使我對于 程序設(shè)計(jì)的周全思維提高很多。 誠然，我的多方面的提高，離不開老師的幫助，在此，我真誠地向指導(dǎo)教師閆老師表示真心的感謝！ 6. 參考文獻(xiàn) [1] 嚴(yán)蔚敏，吳偉民 . 數(shù)據(jù)結(jié)構(gòu)（ C 語言版） .清華大學(xué)出版社 [2]譚浩強(qiáng) .C 語言程序設(shè)計(jì) .清華大學(xué)出版社 [3]C++程序設(shè)計(jì)教程 —— 設(shè)計(jì)思想與實(shí)現(xiàn) 錢能 著 清華大學(xué)出版社 [4]C 語言程序設(shè)計(jì) —— 現(xiàn)代方法 [美 ] 著 人民郵電出版社
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1