樹的遍歷與生成樹ppt課件(編輯修改稿)
2025-02-10 22:10 本頁面
【文章內(nèi)容簡介】 譯系統(tǒng)； 作業(yè) P333 ： 針對 4題的圖寫出前序遍歷、中序遍歷和后序遍歷的頂點順序。 8,11(a) Chap 7 樹 ? 樹的概念 /Introduction of Trees ? 樹的應用 /Applications of Trees ? 樹的遍歷 /Tree Traversal ? 生成樹和最小生成樹 / Spanning Trees and minimum Spanning Trees 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 緬因州的道路系統(tǒng)圖 確保任兩個鄉(xiāng)鎮(zhèn)都有通路，且不能有多余的邊。 求一個包含該圖所有頂點的樹（ 5條邊） [定義 1]生成樹：無向簡單圖 G=(V, E) 的生成子圖 T是樹，則稱 T為 G的 生成樹 /spanning tree。 T=(V, E39。), E39。?E 例 1 找出下面簡單圖的生成樹。 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 證明： 必要性 ： T是生成子圖，包含 G的所有頂點， T是樹， T連通，則 G連通。 充分性 ：若 G是連通的 , 1) 若 G無回路，則 G本身是樹，即生成樹。 2) 若存在回路，去掉回路中任一邊，不影響連通性，也不減少頂點 . 所有回路都移去一條邊，剩下的子圖包含所有頂點，又是無回路的連通圖，即為生成樹。 注：移去邊時可隨意 ， 故生成樹不唯一 。 [定理 1] 無向簡單圖 G=(V, E)存在生成樹的充要條件是G是連通的 。 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees ?為了從源計算機發(fā)送數(shù)據(jù)到多個接收計算機（一個子網(wǎng)），可以分別發(fā)送數(shù)據(jù)到每個計算機 —— 單點廣播 ?但單點廣播是無效的，因為網(wǎng)絡上存有發(fā)送的相同數(shù)據(jù)的多個副本 ? 生成樹的應用 —— IP組播 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 路由 子網(wǎng) 帶接收站的子網(wǎng) ?有效的方法 —— IP組播 ?源計算機在網(wǎng)絡上發(fā)送數(shù)據(jù)的單一副本，當數(shù)據(jù)到達中間路由器時，就把數(shù)據(jù)分發(fā)到一個或更多的其他路由器，以便接收計算機都可在它們不同的子網(wǎng)里最終接收到數(shù)據(jù) ? 生成樹的應用 —— IP組播 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 路由 子網(wǎng) 帶接收站的子網(wǎng) ?為了讓數(shù)據(jù)盡可能快地到達接收計算機，在數(shù)據(jù)穿過網(wǎng)絡的通路里不應當存在環(huán)路 ?以組播源、路由器和包含接收計算機的子網(wǎng)作為頂點，以邊表示計算機和 /或路由器之間的連接，構(gòu)造 IP網(wǎng)絡的生成樹 ? 生成樹的應用 —— IP組播 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 路由 子網(wǎng) 帶接收站的子網(wǎng) ?思路：首先按照深度優(yōu)先搜索獲得簡單圖的一個根樹，根樹對應的無向圖即簡單圖的生成樹 ? DFS： ? 任選圖中一個頂點作為根，通過相繼添加邊來形成從這個頂點開始的通路，其中每條新邊都與通路上的最后一個頂點以及還不在通路上的一個頂點關聯(lián)。
教學課件相關推薦
鄂ICP備17016276號-1