計算機問題求解

–

論題2-16

圖的計算機表示以及遍歷問題1:你能否根據(jù)這兩組圖解釋計算機中最主要的圖表示方式?問題2:我們討論表示方法是否合適主要根據(jù)什么?你能否結(jié)合上述兩種方式給以說明?關(guān)鍵操作的效率vs.

存儲需求問題3:通常圖中與應(yīng)用相關(guān)的附加信息有些什么?他們對表示方法的選擇有什么影響?問題4:圖的搜索是什么意思?為什么它是用圖模型解決問題的基本操作?圖搜索經(jīng)常被稱為“遍歷”(traversal)在一個連通圖中，選定一個起點總可以到達所有其它點，如果我們確保任一定點只“到達”一次，則“經(jīng)過”的邊不會構(gòu)成回路。廣度與深度搜索所“經(jīng)過”的邊構(gòu)成的是原來圖的“生成樹”。Backtracking(回朔)廣度優(yōu)先深度優(yōu)先廣度優(yōu)先兩個關(guān)鍵的動詞問題5：圖搜索時用什么辦法來跟蹤搜索的進度？問題6：在何處體現(xiàn)”frontierexpansion”?為什么“擴張”的結(jié)果一定是樹？問題7：為什么說廣度優(yōu)先搜索的代價是線性的？其問題規(guī)模是用什么參數(shù)表示的？v.d的上限問題8：你能解釋是怎么歸納的嗎？為什么？進隊列的次序與v.d

值的大小注意：每個頂點被賦一次有限的.d值，之后再不改變。其實：同時在隊列中的頂點的.d

值是非遞減的，差值最多為1問題9：你能根據(jù)代碼直觀地解釋以下為什么嗎？廣度優(yōu)先搜索計算最短路長度算法終止時證明要點：假設(shè)頂點v是不滿足上述條件的定點中.d值最小的一個，針對v用反證法證明。設(shè)u是從s到v的最短路上的直接前驅(qū)點，則深度優(yōu)先搜索注意：time深度優(yōu)先搜索也是線性算法問題10：為什么區(qū)分黑色頂點與灰色定點對于深度優(yōu)先很重要，對于廣度優(yōu)先其實不重要？問題11：為什么對深度優(yōu)先需要引入“時間戳”？u.d和u.f的含義是什么？問題12：你能解釋深度優(yōu)先搜索森林內(nèi)/外的邊與頂點活動時間段之間的關(guān)系嗎？問題13：深度優(yōu)先搜索對于無向圖與有向圖有何不同？問題14:廣度優(yōu)先搜索是利用隊列實現(xiàn)的,那深度優(yōu)先搜索用什么數(shù)據(jù)結(jié)構(gòu)呢?為什么有這樣的差別?DirectedAcyclicGraph(DAG)324167859324167859ADirectedAcyclicGraphNotaDAGTopologicalOrder(拓撲序)G=(V,E)isadirectedgraphwithnvertices.AtopologicalorderforGisanassignmentofdistinctinteger1,2,…,ntotheverticesofVastheirtopologicalnumber,suchthat,foreveryvwE,thetopologicalnumberofvislessthanthatofw.Reversetopologicalordercanbedefinedsimilarly,(“greaterthan”)324167859123456789排序的結(jié)果不是唯一的。其實，可以將DFS看作一個算法的skeleton!有向圖中的強連通分支問題此有向圖含4個強連通分支在“轉(zhuǎn)置圖”中，結(jié)果不變。理解強分支算法的關(guān)鍵DFStree1:含3個分支DFStree2:含1個分支DFS算法能將圖分割成DFStrees,但不能區(qū)分強分支。任何一個強分支一定完整的包含在一個DFStree中。位于同一DFStree，但不同強分支中兩點通路一定是單向的。因此將一個分支看作一個點得到的圖是DAG。解決問題的關(guān)鍵：先將圖分解為正常的DFS

trees,分別對各個tree的轉(zhuǎn)置圖再做DFS,按照特別的順序使得從選定頂點出發(fā)只能達到一個強分支內(nèi)的頂點，不能到達其它定點的原因可能是因為通路已不存在（轉(zhuǎn)置），或者那些頂點已經(jīng)是黑色的了。即在前一次DFS中后finish的點會先被搜索，這如何實現(xiàn)呢？問題15：從應(yīng)用角度看，你認為兩種圖遍歷方法最大的差別是什么？課外作業(yè)TCpp.592-:ex.22.1-3;22.1-8TCpp.601-:ex.22.2-3;22.2-4;22.2-5TCpp.610-:e