本節(jié)主要介紹圖的遍歷算法BFS和DFS，以及尋找圖的(強(qiáng))連通分量的算法

Traversal就是遍歷，主要是對(duì)圖的遍歷，也就是遍歷圖中的每個(gè)節(jié)點(diǎn)。對(duì)一個(gè)節(jié)點(diǎn)的遍歷有兩個(gè)階段，首先是發(fā)現(xiàn)(discover)，然后是訪問(wèn)(visit)。遍歷的重要性自然不必說(shuō)，圖中有幾個(gè)算法和遍歷沒(méi)有關(guān)系？！

[算法導(dǎo)論對(duì)于發(fā)現(xiàn)和訪問(wèn)區(qū)別的非常明顯，對(duì)圖的算法講解地特別好，在遍歷節(jié)點(diǎn)的時(shí)候給節(jié)點(diǎn)標(biāo)注它的發(fā)現(xiàn)節(jié)點(diǎn)時(shí)間d[v]和結(jié)束訪問(wèn)時(shí)間f[v]，然后由這些時(shí)間的一些規(guī)律得到了不少實(shí)用的定理，本節(jié)后面介紹了部分內(nèi)容，感興趣不妨閱讀下算法導(dǎo)論原書(shū)]

圖的連通分量是圖的一個(gè)最大子圖，在這個(gè)子圖中任何兩個(gè)節(jié)點(diǎn)之間都是相互可達(dá)的(忽略邊的方向)。我們本節(jié)的重點(diǎn)就是想想怎么找到一個(gè)圖的連通分量呢？

一個(gè)很明顯的想法是，我們從一個(gè)頂點(diǎn)出發(fā)，沿著邊一直走，慢慢地?cái)U(kuò)大子圖，直到子圖不能再擴(kuò)大了停止，我們就得到了一個(gè)連通分量對(duì)吧，我們?cè)趺创_定我們真的是找到了一個(gè)完整的連通分量呢？可以看下作者給出的解釋，類似上節(jié)的Induction，我們思考從i-1到i的過(guò)程，只要我們保證增加了這個(gè)節(jié)點(diǎn)后子圖仍然是連通的就對(duì)了。

Let'slookatthefollowingrelatedproblem.Showthatyoucanorderthenodesinaconnectedgraph,V1,V2,…Vn,sothatforanyi=1…n,thesubgraphoverV1,…,Viisconnected.Ifwecanshowthisandwecanfigureouthowtodotheordering,wecangothroughallthenodesinaconnectedcomponentandknowwhenthey'reallusedup.

Howdowedothis?Thinkinginductively,weneedtogetfromi-1toi.Weknowthatthesubgraphoverthei-1firstnodesisconnected.Whatnext?Well,becausetherearepathsbetweenanypairofnodes,consideranodeuinthefirsti-1nodesandanodevintheremainder.Onthepathfromutov,considerthelastnodethatisinthecomponentwe'vebuiltsofar,aswellasthefirstnodeoutsideit.Let'scallthemxandy.Clearlytheremustbeanedgebetweenthem,soaddingytothenodesofourgrowingcomponentkeepsitconnected,andwe'veshownwhatwesetouttoshow.

經(jīng)過(guò)上面的一番思考，我們就知道了如何找連通分量：從一個(gè)頂點(diǎn)開(kāi)始，沿著它的邊找到其他的節(jié)點(diǎn)(或者說(shuō)站在這個(gè)節(jié)點(diǎn)上看，看能夠發(fā)現(xiàn)哪些節(jié)點(diǎn))，然后就是不斷地向已有的連通分量中添加節(jié)點(diǎn)，使得連通分量?jī)?nèi)部依然滿足連通性質(zhì)。如果我們按照上面的思路一直做下去，我們就得到了一棵樹(shù)，一棵遍歷樹(shù)，它也是我們遍歷的分量的一棵生成樹(shù)。在具體實(shí)現(xiàn)這個(gè)算法時(shí)，我們要記錄“邊緣節(jié)點(diǎn)”，也就是那些和已得到的連通分量中的節(jié)點(diǎn)相連的節(jié)點(diǎn)，它們就像是一個(gè)個(gè)待辦事項(xiàng)(to-dolist)一樣，而前面加入的節(jié)點(diǎn)就是標(biāo)記為已完成的(checkedoff)待辦事項(xiàng)。

這里作者舉了一個(gè)很有意思的例子，一個(gè)角色扮演的游戲，如下圖所示，我們可以將房間看作是節(jié)點(diǎn)，將房間的門(mén)看作是節(jié)點(diǎn)之間的邊，走過(guò)的軌跡就是遍歷樹(shù)。這么看的話，房間就分成了三種：(1)我們已經(jīng)經(jīng)過(guò)的房間；(2)我們已經(jīng)經(jīng)過(guò)的房間附近的房間，也就是馬上可以進(jìn)入的房間；(3)“黑屋”，我們甚至都不知道它們是否存在，存在的話也不知道在哪里。

根據(jù)上面的分析可以寫(xiě)出下面的遍歷函數(shù)walk，其中參數(shù)S暫時(shí)沒(méi)有用，它在后面求強(qiáng)連通分量時(shí)需要，表示的是一個(gè)“禁區(qū)”(forbidden zone)，也就是不要去訪問(wèn)這些節(jié)點(diǎn)。

注意下面的difference函數(shù)的使用，參數(shù)可以是多個(gè)，也就是說(shuō)調(diào)用后返回的集合中的元素在各個(gè)參數(shù)中都不存在，此外，參數(shù)也不一定是set，也可以是dict或者list，只要是可迭代的(iterables)即可?？梢钥聪聀ython docs

# Walking Through a Connected Component of a Graph Represented Using Adjacency Sets
def walk(G, s, S=set()):            # Walk the graph from node s
  P, Q = dict(), set()            # Predecessors + "to do" queue
  P[s] = None                 # s has no predecessor
  Q.add(s)                  # We plan on starting with s
  while Q:                  # Still nodes to visit
    u = Q.pop()               # Pick one, arbitrarily
    for v in G[u].difference(P, S):     # New nodes?
      Q.add(v)              # We plan to visit them!
      P[v] = u              # Remember where we came from
  return P

我們可以用下面代碼來(lái)測(cè)試下，得到的結(jié)果沒(méi)有問(wèn)題

def some_graph():
  a, b, c, d, e, f, g, h = range(8)
  N = [
    [b, c, d, e, f],  # a
    [c, e],       # b
    [d],        # c
    [e],        # d
    [f],        # e
    [c, g, h],     # f
    [f, h],       # g
    [f, g]       # h
  ]
  return N
 
G = some_graph()
for i in range(len(G)): G[i] = set(G[i])
print list(walk(G,0)) #[0, 1, 2, 3, 4, 5, 6, 7]

上面的walk函數(shù)只適用于無(wú)向圖，而且只能找到一個(gè)從參數(shù)s出發(fā)的連通分量，要想得到全部的連通分量需要修改下

def components(G):               # The connected components
  comp = []
  seen = set()                # Nodes we've already seen
  for u in G:                 # Try every starting point
    if u in seen: continue         # Seen? Ignore it
    C = walk(G, u)             # Traverse component
    seen.update(C)             # Add keys of C to seen
    comp.append(C)             # Collect the components
  return comp

用下面的代碼來(lái)測(cè)試下，得到的結(jié)果沒(méi)有問(wèn)題

G = {
  0: set([1, 2]),
  1: set([0, 2]),
  2: set([0, 1]),
  3: set([4, 5]),
  4: set([3, 5]),
  5: set([3, 4])
  }
 
print [list(sorted(C)) for C in components(G)] #[[0, 1, 2], [3, 4, 5]]

至此我們就完成了一個(gè)時(shí)間復(fù)雜度為Θ(E+V)的求無(wú)向圖的連通分量的算法，因?yàn)槊織l邊和每個(gè)頂點(diǎn)都要訪問(wèn)一次。[這個(gè)時(shí)間復(fù)雜度會(huì)經(jīng)?？吹?，例如拓?fù)渑判?，?qiáng)連通分量都是它]

[接下來(lái)作者作為擴(kuò)展介紹了歐拉回路和哈密頓回路：前者是經(jīng)過(guò)圖中的所有邊一次，然后回到起點(diǎn)；后者是經(jīng)過(guò)圖中的所有頂點(diǎn)一次，然后回到起點(diǎn)。網(wǎng)上資料甚多，感興趣自行了解]

下面我們看下迷宮問(wèn)題，如下圖所示，原始問(wèn)題是一個(gè)人在公園中走路，結(jié)果走不出來(lái)了，即使是按照“左手準(zhǔn)則”(也就是但凡遇到交叉口一直向左轉(zhuǎn))走下去，如果走著走著回到了原來(lái)的起點(diǎn)，那么就會(huì)陷入無(wú)限的循環(huán)中！有意思的是，左邊的迷宮可以通過(guò)“左手準(zhǔn)則”轉(zhuǎn)換成右邊的樹(shù)型結(jié)構(gòu)。

[注：具體的轉(zhuǎn)換方式我還未明白，下面是作者給出的構(gòu)造說(shuō)明]

Here the “keep one hand on the wall” strategy will work nicely. One way of seeing why it works is to observe that the maze really has only one inner wall (or, to put it another way, if you put wallpaper inside it, you could use one continuous strip). Look at the outer square. As long as you're not allowed to create cycles, any obstacles you draw have to be connected to the it in exactly one place, and this doesn't create any problems for the left-hand rule. Following this traversal strategy, you'll discover all nodes and walk every passage twice (once in either direction).

上面的迷宮實(shí)際上就是為了引出深度優(yōu)先搜索(DFS)，每次到了一個(gè)交叉口的時(shí)候，可能我們可以向左走，也可以向右走，選擇是有不少，但是我們要向一直走下去的話就只能選擇其中的一個(gè)方向，如果我們發(fā)現(xiàn)這個(gè)方向走不出去的話，我們就回溯回來(lái)，選擇一個(gè)剛才沒(méi)選過(guò)的方向繼續(xù)嘗試下去。

基于上面的想法可以寫(xiě)出下面遞歸版本的DFS

def rec_dfs(G, s, S=None):
  if S is None: S = set()           # Initialize the history
  S.add(s)                  # We've visited s
  for u in G[s]:               # Explore neighbors
    if u in S: continue           # Already visited: Skip
    rec_dfs(G, u, S)            # New: Explore recursively
  return S # For testing
 
G = some_graph()
for i in range(len(G)): G[i] = set(G[i])
print list(rec_dfs(G, 0))  #[0, 1, 2, 3, 4, 5, 6, 7]

很自然的我們想到要將遞歸版本改成迭代版本的，下面的代碼中使用了Python中的yield關(guān)鍵字，具體的用法可以看下這里IBM Developer Works

def iter_dfs(G, s):
  S, Q = set(), []              # Visited-set and queue
  Q.append(s)                 # We plan on visiting s
  while Q:                  # Planned nodes left?
    u = Q.pop()               # Get one
    if u in S: continue           # Already visited? Skip it
    S.add(u)                # We've visited it now
    Q.extend(G[u])             # Schedule all neighbors
    yield u                 # Report u as visited
 
G = some_graph()
for i in range(len(G)): G[i] = set(G[i])
print list(iter_dfs(G, 0)) #[0, 5, 7, 6, 2, 3, 4, 1]

上面迭代版本經(jīng)過(guò)一點(diǎn)點(diǎn)的修改可以得到更加通用的遍歷函數(shù)

def traverse(G, s, qtype=set):
  S, Q = set(), qtype()
  Q.add(s)
  while Q:
    u = Q.pop()
    if u in S: continue
    S.add(u)
    for v in G[u]:
      Q.add(v)
    yield u

函數(shù)traverse中的參數(shù)qtype表示隊(duì)列類型，例如棧stack，下面的代碼給出了如何自定義一個(gè)stack，以及測(cè)試traverse函數(shù)

class stack(list):
  add = list.append
 
G = some_graph()
print list(traverse(G, 0, stack)) #[0, 5, 7, 6, 2, 3, 4, 1]

如果還不清楚的話可以看下算法導(dǎo)論中的這幅DFS示例圖，節(jié)點(diǎn)的顏色后面有介紹

上圖在DFS時(shí)給節(jié)點(diǎn)加上了時(shí)間戳，這有什么作用呢？

前面提到過(guò)，在遍歷節(jié)點(diǎn)的時(shí)候如果給節(jié)點(diǎn)標(biāo)注它的發(fā)現(xiàn)節(jié)點(diǎn)時(shí)間d[v]和結(jié)束訪問(wèn)時(shí)間f[v]的話，從這些時(shí)間我們就能夠發(fā)現(xiàn)一些信息，比如下圖，(a)是圖的一個(gè)DFS遍歷加上時(shí)間戳后的結(jié)果；(b)是如果給每個(gè)節(jié)點(diǎn)的d[v]到f[v]區(qū)間加上一個(gè)括號(hào)的話，可以看出在DFS遍歷中(也就是后來(lái)的深度優(yōu)先樹(shù)/森林)中所有的節(jié)點(diǎn) u 的后繼節(jié)點(diǎn) v 的區(qū)間都在節(jié)點(diǎn) u 的區(qū)間內(nèi)部，如果節(jié)點(diǎn) v 不是節(jié)點(diǎn) u 的后繼，那么兩個(gè)節(jié)點(diǎn)的區(qū)間不相交，這就是“括號(hào)定理”。

加上時(shí)間戳的DFS遍歷還算比較好寫(xiě)對(duì)吧

#Depth-First Search with Timestamps
def dfs(G, s, d, f, S=None, t=0):
  if S is None: S = set()           # Initialize the history
  d[s] = t; t += 1              # Set discover time
  S.add(s)                  # We've visited s
  for u in G[s]:               # Explore neighbors
    if u in S: continue           # Already visited. Skip
    t = dfs(G, u, d, f, S, t)        # Recurse; update timestamp
  f[s] = t; t += 1              # Set finish time
  return t                  # Return timestamp

除了給節(jié)點(diǎn)加上時(shí)間戳之外，算法導(dǎo)論在介紹DFS的時(shí)候還給節(jié)點(diǎn)進(jìn)行著色，在節(jié)點(diǎn)被發(fā)現(xiàn)之前是白色的，在發(fā)現(xiàn)之后先是灰色的，在結(jié)束訪問(wèn)之后才是黑色的，詳細(xì)的流程可以參考上面給出的算法導(dǎo)論中的那幅DFS示例圖。有了顏色有什么用呢？作用大著呢！根據(jù)節(jié)點(diǎn)的顏色，我們可以對(duì)邊進(jìn)行分類！大致可以分為下面四種：

使用DFS對(duì)圖進(jìn)行遍歷時(shí)，對(duì)于每條邊(u,v)，當(dāng)該邊第一次被發(fā)現(xiàn)時(shí)，根據(jù)到達(dá)節(jié)點(diǎn) v 的顏色來(lái)對(duì)邊進(jìn)行分類(正向邊和交叉邊不做細(xì)分)：

(1)白色表示該邊是一條樹(shù)邊；

(2)灰色表示該邊是一條反向邊；

(3)黑色表示該邊是一條正向邊或者交叉邊。

下圖顯示了上面介紹括號(hào)定理用時(shí)的那個(gè)圖的深度優(yōu)先樹(shù)中的所有邊的類型，灰色標(biāo)記的邊是深度優(yōu)先樹(shù)的樹(shù)邊

那對(duì)邊進(jìn)行分類有什么作用呢？作用多著呢！最常見(jiàn)的作用的是判斷一個(gè)有向圖是否存在環(huán)，如果對(duì)有向圖進(jìn)行DFS遍歷發(fā)現(xiàn)了反向邊，那么一定存在環(huán)，反之沒(méi)有環(huán)。此外，對(duì)于無(wú)向圖，如果對(duì)它進(jìn)行DFS遍歷，肯定不會(huì)出現(xiàn)正向邊或者交叉邊。

那對(duì)節(jié)點(diǎn)標(biāo)注時(shí)間戳有什么用呢？其實(shí)，除了可以發(fā)現(xiàn)上面提到的那些很重要的性質(zhì)之外，時(shí)間戳對(duì)于接下來(lái)要介紹的拓?fù)渑判虻牧硪环N解法和強(qiáng)連通分量很重要！

我們先看下摘自算法導(dǎo)論的這幅拓?fù)渑判蚴纠龍D，這是某個(gè)教授早上起來(lái)后要做的事情，嘿嘿

不難發(fā)現(xiàn)，最終得到的拓?fù)渑判騽偤檬枪?jié)點(diǎn)的完成時(shí)間f[v]降序排列的！結(jié)合前面的括號(hào)定理以及依賴關(guān)系不難理解，如果我們按照節(jié)點(diǎn)的f[v]降序排列，我們就得到了我們想要的拓?fù)渑判蛄?！這就是拓?fù)渑判虻牧硪粋€(gè)解法！[在算法導(dǎo)論中該解法是主要介紹的解法，而我們前面提到的那個(gè)解法是在算法導(dǎo)論的習(xí)題中出現(xiàn)的]

基于上面的想法就能夠得到下面的實(shí)現(xiàn)代碼，函數(shù)recurse是一個(gè)內(nèi)部函數(shù)，這樣它就可以訪問(wèn)到G和res等變量

#Topological Sorting Based on Depth-First Search
def dfs_topsort(G):
  S, res = set(), []             # History and result
  def recurse(u):               # Traversal subroutine
    if u in S: return            # Ignore visited nodes
    S.add(u)                # Otherwise: Add to history
    for v in G[u]:
      recurse(v)             # Recurse through neighbors
    res.append(u)              # Finished with u: Append it
  for u in G:
    recurse(u)               # Cover entire graph
  res.reverse()                # It's all backward so far
  return res
 
G = {'a': set('bf'), 'b': set('cdf'), 'c': set('d'), 'd': set('ef'), 'e': set('f'), 'f': set()}
print dfs_topsort(G)

[接下來(lái)作者介紹了一個(gè)Iterative Deepening Depth-First Search，沒(méi)看懂，貌似和BFS類似]

如果我們?cè)诒闅v圖時(shí)“一層一層”式地遍歷，先發(fā)現(xiàn)的節(jié)點(diǎn)先訪問(wèn)，那么我們就得到了廣度優(yōu)先搜索(BFS)。下面是作者給出的一個(gè)有意思的區(qū)別BFS和DFS的例子，遍歷過(guò)程就像我們上網(wǎng)一樣，DFS是順著網(wǎng)頁(yè)上的鏈接一個(gè)個(gè)點(diǎn)下去，當(dāng)訪問(wèn)完了這個(gè)網(wǎng)頁(yè)時(shí)就點(diǎn)擊Back回退到上一個(gè)網(wǎng)頁(yè)繼續(xù)訪問(wèn)。而B(niǎo)FS是先在后臺(tái)打開(kāi)當(dāng)前網(wǎng)頁(yè)上的所有鏈接，然后按照打開(kāi)的順序一個(gè)個(gè)訪問(wèn)，訪問(wèn)完了一個(gè)網(wǎng)頁(yè)就把它的窗口關(guān)閉。

One way of visualizing BFS and DFS is as browsing the Web. DFS is what you get if you keep following links and then use the Back button once you're done with a page. The backtracking is a bit like an “undo.” BFS is more like opening every link in a new window (or tab) behind those you already have and then closing the windows as you finish with each page.

BFS的代碼很好實(shí)現(xiàn)，主要是使用隊(duì)列

#Breadth-First Search
from collections import deque
 
def bfs(G, s):
  P, Q = {s: None}, deque([s])        # Parents and FIFO queue
  while Q:
    u = Q.popleft()             # Constant-time for deque
    for v in G[u]:
      if v in P: continue         # Already has parent
      P[v] = u              # Reached from u: u is parent
      Q.append(v)
  return P
 
G = some_graph()
print bfs(G, 0)

Python的list可以很好地充當(dāng)stack，但是充當(dāng)queue則性能很差，函數(shù)bfs中使用的是collections模塊中的deque，即雙端隊(duì)列(double-ended queue)，它一般是使用鏈表來(lái)實(shí)現(xiàn)的，這個(gè)類有extend、append和pop等方法都是作用于隊(duì)列右端的，而方法extendleft、appendleft和popleft等方法都是作用于隊(duì)列左端的，它的內(nèi)部實(shí)現(xiàn)是非常高效的。

Internally, the deque is implemented as a doubly linked list of blocks, each of which is an array of individual elements. Although asymptotically equivalent to using a linked list of individual elements, this reduces overhead and makes it more efficient in practice. For example, the expression d[k] would require traversing the first k elements of the deque d if it were a plain list. If each block contains b elements, you would only have to traverse k//b blocks.

最后我們看下強(qiáng)連通分量，前面的分量是不考慮邊的方向的，如果我們考慮邊的方向，而且得到的最大子圖中，任何兩個(gè)節(jié)點(diǎn)都能夠沿著邊可達(dá)，那么這就是一個(gè)強(qiáng)連通分量。

下圖是算法導(dǎo)論中的示例圖，(a)是對(duì)圖進(jìn)行DFS遍歷帶時(shí)間戳的結(jié)果；(b)是上圖的的轉(zhuǎn)置，也就是將上圖中所有邊的指向反轉(zhuǎn)過(guò)來(lái)得到的圖；(c)是最終得到的強(qiáng)連通分支圖，每個(gè)節(jié)點(diǎn)內(nèi)部顯示了該分支內(nèi)的節(jié)點(diǎn)。

上面的示例圖自然不太好明白到底怎么得到的，我們慢慢來(lái)分析三幅圖 [原書(shū)的分析太多了，我被繞暈了+_+，下面是我結(jié)合算法導(dǎo)論的分析過(guò)程]

先看圖(a)，每個(gè)灰色區(qū)域都是一個(gè)強(qiáng)連通分支，我們想想，如果強(qiáng)連通分支 X 內(nèi)部有一條邊指向另一個(gè)強(qiáng)連通分支 Y，那么強(qiáng)連通分支 Y 內(nèi)部肯定不存在一條邊指向另一個(gè)強(qiáng)連通分支 Y，否則它們能夠整合在一起形成一個(gè)新的更大氣的強(qiáng)連通分支！這也就是說(shuō)強(qiáng)連通分支圖肯定是一個(gè)有向無(wú)環(huán)圖！我們從圖(c)也可以看出來(lái)

再看看圖(c)，強(qiáng)連通分支之間的指向，如果我們定義每個(gè)分支內(nèi)的任何頂點(diǎn)的最晚的完成時(shí)間為對(duì)應(yīng)分支的完成時(shí)間的話，那么分支abe的完成時(shí)間是16，分支cd是10，分支fg是7，分支h是6，不難發(fā)現(xiàn)，分支之間邊的指向都是從完成時(shí)間大的指向完成時(shí)間小的，換句話說(shuō)，總是由完成時(shí)間晚的強(qiáng)連通分支指向完成時(shí)間早的強(qiáng)連通分支！

最后再看看圖(b)，該圖是原圖的轉(zhuǎn)置，但是得到強(qiáng)連通分支是一樣的(強(qiáng)連通分支圖是會(huì)變的，剛好又是原來(lái)分支圖的轉(zhuǎn)置)，那為什么要將邊反轉(zhuǎn)呢？結(jié)合前面兩個(gè)圖的分析，既然強(qiáng)連通分支圖是有向無(wú)環(huán)圖，而且總是由完成時(shí)間晚的強(qiáng)連通分支指向完成時(shí)間早的強(qiáng)連通分支，如果我們將邊反轉(zhuǎn)，雖然我們得到的強(qiáng)連通分支不變，但是分支之間的指向變了，完成時(shí)間晚的就不再指向完成時(shí)間早的了！這樣的話如果我們對(duì)它進(jìn)行拓?fù)渑判?，即按照完成時(shí)間的降序再次進(jìn)行DFS時(shí)，我們就能夠得到一個(gè)個(gè)的強(qiáng)連通分支了對(duì)不對(duì)？因?yàn)槊看蔚玫降膹?qiáng)連通分支都沒(méi)有辦法指向其他分支了，也就是確定了一個(gè)強(qiáng)連通分支之后就停止了。[試試畫(huà)個(gè)圖得到圖(b)的強(qiáng)連通分支圖的拓?fù)渑判蚪Y(jié)果就明白了]

經(jīng)過(guò)上面略微復(fù)雜的分析之后我們知道強(qiáng)連通分支算法的流程有下面四步：

1.對(duì)原圖G運(yùn)行DFS，得到每個(gè)節(jié)點(diǎn)的完成時(shí)間f[v]；

2.得到原圖的轉(zhuǎn)置圖GT；

3.對(duì)GT運(yùn)行DFS，主循環(huán)按照節(jié)點(diǎn)的f[v]降序進(jìn)行訪問(wèn)；

4.輸出深度優(yōu)先森林中的每棵樹(shù)，也就是一個(gè)強(qiáng)連通分支。

根據(jù)上面的思路可以得到下面的強(qiáng)連通分支算法實(shí)現(xiàn)，其中的函數(shù)parse_graph是作者用來(lái)方便構(gòu)造圖的函數(shù)

def tr(G):                   # Transpose (rev. edges of) G
  GT = {}
  for u in G: GT[u] = set()          # Get all the nodes in there
  for u in G:
    for v in G[u]:
      GT[v].add(u)            # Add all reverse edges
  return GT
 
def scc(G):
  GT = tr(G)                 # Get the transposed graph
  sccs, seen = [], set()
  for u in dfs_topsort(G):          # DFS starting points
    if u in seen: continue         # Ignore covered nodes
    C = walk(GT, u, seen)          # Don't go "backward" (seen)
    seen.update(C)             # We've now seen C
    sccs.append(C)             # Another SCC found
  return sccs
 
from string import ascii_lowercase
def parse_graph(s):
  # print zip(ascii_lowercase, s.split("/"))
  # [('a', 'bc'), ('b', 'die'), ('c', 'd'), ('d', 'ah'), ('e', 'f'), ('f', 'g'), ('g', 'eh'), ('h', 'i'), ('i', 'h')]
  G = {}
  for u, line in zip(ascii_lowercase, s.split("/")):
    G[u] = set(line)
  return G
 
G = parse_graph('bc/die/d/ah/f/g/eh/i/h')
print list(map(list, scc(G)))
#[['a', 'c', 'b', 'd'], ['e', 'g', 'f'], ['i', 'h']]

[最后作者提到了一點(diǎn)如何進(jìn)行更加高效的搜索，也就是通過(guò)分支限界來(lái)實(shí)現(xiàn)對(duì)搜索樹(shù)的剪枝，具體使用可以看下這個(gè)問(wèn)題頂點(diǎn)覆蓋問(wèn)題Vertext Cover Problem]

問(wèn)題5.17 強(qiáng)連通分支

In Kosaraju's algorithm, we find starting nodes for the final traversal by descending finish times from an initial DFS, and we perform the traversal in the transposed graph (that is, with all edges reversed). Why couldn't we just use ascending finish times in the original graph?

問(wèn)題就是說(shuō)，我們干嘛要對(duì)轉(zhuǎn)置圖按照完成時(shí)間降序遍歷一次呢？干嘛不直接在原圖上按照完成時(shí)間升序遍歷一次呢？

Try finding a simple example where this would give the wrong answer. (You can do it with a really small graph.)

總結(jié)

以上就是本文關(guān)于Python算法之圖的遍歷的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站：

python先序遍歷二叉樹(shù)問(wèn)題

python實(shí)現(xiàn)報(bào)表自動(dòng)化詳解

python繪制鉛球的運(yùn)行軌跡代碼分享

如有不足之處，歡迎留言指出。

最新評(píng)論