我们再看看DFS/BFS中图的处理问题。

DFS就是Depth First Search，是一种非常常用的图的遍历方法。深度优先搜索的具体过程这里就不赘述了。我们主要讲讲DFS处理图论问题的方法。

首先我们看一个问题：

给出一张图，判断其是否为连通图？

可能会先提出一个问题。什么是连通图？那我们先了解一下什么是联通。如下图：

走完一遍过程后，我们访问了结点1、2、3、4，因此(1,2,3,4)为一个连通块。

如果不理解这个过程我们可以这样考虑：有6个水槽，标记为1~6号。其中1和2号相连，2与4相连。4与3相连，5与6相连。（就像上面的例子一样）而DFS的过程我们可以想象成倒水。DFS(i)就是往i号水槽里倒水，当往i号水槽倒水的时候，与i相连接的水槽也会逐渐充满水。当我们枚举完整个过程后，我们就能发现所有含水的水槽是一个连通块。

我们得到如下的代码：（用邻接表存储数据）

代码可能理解起来比较困难，因此这里我举个例子：

我构造了上面这个图，我们从1开始做DFS。

1.1可以指向结点2。2进入栈，遍历结点2。此时栈为1，2。

2.2可以指向结点3。3进入栈，遍历结点3。此时栈为1，2，3。

3.3可以指向结点1。1已经在栈中，我们认为该图形成一个环。

栈的元素分别为1，2，3；栈的顺序也体现了从起点到当前点的一条路径。