Graph & Search

Graph

Graph 由节点(vertex)和边(edge)构成,通常用 G=(V,E)G = (V, E) 来表示:

  • V 表示节点的集合

  • E 表示边的集合,通常每条边由一对节点来表示,如 (v,w)(v, w) ,具体可分为

    • 有序对:有向(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 - 解魔方示意图

如图 1 所示,左边第一层的节点是魔方已经解决(solved)的状态,左边第二层节点是从解决状态移动一次所能达到的节点,依次类推到最右边的节点。此时,一种暴力解就是从 solved 节点出发,在图上搜索到魔方的起始状态。

Graph Representation (data structures)

Adjacency Lists

每个图 G=(V,E)G = (V, E)V|V| 个链表构成,每个链表保存着该节点的所有邻居,成为它的 adjacency list:

  • 如果是无向图:同一条边会出现在两个节点的 adjacency list 中

  • 如果是有向图:adjacency list 只保存以该节点为起点可达的邻居

Adjacency Lists 的优势:

  • 可以在同一组点上保存多个图

Graph Search In Details

Breadth First Search (BFS)

逐层地以起点为中心向外扩张地搜索,如图 2 所示:

图 2 - BFS 示意

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] 也只被遍历一次,时间复杂度为 Adj[v]\sum |Adj[v]| ,对于有向图来说是 E|E| ,对于无向图来说是 2E2|E| ,因此时间复杂度分析为 O(E)O(E)

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)