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

Traversal就是遍歷，主要是對圖的遍歷，也就是遍歷圖中的每個節(jié)點。對一個節(jié)點的遍歷有兩個階段，首先是發(fā)現(discover)，然后是訪問(visit)。遍歷的重要性自然不必說，圖中有幾個算法和遍歷沒有關系？！

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

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

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

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.

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

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

根據上面的分析可以寫出下面的遍歷函數walk，其中參數S暫時沒有用，它在后面求強連通分量時需要，表示的是一個“禁區(qū)”(forbidden zone)，也就是不要去訪問這些節(jié)點。

注意下面的difference函數的使用，參數可以是多個，也就是說調用后返回的集合中的元素在各個參數中都不存在，此外，參數也不一定是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

我們可以用下面代碼來測試下，得到的結果沒有問題

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函數只適用于無向圖，而且只能找到一個從參數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

用下面的代碼來測試下，得到的結果沒有問題

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]]

至此我們就完成了一個時間復雜度為Θ(E+V)的求無向圖的連通分量的算法，因為每條邊和每個頂點都要訪問一次。[這個時間復雜度會經?？吹?，例如拓撲排序，強連通分量都是它]

[接下來作者作為擴展介紹了歐拉回路和哈密頓回路：前者是經過圖中的所有邊一次，然后回到起點；后者是經過圖中的所有頂點一次，然后回到起點。網上資料甚多，感興趣自行了解]

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

[注：具體的轉換方式我還未明白，下面是作者給出的構造說明]

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).

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

基于上面的想法可以寫出下面遞歸版本的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關鍵字，具體的用法可以看下這里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]

上面迭代版本經過一點點的修改可以得到更加通用的遍歷函數

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

函數traverse中的參數qtype表示隊列類型，例如棧stack，下面的代碼給出了如何自定義一個stack，以及測試traverse函數

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

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

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

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

加上時間戳的DFS遍歷還算比較好寫對吧

#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é)點加上時間戳之外，算法導論在介紹DFS的時候還給節(jié)點進行著色，在節(jié)點被發(fā)現之前是白色的，在發(fā)現之后先是灰色的，在結束訪問之后才是黑色的，詳細的流程可以參考上面給出的算法導論中的那幅DFS示例圖。有了顏色有什么用呢？作用大著呢！根據節(jié)點的顏色，我們可以對邊進行分類！大致可以分為下面四種：

使用DFS對圖進行遍歷時，對于每條邊(u,v)，當該邊第一次被發(fā)現時，根據到達節(jié)點 v 的顏色來對邊進行分類(正向邊和交叉邊不做細分)：

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

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

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

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

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

那對節(jié)點標注時間戳有什么用呢？其實，除了可以發(fā)現上面提到的那些很重要的性質之外，時間戳對于接下來要介紹的拓撲排序的另一種解法和強連通分量很重要！

我們先看下摘自算法導論的這幅拓撲排序示例圖，這是某個教授早上起來后要做的事情，嘿嘿

不難發(fā)現，最終得到的拓撲排序剛好是節(jié)點的完成時間f[v]降序排列的！結合前面的括號定理以及依賴關系不難理解，如果我們按照節(jié)點的f[v]降序排列，我們就得到了我們想要的拓撲排序了！這就是拓撲排序的另一個解法！[在算法導論中該解法是主要介紹的解法，而我們前面提到的那個解法是在算法導論的習題中出現的]

基于上面的想法就能夠得到下面的實現代碼，函數recurse是一個內部函數，這樣它就可以訪問到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)

[接下來作者介紹了一個Iterative Deepening Depth-First Search，沒看懂，貌似和BFS類似]

如果我們在遍歷圖時“一層一層”式地遍歷，先發(fā)現的節(jié)點先訪問，那么我們就得到了廣度優(yōu)先搜索(BFS)。下面是作者給出的一個有意思的區(qū)別BFS和DFS的例子，遍歷過程就像我們上網一樣，DFS是順著網頁上的鏈接一個個點下去，當訪問完了這個網頁時就點擊Back回退到上一個網頁繼續(xù)訪問。而BFS是先在后臺打開當前網頁上的所有鏈接，然后按照打開的順序一個個訪問，訪問完了一個網頁就把它的窗口關閉。

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的代碼很好實現，主要是使用隊列

#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可以很好地充當stack，但是充當queue則性能很差，函數bfs中使用的是collections模塊中的deque，即雙端隊列(double-ended queue)，它一般是使用鏈表來實現的，這個類有extend、append和pop等方法都是作用于隊列右端的，而方法extendleft、appendleft和popleft等方法都是作用于隊列左端的，它的內部實現是非常高效的。

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.

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

下圖是算法導論中的示例圖，(a)是對圖進行DFS遍歷帶時間戳的結果；(b)是上圖的的轉置，也就是將上圖中所有邊的指向反轉過來得到的圖；(c)是最終得到的強連通分支圖，每個節(jié)點內部顯示了該分支內的節(jié)點。

上面的示例圖自然不太好明白到底怎么得到的，我們慢慢來分析三幅圖 [原書的分析太多了，我被繞暈了+_+，下面是我結合算法導論的分析過程]

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

再看看圖(c)，強連通分支之間的指向，如果我們定義每個分支內的任何頂點的最晚的完成時間為對應分支的完成時間的話，那么分支abe的完成時間是16，分支cd是10，分支fg是7，分支h是6，不難發(fā)現，分支之間邊的指向都是從完成時間大的指向完成時間小的，換句話說，總是由完成時間晚的強連通分支指向完成時間早的強連通分支！

最后再看看圖(b)，該圖是原圖的轉置，但是得到強連通分支是一樣的(強連通分支圖是會變的，剛好又是原來分支圖的轉置)，那為什么要將邊反轉呢？結合前面兩個圖的分析，既然強連通分支圖是有向無環(huán)圖，而且總是由完成時間晚的強連通分支指向完成時間早的強連通分支，如果我們將邊反轉，雖然我們得到的強連通分支不變，但是分支之間的指向變了，完成時間晚的就不再指向完成時間早的了！這樣的話如果我們對它進行拓撲排序，即按照完成時間的降序再次進行DFS時，我們就能夠得到一個個的強連通分支了對不對？因為每次得到的強連通分支都沒有辦法指向其他分支了，也就是確定了一個強連通分支之后就停止了。[試試畫個圖得到圖(b)的強連通分支圖的拓撲排序結果就明白了]

經過上面略微復雜的分析之后我們知道強連通分支算法的流程有下面四步：

1.對原圖G運行DFS，得到每個節(jié)點的完成時間f[v]；

2.得到原圖的轉置圖GT；

3.對GT運行DFS，主循環(huán)按照節(jié)點的f[v]降序進行訪問；

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

根據上面的思路可以得到下面的強連通分支算法實現，其中的函數parse_graph是作者用來方便構造圖的函數

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']]

[最后作者提到了一點如何進行更加高效的搜索，也就是通過分支限界來實現對搜索樹的剪枝，具體使用可以看下這個問題頂點覆蓋問題Vertext Cover Problem]

問題5.17 強連通分支

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?

問題就是說，我們干嘛要對轉置圖按照完成時間降序遍歷一次呢？干嘛不直接在原圖上按照完成時間升序遍歷一次呢？

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

總結

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

python先序遍歷二叉樹問題

python實現報表自動化詳解

python繪制鉛球的運行軌跡代碼分享

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

最新評論