在計算機科學(xué)，圖遍歷（Tree Traversal，也稱圖搜索）是一系列圖搜索的算法，是單次訪問樹結(jié)構(gòu)類型數(shù)據(jù)（tree data structure)中每個節(jié)點以便檢查或更新的一系列機制。圖遍歷算法可以按照節(jié)點訪問順序進行分類舟铜，根據(jù)訪問目的或使用場景的不同，算法大致可分為28種：

序號	算法名稱	應(yīng)用場景
1	$\alpha-\beta$ 修剪算法	減少樹搜索過程中minimax算法評估的節(jié)點數(shù)量奠衔，屬于對抗性搜索算法
2	$A^{\star}$ 算法	用于尋路和圖遍歷，在多個節(jié)點之間尋找路徑塘娶，多用于點對點
3	$B^{\star}$ 算法	一種最佳優(yōu)先圖搜索算法归斤，用于查找給定初始節(jié)點到任何目標(biāo)節(jié)點的最低成本路徑
4	回溯算法(backtracking)	通用算法，用于查找某些計算問題的所有可行解刁岸，特別是約束滿足問題脏里，逐步構(gòu)建候選解，并在確定候選解不可行時進行回溯
5	波束搜索（beam) 算法	啟發(fā)式搜索算法虹曙，通過擴展有限集中最可能的節(jié)點來探索圖形
6	Bellman-Ford 算法	計算加權(quán)有向中單個源節(jié)點到其他節(jié)點的最短路徑迫横，比Dijkstra算法慢番舆，但更通用
7	Best-first 算法	根據(jù)指定規(guī)則選擇最可能的點來進行圖搜索
8	雙向(Bidirectional)搜索	從有向圖中找出給定初始點到目標(biāo)點的最短路徑，進行兩次搜索：一次從初始點開始向前搜索矾踱，一次從目標(biāo)點向后搜索恨狈，相遇時停止
9	Boruvka算法	貪婪算法，從圖中找到所有邊緣權(quán)重不同的最小生成樹或最小生成林
10	分支定界(Branch & Bound) 算法	通過狀態(tài)空間搜索可行解
11	廣度優(yōu)先搜索BFS (Breadth-first search)	遍歷或搜索樹或圖數(shù)據(jù)結(jié)構(gòu)呛讲，從圖任意節(jié)點開始禾怠，并在移動到下一節(jié)點之前探索當(dāng)前深度水平的所有相鄰節(jié)點
12	$D^{\star}$ 算法	增量搜索算法
13	深度優(yōu)先搜索DFS(Depth-first search)	遍歷或搜索樹或圖數(shù)據(jù)結(jié)構(gòu)的算法，選擇任意節(jié)點作為根節(jié)點贝搁，在回溯之前盡可能地沿著每個分支進行搜索
14	Dijkstra算法（SPF 算法吗氏，　shortest path faster）	搜索節(jié)點之間的最短路徑。單源最短路徑搜索：給定初始點雷逆，搜尋初始點到其他點的最短路徑弦讽，生成最短路徑樹
15	Edmonds算法	最小生成樹的定向模擬
16	Floyd-Warshall算法	在具有正或負邊緣權(quán)重的加權(quán)圖中尋找最短路徑
17	Fringe搜索	尋找從給定初始節(jié)點到目標(biāo)節(jié)點之間的最低成本路徑
18	爬山(Hill Climbing) 算法	從圖的任意節(jié)點開始，然后嘗試通過對節(jié)點進行增量更改來找到更好的節(jié)點
19	IDA (Iterative deepening $A^{\star}$ )算法	在加權(quán)圖中找到從給定初始節(jié)點到一組目標(biāo)節(jié)點中任意節(jié)點之間的最短路徑
20	迭代深化搜索算法(Iterative deepening)	具有深度限制的深度優(yōu)先搜索
21	Johnson算法	在稀疏邊緣加權(quán)有向圖中找到節(jié)點之間最短路徑
22	跳躍點搜索JPS (Jump point)算法	$A^{\star}$ 算法優(yōu)化版本
23	Kruskal 算法	最小生成樹算法膀哲，找到聯(lián)通樹中任意兩棵樹的最小權(quán)重邊緣
24	詞典寬度有限搜索Lex-BFS算法	對圖節(jié)點進行排序的線形時間搜索算法
25	LPA $^{\star}$ 算法	基于 $A^{\star}$ 算法的增量啟發(fā)式搜索算法
26	Prim 算法	一種貪婪算法坦袍，用于從加權(quán)無向圖中找到最小生成樹
27	SMA $^{\star}$ 算法	使用有界內(nèi)存的 $A^{\star}$ 算法，繼承了 $A^{\star}$ 算法的特性
28	最短路徑快速SPFA算法	Bellman-Ford算法的改進等太，在加權(quán)有向圖中計算單源最短路徑

圖遍歷即以特定方式訪問圖中所有節(jié)點捂齐，給定節(jié)點下有多種可能的搜索路徑。假定以順序方式進行（非并行）缩抡，還未訪問的節(jié)點就需通過堆棧（LIFO）或隊列（FIFO）規(guī)則來確定訪問先后奠宜。由于樹結(jié)構(gòu)是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，在清晰的定義下瞻想，未訪問節(jié)點可存儲在調(diào)用堆棧中压真。本文介紹了圖遍歷領(lǐng)域最流行的廣度優(yōu)先搜索算法BFS和深度優(yōu)先搜索算法DFS，對其原理蘑险、應(yīng)用及實現(xiàn)進行了闡述滴肿。通常意義上而言，深度優(yōu)先搜索（DFS）通過遞歸調(diào)用堆棧比較容易實現(xiàn)佃迄，廣義優(yōu)先搜索通過隊列實現(xiàn)泼差。

一、深度優(yōu)先搜索（Depth-first search）

深度優(yōu)先搜索（DFS）是用于遍歷或搜索圖數(shù)據(jù)結(jié)構(gòu)的算法呵俏，該算法從根節(jié)點開始（圖搜索時可選擇任意節(jié)點作為根節(jié)點）沿著每個分支進行搜索堆缘，分支搜索結(jié)束后在進行回溯。在進入下一節(jié)點之前普碎，樹的搜索盡可能的加深吼肥。
DFS的搜索算法如下（以二叉樹為例）：假定根節(jié)點（圖的任意節(jié)點可作為根節(jié)點）標(biāo)記為 $N$ ,
(L) : 遞歸遍歷左子樹，并在節(jié)點 $N$ 結(jié)束。
(R): 遞歸遍歷右子樹缀皱，并在節(jié)點 $N$ 結(jié)束斗这。
(N): 訪問節(jié)點 $N$ 。
這些步驟可以以任意次序排列啤斗。如果（L）在（R）之前表箭，則該過程稱為從左到右的遍歷；反之争占，則稱為從右到左的遍歷燃逻。根據(jù)訪問次序的不同，深度優(yōu)先搜索可分為 pre-order臂痕、in-order伯襟、out-order以及post-order遍歷方式。

1. Pre-order（NLR）遍歷

（a）檢查當(dāng)前節(jié)點是否為空握童；
（b）展示根節(jié)點或當(dāng)前節(jié)點數(shù)據(jù)姆怪；
（c）遞歸調(diào)用pre-order函數(shù)遍歷左子樹；
（d）遞歸調(diào)用pre-order函數(shù)遍歷右子樹澡绩。
pre-order遍歷屬于拓撲排序后的遍歷稽揭，父節(jié)點總是在任何子節(jié)點之前被訪問。該遍歷方式的圖示如下：

圖1. pre-order遍歷

遍歷次序依次為：F -B -A-D- C-E-G- I-H.

2. In-order (LNR)遍歷

（a）檢查當(dāng)前節(jié)點是否為空肥卡；
（b）遞歸調(diào)用in-order函數(shù)遍歷左子樹溪掀；
（c）展示根節(jié)點或當(dāng)前節(jié)點數(shù)據(jù)；
（d）遞歸調(diào)用in-order函數(shù)遍歷右子樹步鉴。
在二叉樹搜索中揪胃，in-order遍歷以排序順序訪問節(jié)點數(shù)據(jù)。該遍歷方式的圖示如下：

圖2. in-order遍歷

遍歷次序依次為：A -B - C - D - E - F - G -H-I

3. Out-order (RNL)遍歷

（a）檢查當(dāng)前節(jié)點是否為空氛琢；
（b）遞歸調(diào)用out-order函數(shù)遍歷右子樹喊递；
（c）展示根節(jié)點或當(dāng)前節(jié)點數(shù)據(jù)；
（d）遞歸調(diào)用out-order函數(shù)遍歷左子樹阳似。
該遍歷方式與LNR類似骚勘，但先遍歷右子樹后遍歷左子樹。仍然以圖2為例撮奏，遍歷次序依次為：H- I-G- F- B- E- D- C- A.

4. post-order (LRN)遍歷

（a）檢查當(dāng)前節(jié)點是否為空俏讹；
（b）遞歸調(diào)用post-order函數(shù)遍歷左子樹；
（c）遞歸調(diào)用post-order函數(shù)遍歷右子樹挽荡；
（d）展示根節(jié)點或當(dāng)前節(jié)點數(shù)據(jù)藐石。
post-order遍歷圖示如下：

圖3. post-order遍歷

遍歷次序依次為：A-C-E-D-B-H-I-G-F.

pre-order遍歷方式使用場景：用于創(chuàng)建樹或圖的副本；
in-order遍歷使用場景：二叉樹遍歷定拟；
post-order遍歷使用場景：刪除樹

遍歷追蹤也稱樹的序列化，是所訪問根節(jié)點列表。無論是pre-order青自，in-order或是post-order都無法完整的描述樹特性株依。給定含有不同元素的樹結(jié)構(gòu)，pre-order或post-order與in-order遍歷方式結(jié)合起來使用才可以描述樹的獨特性延窜。

二恋腕、廣度優(yōu)先搜索（Breath-first search）

樹或圖形的訪問也可以按照節(jié)點所處的級別進行遍歷。在每次訪問下一層級節(jié)點之前逆瑞，遍歷所在高層級的所有節(jié)點荠藤。BFS從根節(jié)點（圖的任意節(jié)點可作為根節(jié)點）出發(fā)，在移動到下一節(jié)點之前訪問所有相同深度水平的相鄰節(jié)點获高。

1945年哈肖，Konrad Zuse 在他被拒的博士論文中首次提到BFS在聯(lián)通子圖方面的應(yīng)用。1972年念秧，該博士論文被出版淤井。1959年，Edward F. Moore對BFS進行重新設(shè)計摊趾，并用于尋找迷宮中的最短路徑币狠。 1961年，C.Y.Lee對算法進行開發(fā)作為電路路由算法砾层。

BFS的遍歷方法圖示如下：

圖4. BFS遍歷

遍歷次序依次為： F-B-G-A-D-I-C-E-H.

三漩绵、DFS與BFS的偽代碼實現(xiàn)

1. DFS： pre-order 遍歷

preorder(node)
  if (node = null)
    return
  visit(node)
  preorder(node.left)
  preorder(node.right)

iterativePreorder(node)
  if (node = null)
    return
  s ← empty stack
  s.push(node)
  while (not s.isEmpty())
    node ← s.pop()
    visit(node)
    //right child is pushed first so that left is processed first
    if (node.right ≠ null)
      s.push(node.right)
    if (node.left ≠ null)
      s.push(node.left)

2. DFS：in-order遍歷

inorder(node)
  if (node = null)
    return
  inorder(node.left)
  visit(node)
  inorder(node.right)

iterativeInorder(node)
  s ← empty stack
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      node ← s.pop()
      visit(node)
      node ← node.right

3. DFS: post-order遍歷

postorder(node)
  if (node = null)
    return
  postorder(node.left)
  postorder(node.right)
  visit(node)

iterativePostorder(node)
  s ← empty stack
  lastNodeVisited ← null
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      peekNode ← s.peek()
      // if right child exists and traversing node
      // from left child, then move right
      if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right)
        node ← peekNode.right
      else
        visit(peekNode)
        lastNodeVisited ← s.pop()

4. BFS

levelorder(root)
  q ← empty queue
  q.enqueue(root)
  while (not q.isEmpty())
    node ← q.dequeue()
    visit(node)
    if (node.left ≠ null)
      q.enqueue(node.left)
    if (node.right ≠ null)
      q.enqueue(node.right)

四、DFS與BFS的R及Python代碼實現(xiàn)

1. R語言實現(xiàn)DFS與BFS

圖算法相關(guān)的R包為igraph肛炮，主要包括圖的生成止吐、圖計算等一系列算法的實現(xiàn)。

1.1 R語言實現(xiàn)DFS：函數(shù)dfs

使用方法：

dfs(graph, root, neimode = c("out", "in", "all", "total"),
unreachable = TRUE, order = TRUE, order.out = FALSE,
father = FALSE, dist = FALSE, in.callback = NULL,
out.callback = NULL, extra = NULL, rho = parent.frame())

參數(shù)說明：

參數(shù)	含義
graph	輸入圖
root	根節(jié)點铸董，搜索開始的單個節(jié)點
neimode	對有向圖祟印，指定訪問邊的類型。'out' 表示從節(jié)點出發(fā)的邊粟害，'in'表示進節(jié)點的邊蕴忆，'all' 完全忽略邊的方向，'total' 與'all'相同悲幅。對于無向圖套鹅，該參數(shù)可忽略
unreachable	邏輯值，取值'true'或'false'汰具，表示搜索是否需要訪問從根節(jié)點無法到達的節(jié)點集合
order	邏輯值卓鹿，是否返回DFS排序后的節(jié)點序列
order.out	邏輯值，是否返回離開子圖的節(jié)點排序
father	邏輯值留荔，是否返回節(jié)點的父節(jié)點
dist	邏輯值吟孙，是否返回從根節(jié)點出發(fā)搜索的距離
in.callback	若不為空，則存在callback函數(shù)
out.callback	若不為空，則存在callback函數(shù)
extra	callback函數(shù)的其他參數(shù)
rho	callback函數(shù)被評估的環(huán)境

示例：

require(igraph)
## generate graph
graph <- make_tree(10) %du% make_tree(10)
# plot graph
plot(graph)
# 搜索從根節(jié)點出發(fā)的節(jié)點排序
dfs_res<-dfs(graph, root=1, "out",TRUE, TRUE, TRUE, TRUE)

結(jié)果展示：

圖5. 無向圖示例

DFS R輸出節(jié)點排序：

1-2-4-8-9-5-10-3-6-7-11-12-14-18-19-15-20-13-16-17

1.2 R語言實現(xiàn)BFS：函數(shù)bfs

使用方法：

bfs(graph, root, neimode = c("out", "in", "all", "total"),
unreachable = TRUE, restricted = NULL, order = TRUE,
rank = FALSE, father = FALSE, pred = FALSE, succ = FALSE,
dist = FALSE, callback = NULL, extra = NULL,
rho = parent.frame())

參數(shù)含義同dfs
示例：

require(igraph)
## generate graph
graph <- make_ring(10) %du% make_ring(10)
# plot graph
plot(graph)
# 搜索從根節(jié)點出發(fā)的節(jié)點排序
bfs_res<-bfs(graph, root=1, "out",order=TRUE, rank=TRUE, father=TRUE, pred=TRUE,
             succ=TRUE, dist=TRUE)

結(jié)果展示：

圖6. 無向圖示例

BFS R輸出節(jié)點排序：

1-2-10-3-9-4-8-5-7-6-11-12-20-13-19-14-18-15-17-16

2. Python 實現(xiàn)BFS 及DFS

以尋找兩點之間的路徑為例杰妓，分別展示BFS及DFS的實現(xiàn)藻治。圖示例如下：

圖7. 無向圖示例

2.1 Python實現(xiàn)BFS

示例：

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

def bfs_paths(graph, start, goal):
    queue = [(start, [start])]
    while queue:
        (vertex, path) = queue.pop(0)
        for next in graph[vertex] - set(path):
            if next == goal:
                yield path + [next]
            else:
                queue.append((next, path + [next]))

list(bfs_paths(graph, 'A', 'F'))

輸出結(jié)果：

[['A', 'C', 'F'], ['A', 'B', 'E', 'F']]

2.2 Python實現(xiàn)DFS

示例：

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    while stack:
        (vertex, path) = stack.pop()
        for next in graph[vertex] - set(path):
            if next == goal:
                yield path + [next]
            else:
                stack.append((next, path + [next]))

list(dfs_paths(graph, 'A', 'F'))