Graph & Search

Graph

Graph 由节点（vertex）和边（edge）构成，通常用 $G = (V, E)$ 来表示：

• V 表示节点的集合

• E 表示边的集合，通常每条边由一对节点来表示，如 $(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)$ 由 $|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] 也只被遍历一次，时间复杂度为 $\sum |Adj[v]|$ ，对于有向图来说是 $|E|$ ，对于无向图来说是 $2|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)