平面嵌入-資料下載頁(yè)
2025-07-19 00:10本頁(yè)面
【正文】 可能學(xué)完所有的算法 ,但是只有不斷的汲取 ,才能提高和完善自己 . 謝謝 ! 快速翻轉(zhuǎn) 當(dāng)進(jìn)入子塊進(jìn)行遍歷會(huì)從新選擇方向 ,當(dāng)選擇方向與原有方向不同時(shí) ,就需要進(jìn)行翻轉(zhuǎn)操作 . 對(duì)外部面 O(1)的翻轉(zhuǎn) : ?只需要交換塊根節(jié)點(diǎn)的兩個(gè)方向的指示 . 在以后的遍歷中 ,只需要知道由哪一個(gè)節(jié)點(diǎn)到達(dá) ,并且走向下一節(jié)點(diǎn) . 快速翻轉(zhuǎn) 對(duì)鄰接表的翻轉(zhuǎn) : ?對(duì)于節(jié)點(diǎn)的子塊 ,如果翻轉(zhuǎn) ,將該節(jié)點(diǎn)與子塊中唯一的兒子相連的樹(shù)邊標(biāo)記為 1. 最后對(duì)圖只經(jīng)過(guò)樹(shù)邊進(jìn)行一次深搜 ,當(dāng)?shù)竭_(dá)節(jié)點(diǎn)經(jīng)過(guò)了奇數(shù)個(gè) 1,就將節(jié)點(diǎn)的鄰接表前后顛倒 . 相關(guān)信息的取得 walkup — 向上遍歷 : 存在回落邊 (v,w),從 w開(kāi)始沿著外部面向上遍歷到 v.并且給每個(gè)節(jié)點(diǎn)配備一個(gè) proots,表示它有哪些塊包含相關(guān)節(jié)點(diǎn) . ?從外部面的兩個(gè)方向同時(shí)遍歷 . ?遇到遍歷過(guò)的點(diǎn)就停止遍歷 . ?在從節(jié)點(diǎn)的子塊上升到該節(jié)點(diǎn)時(shí) ,將該子塊加入到節(jié)點(diǎn)的 proots中 . 相關(guān)信息的取得 在向 proots中加入子塊的時(shí)候 .為了保證法則 1,進(jìn)行這樣的操作 : ?不包含外部活躍節(jié)點(diǎn)的塊所包含的節(jié)點(diǎn) lowpoint一定小于 v的深度 .所以將所包含的 lowpoint都小于 v的深度的子塊加入節(jié)點(diǎn)的 proots表頭 ,否則加入表尾 . 然后按順序處理節(jié)點(diǎn)的 proots. 相關(guān)信息的取得 v v’ s s1 w s2 k s
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1