入门级-数据结构-图的遍历

# 图的遍历

---

图的遍历：从图的某个顶点出发，按照某种搜索方法沿着图的边访问所有顶点，每个顶点仅访问一次。

遍历得到的顶点的序列，称为图遍历序列。显然不同的搜索方法会得到不同的遍历序列。

有两种搜索方法：

* 深度优先搜索（DFS：Depth First Search）
* 广度优先搜索（BFS：Breadth First Search）

---

## 2、深度优先搜索

从某个顶点v0出发，找到其第一个邻接点v1，从v1开始继续进行深度优先搜索，如果某个顶点没有未访问的邻接点，就沿着原路回溯，一直到所有的顶点都被遍历到（既回溯到开始搜索的地方）。

![](https://cdn.itbegin.com//pics/admin/2019/4/2fb7c94c6b8841959e2f9acd9f9e79d7.jpg)

---

上图从A点出发做dfs搜索（蓝字表示访问，红字表示回溯）：

1. 访问A点，邻接点有B、F、G，选择B点
2. 访问B点，邻接点有C、D，选择C点
3. 访问C点，没有邻接点，返回
4. 回溯到B点，未访问点有D，选择D点
5. 访问D点，邻接点有E，选择E点
6. 访问E点，没有邻接点，返回
7. 回溯到D点，没有未访问点，返回
8. 回溯到B点，没有未访问点，返回

---

9. 回溯到A点，未访问点有F、G，选择F
10. 访问F点，没有邻接点，返回
11. 回溯到A点，未访问点有G，选择G
12. 访问G点，未访问点有H，选择H
13. 访问H点，没有邻接点，返回
14. 回溯到G点，没有未访问点，返回
15. 回溯到A点，没有未访问点，返回
16. 回到搜索调用的地方，搜索结束

遍历序列为：ABCDEFGH

`理解dfs`：尽可能的远离起始点。

---

## 3、算法实现

`要点描述`：

* 根据邻接矩阵（或邻接表）能遍历每个点的邻接点
* 已经访问的点，用一个桶数组vis[]记录，防止重复经过
* 用递归函数实现往下遍历
* 也可以用栈(stack)来实现

```
dfs(顶点) {
  记录访问;
  for(邻接点)
    if (没有访问过)
      dfs(邻接点);
}

int main(){
  dfs(起始点);
  return 0;
}
```

---

如果图不一定连通，调用dfs的时候需要用到循环

```
int main() {
  for(int i=1; i<=n; i++)
    if(!vis[i])
      dfs(i);
}
```

---

`注意`：

* dfs遍历经过所有点和边，其复杂度为O(V+E)
* dfs遍历时没有对状态回溯，如果加上状态回溯就变成了枚举所有的路径

---

### 扩展理解

dfs使用递归进行遍历，每个顶点都有进入、退出的时机，注意退出时机是和递归调用反着的。

---

## 4、dfs回溯

在dfs遍历时，往往通过vis数组标记经过的点（或边），这是为了避免回路，这种情况下往往只有一条路径可走。

如果我们想枚举所有的路径，就要对vis状态进行回溯，例如：

```
void dfs(int x) {
  vis[x] = true;
  for(int i=0; i<g[x].size(); i++) {
    int y = g[x][i];
    if(!vis[y])
      dfs(y);
  }
  vis[x] = false;  //这句话对vis[x]进行回溯，使得能遍历所有路径
}
```

---

## 5、保存路径

dfs回溯遍历所有路径，可以用数组将路径保存起来，一般数组的元素可为路径上的点（或边）。

例如：

```
void dfs(int x) {
  vis[x] = true;
  path[++last] = x;   //保存路径的节点
  for(int i=0; i<g[x].size(); i++) {
    int y = g[x][i];
    if(!vis[y])
      dfs(y);
  }
  vis[x] = false; 
  last--;   //回溯，删除路径上的这个点，给后面其它点用
}
```

---

保存路径之后，在触发某些条件时，就可以输出/计算路径。

例如－输出所有到达fx的路径：

```
void dfs(int x) {
  if(x == fx) { //到达fx点时输出路径
    for(int i=1; i<=last; i++)
      cout<<path[i]<<" ";
    cout<<fx<<" "<<endl; //注意此时fx还没有被数组保存，因此..
    return;
  }
  vis[x] = true;
  path[++last] = x;   //保存路径的节点
  for(int i=0; i<g[x].size(); i++) {
    int y = g[x][i];
    if(!vis[y])
      dfs(y);
  }
  vis[x] = false; 
  last--; 
}
```

`注意`：dfs遍历的顺序，与图的存储有关，因此多个路径的先后不是唯一的。

---

## 6、最长/最短距离

有时候题目不需要输出具体的路径，只需要求出最长/最短距离，就可以在递归回溯的同时直接计算距离，进行最大最小判断。

```
void dfs(int x, int sum) {
  if(x == fx) { //求到达fx的最长距离
    ans = max(ans, sum);
    return;
  }
  vis[x] = true;
  path[++last] = x;   //保存路径的节点
  for(int i=0; i<g[x].size(); i++) {
    int y = g[x][i].y, w=g[x][i].w;
    if(!vis[y])
      dfs(y, sum+w); //传入距离参数，自动回溯
  }
  vis[x] = false; 
  last--; 
}
```

`原理`：在递归函数里传入距离参数，参数是会自动回溯的。

---

`剪枝优化`：对正权图求最小距离，可以剪枝优化，即如果当前dfs函数传入的sum>=ans，则再走下去也肯定会比ans大，因此可以直接返回。

```
void dfs(int x, int sum) {
  if(sum >= ans) return; //剪枝
  if(x == x0) { //求到达x0的最小距离
    ans = min(ans, sum);
    return;
  }
  ......
```

---

# 图的遍历之BFS

---

## 1、队列

队列是一种数据结构，只能从队尾加入元素，从队首弹出元素，特性就是先进入队列的元素先出队，简称FIFO（First In First Out）。

c++的stl里提供了队列容器queue，如下：

* 头文件：#include <queue>
* 变量：queue<int> q;
* 入队：q.push(x);  //插入x到队尾
* 出队：q.pop();   //删除队首的元素（没有获取）
* 访问：q.front();  //访问对首的元素
* 判空：q.empty();
* 个数：q.size();

---

## 2、广度优先搜索

从某个顶点v0出发，依次访问其相邻的每个点，然后逐层向外访问，直到没有可访问点（或找到解）为止。

![](https://cdn.itbegin.com//pics/admin/2019/4/8954d48bdfd24819962405cf80e0c00d.jpg)

---

上图从A点出发进行bfs遍历（蓝色字表示访问顺序）：

* 访问A点（出队），邻接点有B、F、G，入队后队列为BFG
* 访问B点（出队），邻接点有C、D，入队后队列为FGCD
* 访问F点（出队），邻接点无，队列为GCD
* 访问G点（出队），邻接点为D、H，入队后队列为CDH（D重复不再入队）
* 访问C点（出队），邻接点无，队列为DH
* 访问D点（出队），邻接点为E，入队后队列为HE
* 访问H点（出队），邻接点无，队列为E
* 访问E点（出队），邻接点无，队列为空
* 循环结束

---

bfs遍历序列为：ABFGCDHE

可以发现，整个遍历过程是分层进行的，先遍历距离为1的所有顶点，再距离为2的所有顶点，···，直到访问完毕。在距离为x的层未访问完成之前，不会访问距离为x+1的层。

---

层次结构如下图：

![](https://cdn.itbegin.com//pics/admin/2018/11/b4031b81ebd64d34a5bd66b7df13ebba.jpg)

---

## 3、算法实现

伪代码：

```
bfs()
  起点入队
  while (队列不空)
    访问队首元素、出队
    for 队首元素相邻结点
      入队并标记
```

---

使用stl的queue容器：

```
void bfs(int v0) {
  queue<int> q;
  vis[v0] = true;
  q.push(v0);
  while(!q.empty()) {
    int tmp = q.front();
    cout<<tmp;
    q.pop();
    for(tmp的所有邻接点i) {
      if(vis[i]) continue;
      vis[i] = true;
      q.push(i);
    }
  }
}
```

---

## 4、bfs求最短路

无权图或等权图，可以用bfs求单源最短路。

原理：bfs遍历是以起点为中心，一层一层往外扩展，显然最先到达的点的层数就是最短距离。

---

算法实现：

* 定义d[N]数组，表示起点到每个点的最短距离
* 初始值d[sx] = 0
* 在bfs遍历到y时，d[y] = d[x]+1

```
void bfs() {
  queue<int> q;
  vis[sx] = true;
  q.push(sx);
  while(!q.empty()) {
    int x = q.front();
    q.pop();
    for(int i=0; i<g[x].size(); i++) {
      int y = g[x][i];
      if(vis[y]) continue;
      d[y] = d[x]+1;  //最短距离
      vis[y] = true;
      q.push(y);
    }
  }
}
```

---

## 5、最短路径

如果要求出路径（一般指路径上的节点集合），可在求遍历求最短距离过程中存储前趋点。

```
for(int i=0; i<g[x].size(); i++) {
      int y = g[x][i];
      if(vis[y]) continue;
      d[y] = d[x]+1;  
      pre[y] = x;  //前趋点, 初始点pre[sx] = sx
      vis[y] = true;
      q.push(y);
    }
```

---

`理解`：

* pre[y] = x指y是从x过来的，也即最短路径上x是y的父亲
* 参照树的父亲存储法，就会发现pre[N]会构成一棵以起点sx为根的树，即最短路树
* 最短路树上，从起点sx到任意一个点y的路径，就是原图中sx到y的最短路径

由pre[N]输出到某个点y的最短路径，可通过栈或递归函数，例如：

```
void show(int x) {
  if(x != pre[x])
    show(pre[x]);
  cout<<x<<" ";
}
```

---

## 6、迷宫最短路

迷宫一般是二维数组来表示，因此一个点(x1,y1)的可能连接点最多有周围的8个位置，即左上、上、右上、右、右下、下、左下、左，可通过偏移坐标得到，例如左上的偏移坐标是(-1, -1)。

一般可通过偏移数组，用循环来遍历某个点的八个连接点：

```
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1,   1,  1,  0, -1, -1};
for(int i=0; i<8; i++) {
  int x2 = x + dx[i];
  int y2 = y + dy[i];
}
```

---

其它：

* 有时题目会要求只走上下左右四个方向
* 有时题目会规定其它走法，例如马步，如偏移(2, 1)
* 有时题目会增加障碍物，某些坐标不可走

有了移动方式之后，就可将迷宫看成一个图，每个点可移动到周围的点，因此可通过bfs来求最短距离。

同时，求最短路径也可用前趋数组来存储，只是数组元素需要用一个结构体来表示坐标。

```
pre[x2][y2] = (Node) {x, y};
```

---

## 扩展理解－dfs与bfs

### 1、广搜的理解

你的眼镜掉了，你趴在地板上找，先摸一圈最近的地方，如果没有，再往远一点摸过去.....

---

### 2、空间复杂度

dfs占用的是栈的空间（因为递归），每次遍历需要占用等于路径深度的栈空间。

bfs占用的是队列的空间，每次遍历需要占用等于邻接点数目的队列空间。

---

从空间复杂度来说：

* 链状图：bfs好于dfs，用bfs的空间占用只有1个，而dfs就要占用链深度大小的空间。
* 星状图：dfs好于bfs，用bfs的空间占用邻接点数目大小，而dfs只有一层深度。

---

### 3、应用场景

bfs适合用于找一条最短路径（无权图），既一个最优解，也可以理解成一种贪心策略。

dfs使用找所有（最短）路径，既遍历所有的解空间，进行判定，也可以理解成枚举策略。

---

## 连通
----

### 无向图

对于一张无向图 $G = (V, E)$，对于 $u, v \in V$，若存在一条途径使得 $v_0 = u, v_k = v$，则称 $u$ 和 $v$ 是 **连通的 (connected)**。由定义，任意一个顶点和自身连通，任意一条边的两个端点连通。

若无向图 $G = (V, E)$，满足其中任意两个顶点均连通，则称 $G$ 是 **连通图 (connected graph)**，$G$ 的这一性质称作 **连通性 (connectivity)**。

若 $H$ 是 $G$ 的一个连通子图，且不存在 $F$ 满足 $H\subsetneq F \subseteq G$ 且 $F$ 为连通图，则 $H$ 是 $G$ 的一个 **连通块/连通分量 (connected component)**（极大连通子图）。

----

### 有向图

对于一张有向图 $G = (V, E)$，对于 $u, v \in V$，若存在一条途径使得 $v_0 = u, v_k = v$，则称 $u$  **可达**  $v$。由定义，任意一个顶点可达自身，任意一条边的起点可达终点。（无向图中的连通也可以视作双向可达。）

若一张有向图的节点两两互相可达，则称这张图是 **强连通的 (strongly connected)**。

若一张有向图的边替换为无向边后可以得到一张连通图，则称原来这张有向图是 **弱连通的 (weakly connected)**。

---

## 例题与练习

|题目|
|---|
|[小S的城市](http://39.99.183.126:8888/p/CCFPB06E01)|
|[Ladder Takahashi](http://39.99.183.126:8888/p/abc277c)|
|[Count Connected Components](http://39.99.183.126:8888/p/abc284c)|
|[Path Graph?](http://39.99.183.126:8888/p/abc287c)|