图的遍历主要有深度优先搜索 DFS(depth-first search) 和广度优先搜索BFS( breadth-first search) 两种方式
g.png
深度优先遍历
深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点为新的源点重复上述过程，直至图中所有的顶点均已被访问为止。
dfs.png
深度优先遍历结果是： A B E F C D G H I
深度优先遍历尽可能优先往深层次进行搜索
广度优先遍历
广度优先遍历可定义如下：首先访问出发点v，接着依次访问v的所有邻接点w1、w2......wt，然后依次访问w1、w2......wt邻接的所有未曾访问过的顶点。以此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。
bfs.png
广度优先遍历结果是： A B C D E F G H I
广度优先遍历按层次优先搜索最近的结点，一层一层往外搜索。
图的数据结构主要有邻接矩阵和邻接表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 ，因为哈希表的遍历输出是不固定的
深度优先遍历
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)
广度优先遍历
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)
广度优先遍历借助了队列来保证按层次搜索，上级层次的结点先入队，结点出队时它的相邻子结点再依次入队
