图的存储展开目录
在讨论图的遍历问题之前，我们先来讨论一下图的存储问题，也就是我们在写程序的时候如何保存、表示一个图。首先我们会用连续的整数编号来表示点集。比如 1 号顶点、2 号顶点……
其次，我们有两种方法表示边集。一种叫做邻接矩阵表示法，另一种叫邻接表表示法
邻接矩阵是说我们用一个二维矩阵 A 来表示边集。A~ij~=0 表示顶点 i 和顶点 j 之间不存在边，A~ij~=1 表示顶点 i 和顶点 j 之间存在边。例如：
除了邻接矩阵表示法以外，我们还有一种表示法叫邻接表表示法。图中的每一个顶点 i 都有一个线性表，保存与 i 相连的顶点编号
在程序中，一般用一个数组嵌套 vector 的方法来表示邻接表：vector<int> g [N+1]。g [i] 是一个 vector，可以想象成一个变长数组，里面保存着每一个与 i 相邻的顶点编号。比如与 1 相连的有 2,3,4，在程序中就有 g1 = 2, g1=3, g1=4
图的遍历展开目录
假设这个图是这样:
搜索需要一个起点，我们不妨设从 1 号顶点起始。在搜索过程中，我们维护一个布尔数组 bool visited [N+1]，这个数组用来表示每个顶点是不是已经遍历过了。visited [i]=true 表示顶点 i 已经遍历过了，visited [i]=false 表示 i 还没有遍历过。DFS 一般我们可以用递归实现，如果采用邻接矩阵，伪代码如下：
- Visited[] = {FALSE,FALSE,...FASLE}
- Visited[x] = TRUE
- For i = 1...N
- If !Visited[i] AND A[x][i]
- DFS(i)
当我们执行 DFS (1) 的时候，程序就会开始从 1 号节点开始遍历。注意我们只会对 visited [x] 的值是 FALSE 的顶点 x 执行 DFS (x)，而执行 DFS (x) 的第一句就是令 Visited [x]=TRUE，所以对于 N 个顶点的图，DFS 函数最多被调用 N 次。而每一次 DFS 执行中都要 i 循环从 1 到 N 遍历一遍。所以整个复杂度是 O (N^2)
如果采用邻接表，伪代码如下：
- Visited[] = {FALSE,FALSE,...FALSE}
- Visited[x] = TURE
- For i in g[x]
- If !Visited[i]
- DFS(i)
因为 g [x] 中直接保存了与 x 相连的顶点编号，所以循环 For i in g [x]: 中直接 i 就是 x 的邻居顶点。用邻接表的复杂度是 O (N+M) 的，其中 M 是图的边数
对于上图来说，深度优先搜索的过程是这样的
红色的边代表 DFS 的调用关系，一开始是 DFS (1)->DFS (2)->DFS (3)->DFS (4)。执行 DFS (4) 的时候会发现没有可以继续 DFS 的顶点，会回溯到 DFS (3)。DFS (3) 也回溯到 DFS (2)，DFS (2) 会再回溯到 DFS (1)。DFS (1) 继续执行会调用 DFS (1)->DFS (5)->DFS (6)。最后再从 DFS (6) 回溯到 DFS (1)，结束遍历
下面我们来通过一道题，写一个 DFS 完整的程序
这道题的基本思路就是从 1 号节点出发开始遍历。如果遍历结束时所有 visited [] 数组的值全都是 true，那么就说明整个图是连通的，否则就不是。代码如下：
- #include <iostream>
- #include <vector>
- using namespace std;
- int n,m;
- vector<int> g[100001];
- bool visited[100001],ans;
- void dfs(int x)
- {
- visited[x] = true;
- for(int i : g[x])
- if(!visited[i])
- dfs(i);
- }
- int main()
- {
- cin >> n >> m;
- for(int i = 0;i < n;i++)
- visited[i] = false;
- for(int i = 0;i < m;i++)
- {
- int u,v;
- cin >> u >> v;
- g[u].push_back(v);
- g[v].push_back(u);
- }
- dfs(1);
- ans = true;
- for(int i = 1;i <= n;i++)
- ans = ans && visited[i];
- if(ans)
- cout << "YES" << endl;
- else
- cout << "NO" << endl;
- return 0;
- }
第 16 行是读入顶点数和边数。第 18 行是初始化 visited 数组。第 19 到第 25 行是在读入边集数据，并保存在邻接表里。这里读入边的时候需要注意一些细节
一是重边的问题，也就是输入数据会不会有一条边出现了 1 次以上。比如 u=1， v=2 有一行，u=2，v=1 也有一行。重边在某些情况下是需要特殊处理的，比如去掉重边只保留一条。在这道题中重边不会影响程序的正确性，所以我们没有去重
二是自环的问题，也就是输入数据会不会有 u=v 这样数据。与重边类似，自环在某些情况下也是要特殊处理的。不过在我们这道题中自环仍是无所谓，所以我们也没有处理
第 26 行 dfs (1) 就是从 1 开始进行深度优先搜索。Dfs 函数在第 7-13 行，比较简单明了。首先是第 9 行将当前顶点 x 标记为已经访问过的。然后就是 10~12 行，对于所有在 g [x] 中的顶点 i，也就是与 x 相邻的顶点，如果 i 还没有被访问过，就递归执行 dfs (i)
第 26 行 dfs (1) 函数返回之后，与 1 直接或者间接相连的顶点 x 就应该都被标记为已经访问过 (visited [x]=true)。第 28-29 行我们在检查 visited [1-N] 是不是都是 true，其实就是检查顶点 1~N 是不是都被访问过了。根据结果输出答案
