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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenghe.gitbook.io/open-courses/mit-6.006/graph-and-search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.