# DSA - 图

## 基本概念

图(graph)是一系列**节点**以及节点间的**关系**组成的集合，是一种抽象数据结构。

用一个生活中的例子来说明的话，在一个家庭中，有爸爸、妈妈、儿子和女儿，他们每个人都分别是一个节点。而节点之间可能存在着某种关系，比如爸爸和妈妈是夫妻关系，爸爸和儿子是父子关系，我们用一条连接两个节点的**线**来表示它们之间的关系。

在图中，节点叫做**顶点(vertice)**，表示关系的线叫做**边(edge)**。

![graph](https://cdn.jsdelivr.net/gh/suukii/Articles/assets/graph/concept.png)

更准确地说，图 G 可以定义为 `G = (V, E)`，它由两个集合组成：`V(顶点Vertex)` 和 `E(边Edge)`。

* V 是**顶点**的集合。
* E 是**边**的集合，这个集合中元素的格式是 `(u, v)`，其中 `u` 和 `v` 都是顶点，`(u, v)` 则表示顶点 `u` 和 `v` 之间存在关系。

![graph](https://cdn.jsdelivr.net/gh/suukii/Articles/assets/graph/graph_1.png)

上面这个图可以定义为：

```
V = {0, 1, 2, 3} // 顶点
E = {(0, 1), (0, 2), (0, 3), (1, 2)} // 边
G = {V, E} // 图
```

在生活中，图一般用来表示网络，包括城市里的道路网络、电话网络、互联网、社交网络等等。

**一些概念**

* 邻接(Adjacency)：如果两个顶点之间有一条边相连，那这两个顶点就是相互邻接的。
* 路径(Path)：指的是从`顶点A`到`顶点B`要经过的一系列**边**的集合。
* 有向图(Directed Graph)：在有向图中，有边 `(u, v)` 不代表有边 `(v, u)`，在有向图中**边**一般都用箭头来表示方向，而上面的图例是无向图。

## 图的分类

图可以分为无向图和有向图，上面所说的是无向图。“无向”指的是顶点之间的边是没有方向的，在上面的例子中，“爸爸和妈妈之间存在某种关系”这句话反过来说也是正确的。而在有向图中，这并不一定成立，A->B 并不意味着 B->A。

图还可以分成 sparse graph 和 dense graph，sparse graph 包含的边的数量较少，而 dense graph 包含的边的数量较多。

## 图的表示

### 邻接矩阵(Adjacency Matrix)

邻接矩阵是一个二维数组，每一行和每一列都分别表示一个顶点。如果 `matrix[i][j]` 是 `1` 的话，说明`顶点i`和`顶点j`有一条边相连。

用邻接矩阵来表示上面定义的那个图：

![graph](https://cdn.jsdelivr.net/gh/suukii/Articles/assets/graph/adjacency_matrix.png)

由于这是一个无向图，所以 `(0, 2)` 表示 `(2, 0)` 也是存在的，也就是 `matrix[0][2]` 和 `matrix[2][0]` 都是 `1`。

**邻接矩阵的优点**

**查找边**的操作，也就是查询两个顶点之间是否有边相连，会比较快，只需要 $O(1)$ 的时间。

增加或者删除边的操作也都是 $O(1)$。

适合用来表示 dense graph，而不适合用来表示 sparse graph

**邻接矩阵的不足**

这种方法占用的内存空间比较多。从上图可以看出，即使两个顶点之间没有边相连，但在矩阵中还是占用了一个位置来记录它们“没有关系”的关系。

邻接矩阵的空间复杂度为 $O(N^2)$，N 是顶点的数量，所以也可以表示为 $O(V^2)$。

增加或者删除顶点会比较麻烦，所以使用邻接矩阵的话，图的顶点数量最好是已知并且固定的。

### 邻接表(Adjacency List)

另一种表示图的方式是使用邻接表。邻接表可以用一个哈希表来表示，哈希表的 `key` 表示图的顶点，`value` 则是一个列表，存放着该顶点的邻接点，这个列表用数组或者链表来实现。

上面的图用邻接表来表示的话：

![graph](https://cdn.jsdelivr.net/gh/suukii/Articles/assets/graph/adjacency_list.png)

邻接表相对邻接矩阵来说更节省空间，因为只需要存储实际存在的关系，空间复杂度可以表示为 $O(V + E)$，V 是顶点数量，E 是边的数量；但查找边的时间复杂度就提高到了 $O(N)$，N 为顶点数量，也可表示为 $O(V)$。

## 图的遍历

ps. 树的遍历其实是特殊的图的遍历。

下面先用邻接表来实现一个简单的无向图。

```javascript
class Graph {
    constructor(noOfVertices) {
        this.noOfVertices = noOfVertices; // 顶点数量
        this.adjList = new Map(); // 邻接表
    }

    // 增加顶点
    addVertex(v) {
        // 在邻接表中增加一个列表来记录该顶点的邻接点
        this.adjList.set(v, []);
    }

    // 增加边
    addEdge(v, w) {
        // 分别把顶点 v, w 加到对方的邻接点列表中
        this.adjList.get(v).push(w);
        this.adjList.get(w).push(v);
    }

    bfs(v) {}

    dfs(v) {}
}
```

### BFS

先遍历“兄弟节点”，再遍历“子节点”。

BFS 可以用来寻找两个顶点之间的最短路径。

关键点：把顶点分为“已遍历”和“未遍历”两个类别，避免无限循环。

**伪代码**

```
选一个顶点作为遍历的起点
把顶点放进一个队列Q中

当队列Q不为空时，重复以下步骤：
    出列一个顶点，把它加到“已遍历”列表中
    遍历这个顶点的邻接点列表：
        如果邻接点属于“未遍历”，把它加到队列Q中
```

注意：如果图中存在一个顶点，从选定的起点并不能到达这个顶点，那它就不会被遍历到。可以对上述代码进行改造，对图中的每一个顶点，都将它们作为起点进行一次遍历。

**复杂度分析**

* 时间复杂度：$O(V + E)$，V 是顶点数量，E 是边的数量。
* 空间复杂度：$O(V)$，V 是顶点数量。

**代码**

```javascript
bfs(v) {
  const visited = Array(this.noOfVertices).fill(false)
  const queue = []
  queue.push(v)
  visited[v] = true
  while (queue.length > 0) {
    const node = queue.shift()
    console.log(node)
    const neighs = this.adjList.get(node)
    neighs.forEach((neigh) => {
      if (!visited[neigh]) {
        visited[neigh] = true
        queue.push(neigh)
      }
    })
  }
}
```

### DFS

先遍历“子节点”，再遍历“兄弟节点”。

**伪代码**

```
选一个顶点作为遍历的起点
把顶点放进一个栈中

当栈不为空时，重复以下步骤：
    出栈一个顶点，把它加到“已遍历”列表中
    遍历这个顶点的邻接点列表：
        如果邻接点属于“未遍历”，将它入栈
```

**复杂度分析**

* 时间复杂度：$O(V + E)$，V 是顶点数量，E 是边的数量。
* 空间复杂度：$O(V)$，V 是顶点数量。

**代码**

```javascript
dfs() {
  const stack = []
  stack.push(v)

  while (stack.length > 0) {
    const vertex = stack.pop()
    if (!visited[vertex]) {
      visited[vertex] = true
      console.log(vertex)
    }
    const neighs = this.adjList.get(vertex)
    neighs.reduceRight((_, neigh) => {
      if (!visited[neigh]) {
        stack.push(neigh)
      }
    }, null)
  }
}
```

也可以用递归来实现，下面的代码同时也考虑了上面提到的“图中存在两个不直接或间接相连的顶点”这个问题。

```javascript
dfs() {
  const visited = Array(this.noOfVertices).fill(false)
  const vertices = this.adjList.keys()
  for (let vertex of vertices) {
    if (!visited[vertex]) {
      this.dfsUntil(vertex, visited)
    }
}
}
dfsUntil(v, visited) {
  if (!visited[v]) {
    visited[v] = true
    console.log(v)
  }
  const neighs = this.adjList.get(v)
  neighs.forEach((neigh) => {
    if (!visited[neigh]) {
      this.dfsUntil(neigh, visited)
    }
  })
}
```

```javascript
var g = new Graph(6);
var vertices = ['A', 'B', 'C', 'D', 'E', 'F'];
for (var i = 0; i < vertices.length; i++) {
    g.addVertex(vertices[i]);
}
g.addEdge('A', 'B');
g.addEdge('A', 'D');
g.addEdge('A', 'E');
g.addEdge('B', 'C');
g.addEdge('D', 'E');
g.addEdge('E', 'F');
g.addEdge('E', 'C');
g.addEdge('C', 'F');
g.dfs('A');
g.bfs('A');
```


---

# 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://suki.gitbook.io/notes/articles/dsa/dsa_graph.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.