深度优先搜索算法

原文：https://blog.csdn.net/younglee2013/article/details/49024821
图（graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V,E），其中，G表示一个图，V是图G中顶点的集合,E是图G中边的集合。
无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边（Edge）

上图G1是一个无向图，G1={V1，E1}，其中

-V1={A,B,C,D}，

-E1={(A,B),(B,C),(C,D),(D,A),(A,C)}

-V2={A,B,C,D}，

-E2={<B,A>,<B,C>,<C,A>,<A,D>}
度
以顶点V为终点的边数称为V的入度，以V为头的数目称为V的出度，A的入度为2，出度为1
图的存储结构
邻接矩阵（有向图）
领接矩阵表示法用二维数组来表示图。数组下标对应各顶点的编号。如果顶点i和j之间存在边，那么m[i][j]=1

邻接表（有向图）

邻接矩阵看上去是个不错的选择，首先是容易理解，但是我们也发现，对于边数相对顶点较少的图，这种结构无疑是存在对存储空间的极大浪费。
因此我们可以考虑另外一种存储结构方式，例如把数组和链表结合一起来存储，这种方式在图结构也适用，我们称为邻接表。
!
-图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。

-图中每个 顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储。
一.算法思想：

深度优先遍历图的方法（一种递归的定义）是，假定给定图G的初始状态是所有顶点均未被访问过，在G中选一个顶点i作为遍历的初始点，则深度优先搜索递归调用包含以下操作：

（1）访问搜索到的未被访问的邻接点；

（2）将此顶点标记为已访问节点；

（3）搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此邻接点开始进行同样的访问和搜索。

三.算法实现：

1、使用栈来实现。相关算法实现总结为：

（1)      将初始节点压栈。

（2）      While(栈非空) {

（3）          取出栈顶点，暂时存储这个节点node_t信息。

（4）          访问该节点，并且标示已访问。

（5）          将栈顶元素出站。

（6）          For(遍历node_t的相邻的未访问过的节点){

（7）                将其入栈。

                                    }

                               }

2.  使用递归来实现。相关算法实现总结为：
   
        （1）      DFS（初始节点）
   
        （2）      Function DFS(一个节点) {
   
        （3）          访问该节点，并且标示已访问。
   
        （4）          For(遍历该节点的相邻的未访问过的节点) {
   
        （5）                DFS（这个邻接节点）。
   
                             }
   
                        }
   

   四.算法运用：

   1.图的遍历。

   2.判断图是否存在环路。

   3.迷宫问题。

   4.对某些问题进行穷举等等。。。。
   5、给定初始状态跟目标状态，要求判断从初始状态到目标状态是否有解。