數據結構 無向圖的存儲和遍歷

《數據結構 無向圖的存儲和遍歷》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、《數據結構》實驗報告◎實驗題目:無向圖的存儲和遍歷◎實驗目的：1、掌握使用VisualC++6.0上機調試程序的基本方法；2、掌握圖的鄰接表存儲結構和深度優(yōu)先遍歷的非遞歸算法。3、提高自己分析問題和解決問題的能力，在實踐中理解教材上的理論。◎實驗內容：建立有10個頂點的無向圖的鄰接表存儲結構，然后對其進行深度優(yōu)先遍歷，該無向圖可以是無向連通圖或無向非連通圖。一、需求分析1、輸入的形式和輸入值的范圍：根據提示，首先輸入圖的所有邊建立鄰接表存儲結構，然后輸入遍歷的起始頂點對圖或非連通圖的某一連通分量進行遍歷。2、輸出

2、的形式：輸出對該圖是連通圖或非連通圖的判斷結果，若是非連通圖則輸出各連通分量的頂點，之后輸出隊連通圖或非連通圖的某一連通分量的遍歷結果。3、程序所能達到的功能：輸入圖的所有邊后，建立圖的鄰接表存儲結構，判斷該圖是連通圖或非連通圖，最后對圖進行遍歷。4、測試數據：輸入10個頂點（空格分隔）:ABCDEFGHIJ輸入邊的信息（格式為xy）:ABACAFCEBDDCHGGIIJHJEH該圖為連通圖,請輸入遍歷的起始頂點:A遍歷結果為:AFCDBEHJIG是否繼續(xù)？（是,輸入1;否,輸入0）:1輸入10個頂點（空格分隔）

3、:ABCDEFGHIJ輸入邊的信息（格式為xy）:ABACCECAAFHGHJIJIG該圖為非連通圖,各連通分量中的頂點為:輸入第1個連通分量起始頂點:F第1個連通分量的遍歷結果為:FACEB輸入第2個連通分量起始頂點:I第2個連通分量的遍歷結果為:IGHJ輸入第3個連通分量起始頂點:D第3個連通分量的遍歷結果為:D是否繼續(xù)？（是,輸入1;否,輸入0）:0謝謝使用!Pressanykeytocontinue二概要設計1、鄰接表是圖的一種順序存儲與鏈式存儲結構結合的存儲方法。鄰接表表

4、示法類似于樹的孩子鏈表表示法。就是對圖G中的每個頂點Vi，將所有鄰接于Vi的頂點Vj鏈成一個單鏈表，這個單鏈表就稱為頂點Vi的鄰接表，再將所有鄰接表的表頭放到數組中，就構成了圖的鄰接表，鄰接表表示中的兩種結點結構如下所示。一種頂點表的結點結構，它由頂點域(vertex)和指向第一條鄰接邊的指針域(firstedge)構成，另一種是邊表（即鄰接表）結點，它由鄰接點域(adjvex)和指向下一條鄰接邊的指針域(next)構成。2、無向圖的建立輸入頂點后，將頂點信息存入頂點表的頂點域。在輸入邊的信息后，如輸入的一條邊為

5、XY，則生成新的邊表結點，將其插入到頂點X的邊表頭部，同理，生成新的邊表結點，將其插入到頂點Y的邊表頭部。最終完成圖的建立。3、圖的深度優(yōu)先遍歷設p為指向邊表結點的指針，首先訪問圖的指定的起始頂點V，從V出發(fā)訪問一個與V鄰接的p所指的頂點，并將其壓入棧中，再從p所指定點出發(fā)，訪問與p所指頂點鄰接且未被訪問的頂點，以后從該頂點出發(fā)。重復上述過程，知道找不到存在未訪問過的鄰接頂點為止。之后執(zhí)行出棧操作，退回到尚有未訪問過的鄰接點的頂點，從該頂點出發(fā)，重復之前所述的操作，知道所有被訪問過的頂點的鄰接點都已被訪問為止。下

6、圖中的深度優(yōu)先遍歷結果為ABDCEHJIGF，AFCEHGIJDB等。4、本程序的基本操作和模塊：確定頂點所對應的下標的函數：locate(ALGraph&G,charch)建立圖的鄰接表存儲結構的函數：Create(ALGraph&G,SeqStack&s)深度優(yōu)先遍歷的函數：DFS(ALGraph&G,intv,SeqStack&s,intvisited[],inttag)判斷圖是否連通的函數：Judge(ALGraph&G,intvisited[],SeqStack&s)確定非連通圖連通分量值的函數：Get

7、(ALGraph&G,intvisited[],SeqStack&s)主函數：main()函數的調用關系如下圖所示:三詳細設計（一）元素類型、結點類型1、鄰接表的表示形式描述typedefstructnode//邊表結點{intadjvex;//鄰接點域structnode*next;//指向下一個鄰接點的指針域}EdgeNode;typedefstructvnode//頂點表結點{charvertex;//頂點域EdgeNode*firstedge;//邊表頭指針}VertexNode;typedefVerte

8、xNodeAdjList[10];//AdjList是鄰接表類型typedefstruct//以鄰接表方式存儲的圖類型{AdjListadjlist;//鄰接表inte;//圖的邊數}ALGraph;1、順序棧的類型描述typedefstruct//存放訪問過的結點的棧{EdgeNode*pin[10];//存放邊表結點的指針inttop;//棧頂指針}SeqStack;