# Graph

## Define

有很多种方法可以存储一个图，最常用的莫过于：

1. 邻接矩阵
2. 邻接表

而邻接矩阵因为耗费空间过大，我们通常在工程中都是使用邻接表作为图的存储结构。

**邻接矩阵 Adjacent Matrix**

```
[
  [1,0,0,1],
  [0,1,1,0],
  [0,1,1,0],
  [1,0,0,1]
]
```

例如上图表示0号点和3号点有连边。1号点和2号店有连边。\
当然，每个点和自己也是默认有连边的。\
图中的`0`表示不连通，`1`表示连通。\
我们也可以用一个更具体的整数值来表示连边的长度。\
邻接矩阵我们可以直接用一个二维数组表示，如`int[][] matrix;`。这种数据结构因为耗费 O(n^2) 的空间，所以在稀疏图上浪费很大，因此并不常用。

**邻接表 (Adjacent List)**

```
[
  [1],
  [0,2,3],
  [1],
  [1]
]
```

这个图表示 0 和 1 之间有连边，1 和 2 之间有连边，1 和 3 之间有连边。即每个点上存储自己有哪些邻居（有哪些连通的点）。\
这种方式下，空间耗费和边数成正比，可以记做 O(m)，m代表边数。m最坏情况下虽然也是 O(n^2)，但是邻接表的存储方式大部分情况下会比邻接矩阵更省空间。

### 自定义邻接表

可以用自定义的类来实现邻接表

```
class DirectedGraphNode {
     int label;
     ArrayList<DirectedGraphNode> neighbors;
     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
}

class UndirectedGraphNode {
     int label;
     List<UndirectedGraphNode> neighbors;
     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
};
```

其中 neighbors 表示和该点连通的点有哪些。

### 使用 Map 和 Set（面试时）

也可以使用 HashMap 和 HashSet 搭配的方式来存储邻接表

```
Map<T, Set<T>> = new HashMap<Integer, HashSet<Integer>>();
```

其中 T 代表节点类型。通常可能是整数(Integer)。\
这种方式虽然没有上面的方式更加直观和容易理解，但是在面试中比较节约代码量。\
而自定义的方法，更加工程化，所以在面试中如果时间不紧张题目不难的情况下，推荐使用自定义邻接表的方式。

### 简化版

有的时候节点会简化成0-1000的数字，这时图的表示就比较简化了

```
Input: [[1,3], [0,2], [1,3], [0,2]]
Explanation: 
The graph looks like this:
0----1
|    |
|    |
3----2
```

```
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Explanation: 
The graph looks like this:
0----1
| \  |
|  \ |
3----2
```

这种就是邻接表的一个例子，注意节点从1开始还是从0开始，有些情况会告诉最大节点数，方便初始化邻接表

### **OJ's undirected graph serialization:**

Nodes are labeled uniquely.

We use`#`as a separator for each node, and`,`as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph`{0,1,2#1,2#2,2}`.

The graph has a total of three nodes, and therefore contains three parts as separated by`#`.

1. First node is labeled as`0`. Connect node`0`to both nodes`1`and`2`
2. Second node is labeled as`1`. Connect node`1`to node`2`.
3. Third node is labeled as`2`. Connect node`2`to node`2`(itself), thus forming a self-cycle.

Visually, the graph looks like the following:

```
       1
      / \
     /   \
    0 --- 2
         / \
         \_/
```

## Some statement for tree in graph theory

> (1) A tree is an undirected graph in which any two vertices are connected by exactly one path.
>
> (2) Any connected graph who has`n`nodes with`n-1`edges is a tree.
>
> (3) The degree of a vertex of a graph is the number of edges incident to the vertex.
>
> (4) A leaf is a vertex of degree 1. An internal vertex is a vertex of degree at least 2.
>
> (5) A path graph is a tree with two or more vertices that is not branched at all.
>
> (6) A tree is called a rooted tree if one vertex has been designated the root.
>
> (7) The height of a rooted tree is the number of edges on the longest downward path between root and a leaf.

## BFS/DFS

Graph 是非常重要而又涵盖很广的内容，以至于有单独的 “图论” 研究方向。LeetCode 上很多问题都可以抽象成 “图” ，比如搜索类问题，树类问题，迷宫问题，矩阵路径问题，等等。

重点在于 DFS 和 BFS 的比较；可以看到；

* BFS 的时间空间占用以 branching factor 为底， 到解的距离 d 为指数增长；空间占用上 Queue 是不会像 DFS 一样只存一条路径的，而是从起点出发越扩越大，因此会有空间不够的风险，空间占用为 O(b^d)。
* DFS 的时间占用以 branching factor 为底，树的深度 m 为指数增长；而空间占用上，却只是 O(bm)，可视化探索过程中只把每个 Node 的所有子节点存在 Stack 上， 探索完了再 pop 出来接着探，因此储存的节点数为 O(bm)。

可以看到无论是 BFS 还是 DFS，树的 branching factor 都是对空间与时间复杂度影响最大的参数；除此之外，BFS 中最重要的是到解的距离，而 DFS 看从当前节点的深度。普遍来讲，DFS 空间上会经济一些，当然也要分情况讨论。

![](https://mnmunknown.gitbooks.io/algorithm-notes/content/TreeSearch.PNG)

Topological sort，拓扑排序，是 graph 搜索中一种特殊的顺序，本质上还是完全可以靠 BFS / DFS 解决。

**有向图 DFS 图示：**

![](https://mnmunknown.gitbooks.io/algorithm-notes/content/DFS.JPG)

**有向图 BFS 图示：**

![](https://mnmunknown.gitbooks.io/algorithm-notes/content/BFS.JPG)

**可以看到两种搜索都用了三种颜色表示状态。**

* **有向图 Directed：**
  * **DFS**:
    * Detect Cycle ([Course Schedule](https://leetcode.com/problems/course-schedule/))

      > * 暴力解法：DFS + Backtracking，寻找“所有从当前节点的” path，如果试图访问 visited 则有环；缺点是，同一个点会被探索多次，而且要从所有点作为起点保证算法正确性，时间复杂度非常高
      > * 最优解法是 CLRS 上用三种状态表示每个节点：
      >   * "0" 还未访问过;
      >   * "1" 代表正在访问；
      >   * "2" 代表已经访问过；
      > * DFS 开始时把当前节点设为 "1";
      > * 在从任意节点出发的时候，如果我们试图访问一个状态为 "1" 的节点，都说明图上有环。
      > * 当前节点的 DFS 结束时，设为 "2";
      > * 在找环上，DFS 比起 BFS 最大的优点是"对路径有记忆"，DFS 记得来时的路径和导致环的位置，BFS 却不行。
    * [Topological Sort](http://www.lintcode.com/en/problem/topological-sorting/)

      > * 类似剥洋葱，可以选择任意点开始向里 DFS ，记录path，后面做的其他 DFS path 都放在之前结果的前面。(CLRS有)
      > * 等价做法是，把每次 DFS 探索中的 path 按照由内向外的顺序添加(单序列反序), 后进行的 DFS 结果放在之前运行完的结果后面(全序列反序)，然后 reverse 就好了，可以改良 ArrayList 添加的时间复杂度。
      > * 更简单的做法是用 Java 内置的 LinkedList，支持双端操作。
    * Count # of connected components
    * Determine if A is reachable from B
  * **BFS**：
    * Detect Cycle ([Course Schedule](https://leetcode.com/problems/course-schedule/))

      > * 首先，在 DAG 上找环，DFS 要比 BFS 强。
      > * **其次重点注意，有向图靠 3 个状态 BFS 是不能正确判断是否有环的，要靠 indegree，一个例子是 【0, 1】 和 【1,0】，环在发现之前已经被标注为 state 2 了。**
      > * 扫一遍所有 edge，记录每个节点的 indegree.
      > * 在有向无环图中，一定会存在至少一个 indegree 为 0 的起点，将所有这样的点加入queue。
      > * 依次处理queue里的节点，把每次poll出来的节点的 children indegree -1. 减完之后如果 child 的 indegree = 0 了，就也放入队列。
      > * 如果图真的没有环，可以顺利访问完所有节点，如果还有剩的，说明图中有环，因为环上节点的 indegree 没法归 0.
    * [Topological Sort](http://www.lintcode.com/en/problem/topological-sorting/)

      > * 步骤同上，扫的时候按顺序 append 就好了。
      > * 类似于“剥洋葱”，从最外面一层出发，逐步向里。
    * Count # of connected components
    * Determine if A is reachable from B

      > * 这个任务最适合用 BFS 做，从 B 做起点一路扫看看能不能扫到 A 就行了。
* **Un-directed:**

  无向图算法的整体思路和有向图基本一致，但是需要重点注意 正确处理 “原路返回” 的情况，免得死循环或者误报。

  在无向图的2个状态基础上增加一个 “正在访问” 的新状态，加上注意 prev 就可以了。

  * **DFS**:
    * Detect Cycle ([Graph Valid Tree](https://leetcode.com/problems/graph-valid-tree/))

      > * 用 int\[] 表示每个点的状态，其中
      >   * 0 代表“未访问”；
      >   * 1 代表“访问中”；
      >   * 2 代表“已访问”；
      > * DFS call 里要传入 "prev节点" 参数，避免出现原路返回，或者回到前一个节点误判为有环。(和 directed graph DFS 唯一的不同之处)
      > * 其他情况下，如果我们试图访问一个状态为 “1” 的节点，都可以说明图中有环。
    * Topological Sort

      > * 都无向图了，topological 。。。。
    * Count # of connected components ([Graph Valid Tree](https://leetcode.com/problems/graph-valid-tree/))
    * Determine if A is reachable from B
  * **BFS：**
    * Detect Cycle ([Graph Valid Tree](https://leetcode.com/problems/graph-valid-tree/))

      > * 扫描所有 edges 记录图到底长啥样；
      > * 用 "0,1,2" states;
      > * 随便扔一个点进 queue，标记 "1"，然后 BFS，所有 child = "0" 的都加入队列
      > * **所有 child 都检查完之后，立刻把当前 node = 2，不然下一层 BFS 会回头去看自己然后误报。**
      > * 如果遇到 child = "1" 的说明有环
    * Topological Sort

      > * 都无向图了，topological 。。。。
    * Count # of connected components ([Graph Valid Tree](https://leetcode.com/problems/graph-valid-tree/))

      > * 和 Detect Cycle 一样，同时记录下到底做了几次 BFS 才扫遍全图，图上就有几个 connected components
    * Determine if A is reachable from B

      > * BFS 搜到底看看能不能到就可以了，这个和只靠 g(x) 的 uniform-cost search 一致。


---

# 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://luj.gitbook.io/code/gragh.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.