深度优先搜索（DFS）

深度优先搜索百度定义

图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。

它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

显然，深度优先搜索是一个递归的过程。

以图为例：

对上图进行深度优先搜索
步骤：
第一步： 搜索节点A

第二步 ：搜索A的临节点B

在第1步访问A之后，接下来应该访问的是A的邻接点，即”B,C”中的一个。但在本文的实现中，顶点ABCDEF是按照顺序存储，B在”C”的前面，因此，搜索问B。

第三步：搜索B的临节点D

第四步：搜索D的临节点E

第五步：E没有临节点，回退到D，再回退到B，再回退到A，发现A的临节点C没有被搜索，访问C

第六步：访问C的临节点F

最终搜索的顺序是A->B->D->E->C->F

对于整个过程，编程实现其实有两个注意点！

1>记录已经搜索的点,伪代码如下

if (0 == flag[A]) {
    访问A节点信息；
    flag[A] = 1;
}

2>回退，这也是搜索算法的核心点，我们可以采用递归，也可以使用栈进行存储，其实递归调用也是通过一个隐形栈来实现，即将整个程序的运行空间安排在一个栈中。每当运行一个函数时，就在栈顶分配空间，函数退出后，释放这块空间。当前运行的函数一定在栈顶。

假设搜索节点的函数是SearchNodeInfo(Node* pNode);，根节点是pRoot,也就是A（开始搜索的节点）
DFS算法可以这样实现：伪代码

SearchNodeInfo(Node* pNode) 
{
    if (NULL == pNode || 1 == flag[pNode->flag]) {
        return;//递归函数最重要的就是退出点
    }
    for (int i = 0; i < pNode->sonNumber; ++i) {
        if (0 == flag[pNode->son[i]]) {
            SearchNodeInfo(pNode->son[i]);
        }
    }
    访问pNode节点信息//具体是干啥要看实际需求
    flag[pNode->flag] = 1;//函数退出的关键
    return;
}

int main
{
    初始化所有的Node->flag = 0;
    SearchNodeInfo(pRoot);
    return 0;
}

来复盘一下上图的搜索过程

在主函数里面调用SearchNodeInfo(pRoot);
这个图的存储方式B,C是A的儿子，E是D，B的儿子，F是C的儿子 。

根节点pRoo是A，首先进入函数的是

即 1：把函数SearchNodeInfo（A节点）入栈
进入第一for（A的儿子）
2:把SearchNodeInfo（B节点）入栈（B是A的第一个儿子）
进入第二个for（B的儿子）
3：把SearchNodeInfo（D节点）入栈（D是B的第一个儿子）
然后对于第二个for
4：把SearchNodeInfo（:E节点）入栈（E是B的第一个儿子）
由于ED都没有儿子了，没有For循环，直接访问节点信息
然后退出。
然后第二个for退出，访问E，再访问B
由于第二for退出，这个时候回退到第一个For
5：把SearchNodeInfo（C节点）入栈（C是A的第二个儿子）
6：把SearchNodeInfo（F节点）入栈（F是C的唯一儿子）
然后访问F， C
然后第二个for退出访问A信息

大概的意思就是

//对于最外层A
Search(A);
for（int i = 0； i < A->sonNumber; ++i） {
   Search(B)；
   for(int j = 0； j < B->sonNumber; ++j) {
       Search(D);
       for(int k = 0； k < D->sonNumber; ++k) {
           Search(E);
           //E没有儿子，直接访问E节点信息然后退出
           对于这个for D只有一个儿子，退出这层for
       }
       访问D节点信息
       对于这个for B有两个儿子，但是E已经被访问退出这层for
   }
   访问B节点信息，然后对于A节点来说
   继续搜索A的第二个儿子C
   Search(C)；
   for(int l = 0; l < C->sonNumber) {
       //由于F没有儿子直接访问F信息
       退出这层for
   }
   访问C节点信息
}
访问A

以上是实际的调用顺序，及过程。方便理解，这可能是不能再详细的，不能再底层的逻辑了

下面我们来一道题练练手；这是DFS的实际运用

给你很多很多个数字 a1,a2,a3,a4……..an,
你能帮我选出若干个数字，使得他们的和等于k

思路：
对于每个数，只有用与不用两种可能，所以考虑状态转移时，分两种情况。设DFS（i，m）为已经考虑完前i-1个数（从0开始），且前i-1个数和为m，此时，如果m==k，可以立即返回结果（查找成功），如果m！=k，若加入第i个数，状态转移为DFS（i+1，m+ai），若不加，状态转移为DFS（i+1，m）。递归直至i==n，若此时仍未有符合要求的解，返回0。这个算法的复杂度为O(2^n)，复杂度为指数级，只能用于处理较小的数据量。

深度优先搜索是一种搜索思路，它从某个状态开始，不断地转移状态直到找到结果或无法转移，然后回退到前一步的状态，继续转移至其他状态，如此不断重复，直至找到最终解。一般采用递归方式。

代码：

    #include<stdio.h>  
    int n,k;  
    int s[100];  
    int DFS(int i,int m)  
    {  
        if(m==k)//结束条件1：找到符合要求的解。  
            return 1;  
        if(i==n)//结束条件2：未找到符合要求的解且当前状态无法再拓展至下一状态。  
            return 0;  
        if(1 == DFS(i+1,m+s[i])|| 1 == DFS(i+1,m))//从当前状态拓展至下一状态。  
            return 1;  
        else return 0;  
    }  
    int main()  
    {  
        scanf("%d%d",&n,&k);  
        for(int i=0;i<n;i++)  
        {  
            scanf("%d",&s[i]);  
        }  
        if(DFS(0,0))  
            printf("Yes\n");  
        else printf("No\n");  
        return 0;  
    }