DFS

图简介
给定一幅由节点和边组成的图G（V，E），V是顶点的集合，E表示边的集合。顶点是对现实对象的一种抽象，而边表示的是两个对象之间一定的关系。

图片

图在计算机中的存储方式有：矩阵存储（适用于稠密的图），邻接表存储（适合稀疏图）。

例：无向图的矩阵

图片说明

图又分有向图和无向图，无向图的矩阵表示是一个对称矩阵（M(i,j)=M(j,i)），有向图的矩阵则不一定对称。

图还有无权图和有权图之分。无权图的矩阵里的数值只表示是否连通，而有权图矩阵里的数值大小可表示价值、距离、代价等现实意义。

图的遍历

当我们需要从图中获取信息时，我们就需要访问图的节点，用dfs的目的不唯一，可能是为了查找是否存在某个节点，可能是要数图中有多少个环，或者判断图能否一笔画等等。

重点是避免重复访问也不能漏掉一些节点。

图的遍历方式有深度优先遍历（DFS）和广度优先遍历（BFS）两种。本文只介绍深度优先遍历。

所谓DFS，通俗的理解就是，当我访问完一个节点（v1）后，我从与当前节点相邻且未访问过的节点集合（S）中拿出一个来，对选出来的这个节点(v2)我们重复与前一个节点相同的过程，直到没有满足条件的节点可以被访问，于是我们退回到v1处，从S中再选出一个未被访问过的节点进行上述过程，直到整张图的节点都被访问过。

以上的描述很明显具有递归结构。我们也知道，递归算法都可以用栈来实现。

DFS算法递归实现的框架如下：

1 procedure DFS(G, V) is 
2      将顶点V标记为 “已遍历”
3      对于 V 的所有邻接点 W 
4             如果 w 未被遍历过 则
5                  深度优先遍历 （G，W）

我们需要一个数组来记录某个节点是否访问过。

用栈来实现DFS算法

栈的特点是先进后出(Fisrt in last out), 利用这个特点，我们可以在访问当前节点之后，把它所有当前未被访问的邻点入栈，然后弹出栈顶元素，即最后一个入栈的节点。对弹出的节点标记为已访问，然后同样把他的所有当前未被访问的邻点入栈（后入栈的节点会比先入栈的节点先出来，以此达到了深度优先遍历的目的）。这样一直进行下去，直到栈空。

procedure DFS-iterative(G, v) is
let S be a stack          //声明s为一个栈
S.push(v)                    //根节点（起始节点）入栈
while S is not empty do    //栈不空时一直循环
       v = S.pop()   //弹出栈顶元素赋值给v
       label v as visited   //标记v为已访问

        //v的所有未被访问的邻点中入栈
        for all edges from v to w in G.adjacentEdges(v) do

                 if w is unvisited S.push(w)

注意以上程序只能访问一个连通枝中的节点，若要访问一个不连通的图中的中的所有节点，只需要在该程序以外加一个大循环，从未被访问过的节点开始访问其他的连通枝即可。

复杂度分析：

DFS算法需要借助一个递归工作栈和一个标记是否访问的数组，故它的空间复杂度为O(N)。N为节点个数。
遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用结构。
邻接表表示时，查找所有顶点的邻接点所需时间为O(E)，访问顶点的邻接点所花时间为O(N),此时，总的时间复杂度为O(N+E) 。

邻接矩阵表示时，查找每个顶点的邻接点所需时间为O(N) ，要查找整个矩阵，故总的时间度为 O(N^2) 。