樹的遍歷與生成樹ppt課件-資料下載頁
2025-01-14 22:10本頁面
【正文】 最小生成樹 Spanning Trees and minimum Spanning Trees 普林算法 Prim39。s algorithm： ? 首先選擇帶最小權的邊，把它放進生成樹里 ? 相繼地向樹里添加與已在樹里的頂點關聯(lián)的、并且不與已在樹里的邊形成簡單回路的權最小的邊 ? 當已經添加了 n1條邊時就停止。 procedure Prim ( G : 帶 n個頂點的連通無向圖 ) T := 權最小的邊 for i:= 1 to n2 begin e := 與 T里頂點關聯(lián)、且若添加到 T里則不形成簡單回路的權最小的邊 T := 添加 e之后的 T end {T 是 G的最小生成樹 } 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 例 4 用普林算法求下圖的最小生成樹 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 例 5 用普林算法求下圖的最小生成樹 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 克魯斯卡爾算法 Kruskal39。s algorithm： ? 添加圖中權最小的一條邊到生成樹 ? 相繼添加不與已經選擇的邊形成簡單回路的權最小的邊 ? 在已經挑選了 n1條邊之后停止 procedure Kruskal(G : 帶 n個頂點的帶權連通無向圖 ) T :=空圖 for i : = 1 to n1 begin e := 當添加到 T里不形成簡單回路的 G中權最小邊 T := 添加 e之后的 T end {T 是 G的最小生成樹 } 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 例 6 用克魯斯卡爾算法求下圖的最小生成樹 生成樹不唯一，但每個最小生成樹的權都是相等的??！ 12 2 3 10 7 1 9 5 6 8 11 4 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 例 7 用克魯斯卡爾算法求下圖的最小生成樹 解題過程： (1）邊排序 :(v1,v2),(v2,v7),(v1,v6),(v6,v7) (v1,v4),(v5,v6),(v4,v5),(v3,v4),(v3,v8) (v5,v8),(v2,v3),(v7,v8) (2) 選 s1={e1} e1=(v1,v2) (3) 選 e2=(v2,v7) (4) e3=(v1,v6) (5) e4=(v1,v4)=5 (6) e5=(v5,v6)=6 (7) e6=(v3,v4)=8 (8) e7=(v3,v8) 小 結 生成樹的定義與存在的充分必要條件 生成樹的深度優(yōu)先搜索 DFS和寬度優(yōu)先搜索 BFS解法 最小生成樹的定義與求法（ Prim、 Kruskal算法） 進一步的思考 求最小生成樹的其他方法 最大生成樹問題 作業(yè) P342：用 DFS和 BFS求 2題中簡單圖的生成樹 P347： 4
教學課件相關推薦
鄂ICP備17016276號-1