> For the complete documentation index, see [llms.txt](https://zhenghe.gitbook.io/open-courses/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhenghe.gitbook.io/open-courses/mit-6.006/graph-and-search.md).

# 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 - 解魔方示意图](/files/-LWBt1-nzu080xPlbfAx)

如图 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 示意](/files/-LWBx5IMj12Ku8bXS4Nu)

BFS 在 Adjacency Lists 图表示上的伪代码示意如下：

```python
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 图表示上的伪代码示意如下：

```python
# 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)
```