圖的遍歷主要有深度優(yōu)先搜索 DFS(depth-first search) 和廣度優(yōu)先搜索BFS( breadth-first search) 兩種方式
深度優(yōu)先遍歷
深度優(yōu)先遍歷可定義如下：首先訪問出發(fā)點v亚隙，并將其標(biāo)記為已訪問過；然后依次從v出發(fā)搜索v的每個鄰接點w抬驴。若w未曾訪問過鸠项，則以w為新的出發(fā)點繼續(xù)進(jìn)行深度優(yōu)先遍歷，直至圖中所有和源點v有路徑相通的頂點均已被訪問為止。若此時圖中仍有未訪問的頂點原朝，則另選一個尚未訪問的頂點為新的源點重復(fù)上述過程，直至圖中所有的頂點均已被訪問為止镶苞。
深度優(yōu)先遍歷結(jié)果是： A B E F C D G H I
深度優(yōu)先遍歷盡可能優(yōu)先往深層次進(jìn)行搜索
廣度優(yōu)先遍歷
廣度優(yōu)先遍歷可定義如下：首先訪問出發(fā)點v喳坠，接著依次訪問v的所有鄰接點w1、w2......wt茂蚓，然后依次訪問w1壕鹉、w2......wt鄰接的所有未曾訪問過的頂點。以此類推聋涨，直至圖中所有和源點v有路徑相通的頂點都已訪問到為止晾浴。此時從v開始的搜索過程結(jié)束。
廣度優(yōu)先遍歷結(jié)果是： A B C D E F G H I
廣度優(yōu)先遍歷按層次優(yōu)先搜索最近的結(jié)點牍白，一層一層往外搜索脊凰。
圖的數(shù)據(jù)結(jié)構(gòu)主要有鄰接矩陣和鄰接表2種。在 python 中我們可以這樣表示上面的圖
#!/usr/bin/env python3
import collections
import queue
g = collections.OrderedDict()
g['A'] = ['B', 'C', 'D']
g['B'] = ['A', 'E']
g['C'] = ['A', 'F']
g['D'] = ['A', 'G', 'H']
g['E'] = ['B', 'F']
g['F'] = ['E', 'C']
g['G'] = ['D', 'H', 'I']
g['H'] = ['G', 'D']
g['I'] = ['G']
類似鄰接表茂腥，這里用了 OrderedDict 狸涌，因為哈希表的遍歷輸出是不固定的
深度優(yōu)先遍歷
def DFSTraverse(g):
visited = {}
def DFS(v):
print(v)
visited[v] = True
for adj in g[v]:
if not visited.get(adj):
DFS(adj)
for v in g:
if not visited.get(v):
DFS(v)
DFSTraverse(g)
廣度優(yōu)先遍歷
def BFSTraverse(g):
visited = {}
q = queue.Queue()
for v in g:
if not visited.get(v):
print(v)
visited[v] = True # 先訪問再入隊
q.put(v)
while not q.empty():
e = q.get()
for adj in g[e]:
if not visited.get(adj):
print(adj)
visited[adj] = True
q.put(adj)
BFSTraverse(g)
廣度優(yōu)先遍歷借助了隊列來保證按層次搜索，上級層次的結(jié)點先入隊最岗，結(jié)點出隊時它的相鄰子結(jié)點再依次入隊
