open-courses
Search…
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)