Graph & Search
Graph
Graph 由节点（vertex）和边（edge）构成，通常用 来表示：
V 表示节点的集合
E 表示边的集合，通常每条边由一对节点来表示，如 ，具体可分为
有序对：有向（directed）边
无序对：无向（undirected) 边
Graph Search Concept
Graph 搜索，就是在图上探索的，从当前节点走到下一个节点，直到达到目的，如：
找到从节点 A 到节点 B 的一条路径
遍历图上的所有节点
找到从节点 A 出发能到达的所有节点
...
Applications
Graph Search 算法的应用非常广泛，举例如下：
web crawling
social networking
network broadcast routing
garbage collection
model checking (finite state machine)
checking mathematical conjectures
solving puzzles & games
如解魔方（Rubik's cube），我们可以把解魔方的过程抽象成一个图：
图上的节点表示魔方可能所处的状态
图上的边表示每个最小的移动，每次移动把魔方从一个状态转移到下一个状态；同时，这里的边是无向的，因此每次移动也都是可逆的
如图 1 所示，左边第一层的节点是魔方已经解决（solved）的状态，左边第二层节点是从解决状态移动一次所能达到的节点，依次类推到最右边的节点。此时，一种暴力解就是从 solved 节点出发，在图上搜索到魔方的起始状态。
Graph Representation (data structures)
Adjacency Lists
每个图 由 个链表构成，每个链表保存着该节点的所有邻居，成为它的 adjacency list：
如果是无向图：同一条边会出现在两个节点的 adjacency list 中
如果是有向图：adjacency list 只保存以该节点为起点可达的邻居
Adjacency Lists 的优势：
可以在同一组点上保存多个图
Graph Search In Details
Breadth First Search (BFS)
逐层地以起点为中心向外扩张地搜索，如图 2 所示：
BFS 在 Adjacency Lists 图表示上的伪代码示意如下：
def BFS(s, Adj):
level = {s: 0}
parent = {s: None}
i = 1
frontier = [s]
while frontier:
next = []
for u in frontier:
for v in Adj[u]:
# 检查是否曾经访问过该点，在树结构中不需要担心这个问题
if v not in level:
level[v] = i
parent[v] = u
next.append(v)
frontier = next
i += 1复杂度分析：
时间复杂度：每个节点 v 只进入 next 一次，因此 Adj[v] 也只被遍历一次，时间复杂度为 ，对于有向图来说是 ，对于无向图来说是 ，因此时间复杂度分析为 。
Depth First Search（DFS）
DFS 就像走迷宫，每当遇到分叉口的时候，可以做一个标记（breadcrumb），然后选择其中一个岔口继续探索，当遇到死胡同时，返回上一个标记处，选择另外一个岔口继续寻找，直到到达出口或者遍历完所有可能的路径。
DFS 在 Adjacency Lists 图表示上的伪代码示意如下：
# explore the entire graph
def dfs(V, Adj):
parent={}
for s in V:
if s not in parent:
parent[s] = None
dfs_visit(V, Adj, s, parent)
# explore all vertexes reachable from s
def dfs_visit(V, Adj, s, parent):
if not parent:
parent = {}
for v in Adj[s]:
if v not in parent:
parent[v] = s
dfs_visit(V, Adj, v, parent)Last updated