數(shù)據結構第章習題答案(編輯修改稿)
2025-07-04 19:56 本頁面
【文章內容簡介】 e,f,g,h}Vexlowcost000d7d6d50{a,c,b,d ,h }{e,f,g }Vexlowcost000d7g200{a,c,b,d ,h ,g}{ f,e }Vexlowcost000f3000{a,c,b,d ,h ,g, f }{e }Vexlowcost0000000{a,c,b,d ,h ,g, f, e }{ }鄰接表為：a→b4→c3b→a4→c5→d5→e9^c→a3→b5→d5→h5^d→b5→c5→e7→f6→g5→h4^e→b9→d7→f3^f→d6→e3→g2^g→d5→f2→h6^h→c5→d4→g6^克魯斯卡爾算法步驟(按邊歸并,堆排序)：先羅列：f2g a—3c f—3—e a—4b d—4—h (a,b,c) (e,f,g) (d,h) 取b—5—d, g—5d 就把三個連通分量連接起來了。3. 【②】已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點1出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。4. 【②】試利用Dijkstra算法求圖中從頂點a到其他各頂點間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)。解：最短路徑為：（a,c,f,e,d,g,b） 四、 【2001年計考研題】給定下列網G: （10分） 1 試著找出網G的最小生成樹，畫出其邏輯結構圖；2 用兩種不同的表示法畫出網G的存儲結構圖；3 用C語言（或其他算法語言）定義其中一種表示法（存儲結構）的數(shù)據類型。A B———————C E————F G————D解：1. 最小生成樹可直接畫出，如右圖所示。2. 可用鄰接矩陣和鄰接表來描述：描述存儲結構的數(shù)據類型可參見教材或電子教案：注：用兩個數(shù)組分別存儲頂點表和鄰接矩陣define INFINITY INT_MAX //最大值∞define MAX_VERTEX_NUM 20 //假設的最大頂點數(shù)（可取為7）Typedef enum {DG, DN, AG,AN } GraphKind。 //有向/無向圖，有向/無向網Typedef struct ArcCell{ //弧（邊）結點的定義 VRType adj。 //頂點間關系，無權圖取1或0
教學教案相關推薦
鄂ICP備17016276號-1