計(jì)算機(jī)問題求解-2020-11-3圖的計(jì)算機(jī)表示及其遍歷

1、計(jì)算機(jī)問題求解 論題3-6 -圖的計(jì)算機(jī)表示以及遍歷2020年11月3日問題1:你能否根據(jù)這兩組圖解釋計(jì)算機(jī)中最主要的圖表示方式?問題2:我們討論表示方法是否合適主要根據(jù)什么?你能否結(jié)合上述兩種方式給以說明?關(guān)鍵操作的效率 vs. 存儲需求問題3:通常圖中與應(yīng)用相關(guān)的附加信息有些什么?他們對表示方法的選擇有什么影響?問題4:圖的搜索是什么意思?為什么它是用圖模型解決問題的基本操作?圖搜索經(jīng)常被稱為“遍歷”(traversal)廣度優(yōu)先兩組關(guān)鍵的動詞How？廣度優(yōu)先一定是棵樹嗎？一定最短嗎？顯然？問題5：圖搜索時用什么辦法來跟蹤搜索的進(jìn)度？白=灰=黑在將算法思想實(shí)現(xiàn)為程序時，需要提供哪些數(shù)據(jù)結(jié)構(gòu)

2、進(jìn)行過程控制？中間結(jié)果保存？最終結(jié)果展示？節(jié)點(diǎn)的顏色優(yōu)先隊(duì)列控制距離的記錄生成樹中父子關(guān)系實(shí)現(xiàn)了”系統(tǒng)地探索”，達(dá)成了“發(fā)現(xiàn)每一個”BFS算法框架：1，圖節(jié)點(diǎn)V-s初始化2，s節(jié)點(diǎn)初始化3，遍歷控制初始化（優(yōu)先隊(duì)列）4，遍歷 4.1 提取隊(duì)列頭節(jié)點(diǎn) 4.2 遍歷該節(jié)點(diǎn)的鄰接點(diǎn) 4.2.1 處理白節(jié)點(diǎn)的顏色、距離、父子關(guān)系 4.2.1 白節(jié)點(diǎn)入隊(duì) 4.3 修改該節(jié)點(diǎn)顏色問題7：u.，起到了什么作用？除了s節(jié)點(diǎn)的前驅(qū)是nil外，每個節(jié)點(diǎn)，有且僅有一個“前驅(qū)節(jié)點(diǎn)”任意節(jié)點(diǎn)v，沿其v.，必定找到一條從s到v的路徑Path問題8：v.d，起到了什么作用？v.d記錄了s節(jié)點(diǎn)到v節(jié)點(diǎn)路徑的長度v.d是原圖中

3、s節(jié)點(diǎn)到v節(jié)點(diǎn)的最短路徑嗎？問題9：為什么說廣度優(yōu)先搜索的代價(jià)是線性的？其問題規(guī)模是用什么參數(shù)表示的？問題10： 為什么我們在討論BFS算法時特別關(guān)注算法能夠正確計(jì)算出最短路徑距離？v.d 是(s,v)的上界我們要證明的結(jié)論“v.d =(s,v)” 和“v.d 是(s,v)的上界”有什么關(guān)系？v.d 是(s,v)的上界為什么？當(dāng)我們觀察隊(duì)列Q中元素的.d時，我們能發(fā)現(xiàn)什么規(guī)律？1，從隊(duì)列頭至隊(duì)列尾，.d是不減序的2，從隊(duì)列頭至隊(duì)列尾，.d相差最多為1一種遞歸的手法定義了最短路徑的獲得廣度優(yōu)先搜索計(jì)算最短路長度算法終止時證明要點(diǎn)：假設(shè)頂點(diǎn)v是不滿足上述條件的頂點(diǎn)中(s,v)值最小的一個，針對v用

4、反證法證明。設(shè)u是從s到v的最短路上v的直接前驅(qū)點(diǎn)，則Why？有什么價(jià)值？在一個連通圖中，選定一個起點(diǎn)總可以到達(dá)所有其它點(diǎn)，如果我們確保任一頂點(diǎn)只“到達(dá)”一次，則“經(jīng)過”的邊不會構(gòu)成回路。廣度與深度搜索所“經(jīng)過”的邊構(gòu)成的是原來圖的“生成樹”。Backtracking(回朔)廣度優(yōu)先深度優(yōu)先深度優(yōu)先搜索什么叫finished？如何從計(jì)算的角度判斷finish了？請?zhí)貏e關(guān)注回溯及回溯的數(shù)據(jù)表示郵戳數(shù)據(jù)提供了圖的重要結(jié)構(gòu)信息。何意？算法思想實(shí)現(xiàn)為程序時，遍歷管理和中間參數(shù)以及最終結(jié)果都需要哪些數(shù)據(jù)結(jié)構(gòu)？點(diǎn)的顏色、郵戳信息、父子關(guān)系沒有距離信息？沒有過程控制信息？深度優(yōu)先搜索顯然，不同的u的選擇，會

5、產(chǎn)生不同的遍歷森林！深度優(yōu)先搜索回溯去哪兒了？深度優(yōu)先搜索回溯去哪兒了？深度優(yōu)先搜索也是線性算法問題10：為什么對深度優(yōu)先需要引入“時間戳”？u.d 和u.f 的含義是什么？你能直觀解釋這個定理的含義嗎？圖中邊標(biāo)記中，BFC分別表示什么？問題11：你能解釋深度優(yōu)先搜索過程中，樹邊、FBC邊的標(biāo)定和頂點(diǎn)活動時間段之間的關(guān)系嗎？問題12：你能解釋深度優(yōu)先搜索在圖結(jié)構(gòu)發(fā)現(xiàn)上的作用嗎？白色路徑定理問題13：深度優(yōu)先搜索對于無向圖與有向圖有何不同？問題14:廣度優(yōu)先搜索是利用隊(duì)列實(shí)現(xiàn)的, 那深度優(yōu)先搜索用什么數(shù)據(jù)結(jié)構(gòu)呢?為什么有這樣的差別?問題15：從應(yīng)用角度看，你認(rèn)為兩種圖遍歷方法最大的差別是什么？D

6、irected Acyclic Graph (DAG)324167859324167859A Directed Acyclic GraphNot a DAGTopological Order(拓?fù)湫?G=(V,E) is a directed graph with n vertices. A topological order for G is an assignment of distinct integer 1,2, n to the vertices of V as their topological number, such that, for every vwE, the topol

7、ogical number of v is less than that of w.Reverse topological order can be defined similarly, (“greater than” )324167859123456789排序的結(jié)果不是唯一的。其實(shí)，可以將DFS看作一個算法的skeleton!有向圖中的強(qiáng)連通分支問題此有向圖含4個強(qiáng)連通分支在“轉(zhuǎn)置圖”中，結(jié)果不變。強(qiáng)連通分量節(jié)點(diǎn)合并后的無環(huán)圖即在前一次DFS中，后finish的點(diǎn)會先被搜索強(qiáng)分支算法DFS tree 1:含3個分支DFS tree 2:含1個分支為什么要從第一次搜索結(jié)果中最大的.f節(jié)點(diǎn)開始第

8、二輪DFS？1/63/42/57/108/915/1611/1412/13定義d(U)和f(U)討論兩個強(qiáng)連通分量的f( )值CCuvCCuvI：d(C) d(C)y關(guān)鍵性推論：令C和C是有向圖G的兩個強(qiáng)連通分量。如果f(C) f(C),那么在G的轉(zhuǎn)置圖GT中，不存在C到C的有向邊CCf(C) f(C)GCCGTXf(C) f(C)為什么？DFS tree 1:含3個分支DFS tree 2:含1個分支DFS算法能將圖分割成DFS trees, 但不能區(qū)分強(qiáng)分支。任何一個強(qiáng)分支一定完整的包含在一個DFS tree中。位于同一DFS tree，但不同強(qiáng)分支中的兩點(diǎn)通路一定是單向的。因此將一個分支看作一個點(diǎn)得到的圖是DAG。解決問題的關(guān)鍵：先將圖進(jìn)行正常的DFS