樹的遍歷與生成樹ppt課件-文庫(kù)吧資料
2025-01-20 22:10本頁(yè)面
【正文】 Trees O(e)或 O(n2) ?思路：首先按照寬度優(yōu)先搜索獲得簡(jiǎn)單圖的一個(gè)根樹，根樹對(duì)應(yīng)的無(wú)向圖即簡(jiǎn)單圖的生成樹 ? BFS： ? 任選圖中一個(gè)頂點(diǎn)作為根，然后添加與這個(gè)頂點(diǎn)關(guān)聯(lián)的所有邊，添加的頂點(diǎn)成為生成樹在 1層的頂點(diǎn)（任意排序） ? 按順序訪問(wèn) 1層上的每個(gè)頂點(diǎn)：只要不產(chǎn)生回路，就將與這個(gè)頂點(diǎn)相關(guān)聯(lián)的每條邊添加到樹，產(chǎn)生 2層的頂點(diǎn) ? 遵循相同的過(guò)程，直到已經(jīng)添加了所有頂點(diǎn) ?因?yàn)?BFS的結(jié)果無(wú)回路，且是包含所有頂點(diǎn)的連通圖，故是圖的生成樹 ? 生成樹的建立方法 — 寬度優(yōu)先搜索 breadthfirst search 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 例 3 用寬度優(yōu)先搜索找出下圖的生成樹 ? 生成樹的建立方法 — 寬度優(yōu)先搜索 breadthfirst search 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees O(e)或 O(n2) ? 生成樹的建立方法 — 寬度優(yōu)先搜索 breadthfirst search 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 問(wèn)題 ：一個(gè)公司建立一個(gè)通信網(wǎng)絡(luò)來(lái)連接它的五個(gè)計(jì)算機(jī)中心，可以租用電話線連接這些中心的任何一對(duì)，應(yīng)當(dāng)建立哪些連接，以便保證任兩個(gè)計(jì)算機(jī)中心都有通路，且網(wǎng)絡(luò)成本最??？ ? 頂點(diǎn)：計(jì)算機(jī)中心 ? 邊：可能租用的電話線 ? 邊上的權(quán)：月租費(fèi) —— 求圖的生成樹 —— 求最小生成樹 [定義 ] 最小生成樹：設(shè)連通加權(quán)圖 G=(V, E, W)， T=(V, E39。 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees ?為了從源計(jì)算機(jī)發(fā)送數(shù)據(jù)到多個(gè)接收計(jì)算機(jī)（一個(gè)子網(wǎng)），可以分別發(fā)送數(shù)據(jù)到每個(gè)計(jì)算機(jī) —— 單點(diǎn)廣播 ?但單點(diǎn)廣播是無(wú)效的，因?yàn)榫W(wǎng)絡(luò)上存有發(fā)送的相同數(shù)據(jù)的多個(gè)副本 ? 生成樹的應(yīng)用 —— IP組播 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 路由 子網(wǎng) 帶接收站的子網(wǎng) ?有效的方法 —— IP組播 ?源計(jì)算機(jī)在網(wǎng)絡(luò)上發(fā)送數(shù)據(jù)的單一副本，當(dāng)數(shù)據(jù)到達(dá)中間路由器時(shí)，就把數(shù)據(jù)分發(fā)到一個(gè)或更多的其他路由器，以便接收計(jì)算機(jī)都可在它們不同的子網(wǎng)里最終接收到數(shù)據(jù) ? 生成樹的應(yīng)用 —— IP組播 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 路由 子網(wǎng) 帶接收站的子網(wǎng) ?為了讓數(shù)據(jù)盡可能快地到達(dá)接收計(jì)算機(jī)，在數(shù)據(jù)穿過(guò)網(wǎng)絡(luò)的通路里不應(yīng)當(dāng)存在環(huán)路 ?以組播源、路由器和包含接收計(jì)算機(jī)的子網(wǎng)作為頂點(diǎn)，以邊表示計(jì)算機(jī)和 /或路由器之間的連接，構(gòu)造 IP網(wǎng)絡(luò)的生成樹 ? 生成樹的應(yīng)用 —— IP組播 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 路由 子網(wǎng) 帶接收站的子網(wǎng) ?思路：首先按照深度優(yōu)先搜索獲得簡(jiǎn)單圖的一個(gè)根樹，根樹對(duì)應(yīng)的無(wú)向圖即簡(jiǎn)單圖的生成樹 ? DFS：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1