图的存储
在讨论图的遍历问题之前，我们先来讨论一下图的存储问题，也就是我们在写程序的时候如何保存、表示一个图。首先我们会用连续的整数编号来表示点集。比如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是不是都被访问过了。根据结果输出答案
