深度优先搜索 订阅
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止,然后返回到某一个HTML文件,再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时,说明搜索已经结束。 [1] 展开全文
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止,然后返回到某一个HTML文件,再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时,说明搜索已经结束。 [1]
信息
提出者
霍普克洛夫特与罗伯特·塔扬
应用学科
计算机
中文名
深度优先搜索
外文名
Depth-First-Search
深度优先搜索详细解释
事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.举例说明之:下图是一个无向图,如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C,D),则我们可能得到如下的一个访问过程:A->B->E(没有路了!回溯到A)->C->F->H->G->D(没有路,最终回溯到A,A也没有未访问的相邻节点,本次搜索结束). 简要说明深度优先搜索的特点:每次深度优先搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.如果将每个节点在深度优先搜索过程中的"结束时间"排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下,将该节点加入list结尾,然后逆转整个链表),则我们可以得到所谓的"拓扑排序",即topological sort. [1] 
收起全文
精华内容
下载资源
问答
  • 深度优先搜索

    万次阅读 多人点赞 2017-08-10 09:01:35
    深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在...

      深搜

    (一):解释与理解

    深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链HTML文件) 。在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止,然后返回到某一个HTML文件,再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时,说明搜索已经结束。

    事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能

    的分支路径深入到不能再深入为止,而且每个节点只能访问一次。深度优先搜索的缺点也出来了:难以寻找最优解,

    仅仅只能寻找有解。其优点就是内存消耗小。

    图

    举例说明之:上图是一个无向图,如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既

    可以是B也可以是C,D),则我们可能得到如下的一个访问过程:A->B->E(没有路了!回溯到A)->C->F->H->G->D

    (没有路,最终回溯到A,A也没有未访问的相邻节点本次搜索结束)简要说明深度优先搜索的特点:每次深度优

    搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.如果将每个节点在深度优先搜索过程中的"结束时

    间"排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下,将该节点加入list结尾,然后逆转

    整个链表),则我们可以得到所谓的"拓扑排序",即topological sort.


    (二):基本思路

    深度优先遍历图的方法是,从图中某顶点v出发:
    (1)访问顶点v;
    (2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;
    (3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点
    均被访问过为止。
    我们将所要解答的问题划分成若干个阶段或者步骤,当一个阶段计算完毕,下面往往有多种可选选择,所有的选择
    共同组成了问题的解空间,对搜索算法而言,将所有的阶段或步骤画出来就类似是树的结构(如图)。从根开始计
    算,到找到位于某个节点的解,回溯法(深度优先搜索)作为最基本的搜索算法,其采用了一种“一只向下走,走不
    通就掉头”的思想(体会“回溯”二字),相当于采用了先根遍历的方法来构造搜索树。
    如果搜索是以接近起始状态的程序依次扩展状态的,叫宽度优先搜索
    如果扩展是首先扩展新产生的状态,则叫深度优先搜索。
    深度优先搜索
    深度优先搜索用一个数组存放产生的所有状态。
    (1) 把初始状态放入数组中,设为当前状态;
    (2) 扩展当前的状态,产生一个新的状态放入数组中,同时把新产生的状态设为当前状态;
    (3) 判断当前状态是否和前面的重复,如果重复则回到上一个状态,产生它的另一状态;
    (4) 判断当前状态是否为目标状态,如果是目标,则找到一个解答,结束算法。
    (5) 如果数组为空,说明无解。
    (三):图文介绍
    参考这位大牛的讲解整理
    http://www.cnblogs.com/skywang12345/p/3711483.html

    ①:无向图的深度优先搜索

    下面以"无向图"为例,来对深度优先搜索进行演示。

    对上面的图G1进行深度优先遍历,从顶点A开始。

    第1步:访问A。 
    第2步:访问(A的邻接点)C。 
        在第1步访问A之后,接下来应该访问的是A的邻接点,即"C,D,F"中的一个。但在本文的实现中,顶点ABCDEFG

    是按照顺序存储,C在"D和F"的前面,因此,先访问C。 
    第3步:访问(C的邻接点)B。 
        在第2步访问C之后,接下来应该访问C的邻接点,即"B和D"中一个(A已经被访问过,就不算在内)。而由于B在D

    之前,先访问B。 

    第4步:访问(C的邻接点)D。 
        在第3步访问了C的邻接点B之后,B没有未被访问的邻接点;因此,返回到访问C的另一个邻接点D。 
    第5步:访问(A的邻接点)F。 
        前面已经访问了A,并且访问完了"A的邻接点B的所有邻接点(包括递归的邻接点在内)";因此,此时返回到访问

    A的另一个邻接点F。 
    第6步:访问(F的邻接点)G。 
    第7步:访问(G的邻接点)E。

    因此访问顺序是:A -> C -> B -> D -> F -> G -> E

     

    ②:有向图的深度优先搜索

    下面以"有向图"为例,来对深度优先搜索进行演示。

    对上面的图G2进行深度优先遍历,从顶点A开始。

    第1步:访问A。 
    第2步:访问B。 
        在访问了A之后,接下来应该访问的是A的出边的另一个顶点,即顶点B。 
    第3步:访问C。 
        在访问了B之后,接下来应该访问的是B的出边的另一个顶点,即顶点C,E,F。在本文实现的图中,顶点ABCDEFG

    按照顺序存储,因此先访问C。 
    第4步:访问E。 
        接下来访问C的出边的另一个顶点,即顶点E。 
    第5步:访问D。 
        接下来访问E的出边的另一个顶点,即顶点B,D。顶点B已经被访问过,因此访问顶点D。 
    第6步:访问F。 
        接下应该回溯"访问A的出边的另一个顶点F"。 
    第7步:访问G。

    因此访问顺序是:A -> B -> C -> E -> D -> F -> G

    DFS函数的调用堆栈

    此后堆栈调用返回到V0那一层,因为V1那一层也找不到跟V1的相邻未访问节点

     

    此后堆栈调用返回到V3那一层

     

    此后堆栈调用返回到主函数调用DFS(V0,0)的地方,因为已经找到解,无需再从别的节点去搜别的路径了。

    (四):例题代码理解

    ①:这第一个代码是从网上淘的;

    HDU-1181

    Sample Input

    so
    soon
    river
    goes
    them
    got
    moon
    begin
    big
    0
    Sample Output
    Yes.

    复制代码
     1 //DFS模板题 HDU 1181
     2 
     3 #include <iostream>
     4 #include <string.h>
     5 #include <queue>
     6 #include <string>
     7 using namespace std;
     8 string str[300];
     9 int vis[300],i;//标记数组,在一条路径中,被查找过的节点不能被再次查找,不然就会使路径出现循环
    10 int flag = 0;//用于判定搜索是否查找到路径
    11 void dfs(string use)
    12 {
    13     char last = use[use.length() - 1];
    14     if (flag == 1)//如果已经找到了就直接结束,减少不必要的搜索过程
    15         return;
    16     for (int k = 0;k<i;k++)//如果视当前use字符串为当前节点,那么for循环就应该遍历下一层的所有可能节点
    17     {
    18         if (vis[k] == 0&& str[k][0] == last)//如果未被访问,且其首字符合本节点末字符匹配,就可以作为搜索树的分支节点
    19         {
    20             vis[k] = 1;//每确定路径中的一个节点,就标记起来
    21             if (str[k][str[k].length() - 1] == 'm')//满足搜索的结束条件就设置flag并退出
    22             {
    23                 flag = 1;
    24                 return;
    25             }
    26             else
    27                 dfs(str[k]);//否则继续向下搜索
    28             //vis[k]=0
    29             //大部分DFS在一条路径搜索失败后都需要回溯到上一状态
    30             //通常需要把从本节点后产生的标记都重置
    31             //实际上是否需要重置标记,应该看路径来源是否会对节点能否到达出口产生影响
    32             //在本题中。如果str[k]是到所求路径中的一个节点,不管从什么途径搜索到了str[k],都不影响他到达终点。
    33         }
    34     }
    35 }
    36 int main() {
    37     
    38     while (cin >> str[i])
    39     {
    40         if (str[i] == "0")
    41         {
    42             memset(vis, 0, sizeof(vis));
    43             flag = 0;
    44             for (int j = 0;j<i;j++)
    45             {
    46                 if (str[j][0] == 'b')//如果满足起始条件就进入搜索过程
    47                 {
    48                     vis[j] = 1;
    49                     dfs(str[j]);
    50                 }
    51             }
    52             i = 0;//有多组测试样例,每完成一组,重置i
    53             if (flag == 1)
    54                 cout << "Yes." << endl;
    55             else
    56                 cout << "No." << endl;
    57         }
    58         else
    59             i++;
    60     }
    61     return 0;
    62 }
    而且我还看了一个比较还理解的代码;
    #include<cstdio>
    #include<cstring>
    #include<string>// string 是c++ 的字符串数据类型 *(s[v].end()-1) 这是字符串尾字母 *(s[j].begin()  这是字符串首字母
    #include<iostream>
    using namespace std;
    string str,s[1000],a[1000];
    int mark[1000],i,flag;
    char x,y;
    void dfs(int v)
    {
        if(*(s[v].end()-1)=='m')//当查到有可以连接且尾字母是 m  的标记  一下说明可以完成任务了  ,此处标记完就可以
    //结束了,就你没有必要再查了,因为你已经完成任务了    flag =1  后加一个 return ; 就结束了
            flag=1;
        else
        {
            for(int j=1;j<=i;j++)
            {
                if(!mark[j]&&*(s[j].begin())==*(s[v].end()-1))// 如果单词没被查过且符合要求首尾可以相连的
                {
                    mark[j]=1;
                    dfs(j);
                    //mark[j]=0;//  此处就不用标记回溯了,因为当你查到某个单词结束时就说明这条线已经走不通了,
    //所以说这个单词就没必要再查了
                }
    
    
            }
        }
    }
    int main()
    {
    
    
        while(cin>>str)
        {
             i=2;
            if(str=="0") //如果是没有单词就是完成不了任务也需要输出
            {
                printf("NO\n");
                continue;
            }
            else
                s[1]=str;
            while(cin>>str,str!="0")
            {
                s[i++]=str;
            }
            flag=0;
            for(int j=1;j<=i;j++)
            {
                if(*(s[j].begin())=='b')//因为开始必须是b 所以直接找出b开头的位置节省时间
                {
                    memset(mark,0,sizeof(mark));
                    mark[j]=1;//找到后标记一下从此位置开始查
                    dfs(j);
                }
            }
            if(flag)
                printf("Yes.\n");
            else
                printf("No.\n");
        }
    
    
        return 0;
    }
    


    ②:下面是我自己根据啊哈!算法中的解救啊哈所写的代码:

    问题介绍:迷宫由n行m列的单元格组成(n和m都小于等于50),每个单元格要么是空地,要么是障碍物。你的任务是帮助小哼找到一条从迷宫的起点通往小哈所在位置的最短路径。


    分析:①:首先我们可以用一个二维数组来存储这个迷宫,刚开始的时候,小哼处于迷宫的入口处(1,1),小哈在(p,q)。我们只能一个一个地去尝试,我们可以让小哼往右边走,直到走不通的时候再回到这里,再去尝试另外一个方向。我们规定一个顺序,按照顺时针的方向来尝试(即按照右下左上的顺序去尝试)。

    ②:现在我们尝试用深度优先搜索来实现这个方法。先来看dfs()函数如何写。dfs()函数的功能是解决当前应该怎么办。小哼处在某个点的时候需要处理的是:先检查小哼是否已经到达小哈的位置,如果没有达到则找出下一步可以走的地方。为了解决这个问题,dfs()函数需要三个参数,分别是当前的这个点x,y,以及已经走的步数step;

    ③:判断是否已经到达小哈的位置这一点很好实现,只需判断当前的坐标和小哈的坐标是否相等就可以了,如果相等就可以了,表明已经到达小哈的位置,

    ④:如果没有到达则需找出下一步可以走的地方,因为有四个地方可以走,根据之前的约定(右下左上),需要我们定义一个nexts数组,通过这个数组使用循环就很容易获得下一步的坐标,下一步的横坐标tx,下一步的纵坐标ty;

    for(int k=0;i<4;k++)

    {

    //计算的下一个点的坐标

    tx=x+nexts[k][0];

    ty=y+nexts[k][1];

    }

    ⑤:接下来要对下一个点进行判断。包括是否越界,是否有障碍物,以及这个点已经在路径中(即避免重复访问一个点)。需要用book[tx][ty]来记录格子(tx,ty)是否已经在路径中。

    如果这个点符合要求,就对这个点进行一步的扩展,即dfs(tx,ty,step+1),注意这里是step+1,因为一旦你从这个点开始继续往下尝试,就意味着你的步数已经增加了1。代码实现如下:

    for(int k=0;k<=3;k++)

    {

    //计算的下一个点的坐标

    ...;

    ...;//同上

    //判断是否越界

    if(tx<1||tx>n||ty<1||ty>m)

    continue;

    //判断该点是否为障碍物或则已经在路径中

    if(a[tx][ty]==0&&book[tx][ty]==0)

    {

    book[tx][ty]=1;//标记这个点已经走过了

    dfs(tx,ty,step+1);//开始尝试下一个点

    book[tx][ty]=0;//尝试结束,取消这个点的标记

    }

    }

    好了,看一下完整的的代码吧!!

    #include<stdio.h>

    int n,m;

    int p,q,min==9999999;

    int a[51][51],book[51][51];

    void dfs(int x,int y,int step)

    {

    int next[4][2]={{0,1}//向右走

    {1,0}//向下走

    {0,-1}//向左走

    {-1,0}};//向上走

    int tx,ty,k;

    if(x==p&&y==q)

    {

    //更新最小值

    if(step<min)

    min=step;

    return ;//这里的返回很重要

    }

    //枚举四种走法

    for(k=0;k<4;k++)

    {

    //计算下一点的坐标

    tx=x+next[k][0];

    ty=y+next[k][1];

    //判断是否越界

    if(tx<1||tx>n||ty<1||ty>m)

    continue;

    //判断该点是否是障碍物或则已经在路径中

    if(a[tx][ty]==0&&book[tx][ty]==0)

    {

    book[tx][ty]=1;

    dfs(tx,ty,step+1);

    book[tx][ty]=0;

    }

    }

    return ;

    }

    int main()

    {

    int i,j,startx.starty;

    //读入n行,m列;

    scanf("%d %d",&n,&m);

    //读入迷宫

    for(i=1;i<=n,i++)

    for(j=1;j<=m;j++)

    scanf("%d",%a[i][j]);

    //读入起点和终点

    scanf("%d%d%d%d",&startx,&starty,&p,&q);

    //从起点开始搜索

    book[startx][starty]=1;//已经标记在路径中,防止后面重负走

    //第一个参数是期待你的x坐标,第二个参数是起点的y坐标,第三个参数是初始步数0

    dfs(startx,starty,0);

    //输出最短的步数

    printf("%d",min);

    getchar();

    return 0;

    }

    测试数据:

    5 4

    0 0 1 0

    0 0 0 0

    0 0 1 0 

    0 1 0 0

    0 0 0 1

    1 1 4 3

    结果:

    7

    ③:从网上又搜了一些:

    1.题目描述

    想必大家都玩过一个游戏,打牌游戏,叫做“24点”:给出4个整数(A(1),J(11),Q(12),K(13)),要求用加减乘除4个运算使其运算结果变成244个数字要不重复的用到计算中。

    例如给出4个数:A(1)234。我可以用以下运算得到结果24

    1*2*3*4 = 24;2*3*4/1 = 24(1+2+3)*4=24;……

    如上,是有很多种组合方式使得他们变成24的,当然也有无法得到结果的4个数,例如:1111

    现在我给你这样4个数,你能告诉我它们能够通过一定的运算组合之后变成24吗?这里我给出约束:数字之间的除法中不得出现小数,例如原本我们可以1/4=0.25,但是这里的约束指定了这样操作是不合法的。

    2.解法:搜索树

    这里为了方便叙述,我假设现在只有3个数,只允许加法减法运算。我绘制了如图5-1的搜索树。


    5-1

     

    此处只有3个数并且只有加减法,所以第二层的节点最多就6个,如果是给你4个数并且有加减乘除,那么第二层的节

    点就会比较多了,当延伸到第三层的时候节点数就比较多了,使用BFS的缺点就暴露了,需要很大的空间去维护那个队列。而你看这个搜索树,其实第一层是3个数,到了第二层就变成2个数了,也就是递归深度其实不会超过3层,所以采用DFS来做会更合理,平均效率要比BFS


    1. #include<stdio.h>  
    2. #include<iostream>  
    3. #include<algorithm>  
    4. using namespace std;  
    5. int flag;  
    6. char a[4];  
    7. int b[4];  
    8. //搜索到第4层的时候 进行判断 如果没有到第4层的话 就加减乘除这一层的数  
    9. void dfs(int cur,int zhi) {  
    10.     if(cur==4) {  
    11.         if(zhi==24)  
    12.             flag=1;  
    13.         else  
    14.             flag=0;  
    15.         return;  
    16.     }  
    17.     else {  
    18.         dfs(cur+1,zhi+b[cur+1]);  
    19.         if(flag)  
    20.         return;  
    21.         dfs(cur+1,zhi-b[cur+1]);  
    22.          if(flag)  
    23.         return;  
    24.         dfs(cur+1,zhi*b[cur+1]);  
    25.          if(flag)  
    26.         return;  
    27.         if(cur<=2 && zhi % b[cur+1] == 0) {  
    28.         dfs(cur+1,zhi/b[cur+1]);  
    29.          if(flag)  
    30.         return;  
    31.         }  
    32.     }  
    33. }  
    34. int main() {  
    35.     for(int i=0;i<4;i++) {  
    36.         cin>>a[i];  
    37.         if(a[i]=='A')  
    38.             b[i]=1;  
    39.         else if(a[i]=='J')  
    40.             b[i]=11;  
    41.         else if(a[i]=='Q')  
    42.             b[i]=12;  
    43.         else if(a[i]=='K')  
    44.             b[i]=13;  
    45.         else  
    46.             b[i]=a[i]-'0';  
    47.         }  
    48.     flag=0;  
    49.     //全排列 总共24中情况的话 每种都做下来 随后进行深搜 有一种情况遇到即可  
    50.     sort(b, b+4);  
    51.     do{  
    52.         dfs(0,b[0]);  
    53.     }while(next_permutation(b,b+4)&&!flag);  
    54.     if(flag)  
    55.         cout<<"Y"<<endl;  
    56.     else  
    57.         cout<<"N"<<endl;  
    58.     return 0;  

    测试数据:



    (五):知识点

    讲一下这段代码中的next_permutation(b,b+4)这个是什么意思:

    next_permutation()函数功能是输出所有比当前排列大的排列,顺序是从小到大。

    而prev_permutation()函数功能是输出所有比当前排列小的排列,顺序是从大到小。

    组合数学中经常用到排列,这里介绍一个计算序列全排列的函数:next_permutation(start,end),和prev_permutation(start,end)。这两个函数作用是一样的,区别就在于前者求的是当前排列的下一个排列,后一个求的是当前排列的上一个排列。至于这里的“前一个”和“后一个”,我们可以把它理解为序列的字典序的前后,严格来讲,就是对于当前序列pn,他的下一个序列pn+1满足:不存在另外的序列pm,使pn<pm<pn+1.


    对于next_permutation函数,其函数原型为:

         #include <algorithm>

         bool next_permutation(iterator start,iterator end)

    当当前序列不存在下一个排列时,函数返回false,否则返回true


    我们来看下面这个例子:

    [cpp] view plain copy
    1. #include <iostream>  
    2. #include <algorithm>  
    3. using namespace std;  
    4. int main()  
    5. {  
    6.     int num[3]={1,2,3};  
    7.     do  
    8.     {  
    9.         cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;  
    10.     }while(next_permutation(num,num+3));  
    11.     return 0;  
    12. }  
    若是while(next_permutation(num,num+3))

    {

    count<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;

    }

    这样只执行了一次;即:如果你输入3,输出结果是 123;

    输出结果为:


    next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列,同时并改变num数组的值。

    另外,需要强调的是,next_permutation()在使用前需要对欲排列数组按升序排序,否则只能找出该序列之后的全排列数。比如,如果数组num初始化为2,3,1,那么输出就变为了:



    此外,next_permutation(node,node+n,cmp)可以对结构体num按照自定义的排序方式cmp进行排序。



    展开全文
  • DFS(深度优先搜索算法)

    万次阅读 多人点赞 2018-10-07 16:32:43
    深度优先搜索算法(Depth First Search,简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到...

    基本概念

    深度优先搜索算法(Depth First Search,简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

    算法思想

    回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。 

     

    基本模板

    int check(参数)
    {
        if(满足条件)
            return 1;
        return 0;
    }
    
    void dfs(int step)
    {
            判断边界
            {
                相应操作
            }
            尝试每一种可能
            {
                   满足check条件
                   标记
                   继续下一步dfs(step+1)
                   恢复初始状态(回溯的时候要用到)
            }
    }   

    问题示例

    1、全排列问题

    //全排列问题
    #include<stdio.h>
    #include<string.h>
    
    int n;
    char  a[15];
    char re[15];
    int vis[15];
    //假设有n个字符要排列,把他们依次放到n个箱子中
    //先要检查箱子是否为空,手中还有什么字符,把他们放进并标记。
    //放完一次要恢复初始状态,当到n+1个箱子时,一次排列已经结束
    void dfs(int step)
    {
        int i;
        if(step==n+1)//判断边界
        {
            for(i=1;i<=n;i++)
                printf("%c",re[i]);
            printf("\n");
            return ;
        }
        for(i=1;i<=n;i++)//遍历每一种情况
        {
            if(vis[i]==0)//check满足
            {
                re[step]=a[i];
                vis[i]=1;//标记
                dfs(step+1);//继续搜索
                vis[i]=0;//恢复初始状态
            }
        }
        return ;
    }
    
    int main(void)
    {
        int T;
        scanf("%d",&T);
        getchar();
        while(T--)
        {
            memset(a,0,sizeof(a));
            memset(vis,0,sizeof(vis));//对存数据的数组分别初始化
            scanf("%s",a+1);
            n=strlen(a+1);
            dfs(1);//从第一个箱子开始
        }
        return 0;
    }

    2、一个环由个圈组成,把自然数1,2,…,N分别放在每一个圆内,数字的在两个相邻圈之和应该是一个素数。 注意:第一圈数应始终为1。

    input: N(0~20)

    output:输出格式如下所示的样品。每一行表示在环中的一系列圆号码从1开始顺时针和按逆时针方向。编号的顺序必须满足上述要求。打印解决方案的字典顺序。

    //Prime Ring Problem
    //与上面的全排列问题其实思路差不多,只是需要判断的条件比较多
    //化大为小
    
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    int book[25];
    int result[25];
    int n;
    int num;
    //判断是否为素数
    int prime(int n)
    {
        if(n<=1)
            return 0;
        int i;
        for(i=2;i*i<=n;i++)
        {
            if(n%i==0)
                break;
        }
        if(i*i>n)
            return 1;
        return 0;
    }
    //判断是否能将当前的数字放到当前的圈内
    int check(int i,int step)
    {
        if((book[i]==0) && prime(i+result[step-1])==1)
        {
            if(step==n-1)
            {
                if(!prime(i+result[0]))
                    return 0;
            }
            return 1;
        }
        return 0;
    }
    
    void dfs(int step)
    {
        if(step==n)//判断边界
        {
            int a;
            printf("%d",result[0]);
            for(a=1;a<n;a++)
            {
                printf(" %d",result[a]);
            }
            printf("\n");
            return ;
        }
        int i;
        for(i=2;i<=n;i++)//遍历每一种情况
        {
            if(check(i,step))//check是否满足
            {
                book[i]=1;//标记
                result[step]=i;//记录结果
                dfs(step+1);//继续往下搜索
                book[i]=0;//恢复初始状态
            }
        }
    }
    
    int main(void)
    {
    
        while(scanf("%d",&n)!=EOF)
        {
            num++;
            memset(result,0,sizeof(result));
            memset(book,0,sizeof(book));
            result[0]=1;
            printf("Case %d:\n",num);//格式比较容易出错
            dfs(1);
            printf("\n");
        }
        return 0;
    }
    

    3、油田问题

    问题:GeoSurvComp地质调查公司负责探测地下石油储藏。 GeoSurvComp现在在一块矩形区域探测石油,并把这个大区域分成了很多小块。他们通过专业设备,来分析每个小块中是否蕴藏石油。如果这些蕴藏石油的小方格相邻,那么他们被认为是同一油藏的一部分。在这块矩形区域,可能有很多油藏。你的任务是确定有多少不同的油藏。

    input: 输入可能有多个矩形区域(即可能有多组测试)。每个矩形区域的起始行包含m和n,表示行和列的数量,

    1<=n,m<=100,如果m =0表示输入的结束,接下来是n行,每行m个字符。每个字符对应一个小方格,并且要么是’*’,代表没有油,要么是’@’,表示有油。

    output: 对于每一个矩形区域,输出油藏的数量。两个小方格是相邻的,当且仅当他们水平或者垂直或者对角线相邻(即8个方向)。

    //A - Oil Deposits 
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    char a[105][105];
    int n,m,result;
    int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};//表示8个方向
    
    int check(int x,int y)//检查是否有油田
    {
        if(x>=0&&x<m&&y>=0&&y<n&&a[x][y]=='@')
            return 1;
        return 0;
    }
    
    int dfs(int x, int y)
    {
        int i,xx,yy;
        if(check(x,y))
        {
            a[x][y]='.'; //统计之后就可以把该油田标记,且不用恢复(要不会重复),
                        //也可以用一个数组来存每个点的访问情况,但是感觉没必要,浪费空间
            for(i=0;i<8;i++)
            {
                xx=x+dir[i][0];
                yy=y+dir[i][1];
                dfs(xx,yy);//依次检查8个方向
            }
            return 1;
        }
        return 0;
    }
    
    int main(void)
    {
        int i,j;
        while(scanf("%d %d",&m,&n)==2)
        {
            if(m==0&&n==0)
                break;
            result = 0;
            memset(a,0,sizeof(a));
            for(i=0;i<m;i++)
                scanf("%s",a[i]);
            for(i=0;i<m;i++)//在每一个点都搜索一次
            {
                for(j=0;j<n;j++)
                {
                    if(dfs(i,j))//找到油田就可以将结果加1
                        result++;
                }
            }
            printf("%d\n",result);
        }
        return 0;
    }

    4、棋盘问题

    问题:在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。

    input: 输入含有多组测试数据。 每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。

    output:对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    int n, k, ans;
    char str[10][10];
    int vis[100];
    
    void dfs(int r, int k)
    {
        if(k==0)//判断边界,此时棋子已经放完
        {
            ans++;
            return;
        }
    
        for(int i=r; i<n; i++)//每次都从放过棋子下一行开始搜索,保证不重复
        {
            for(int j=0; j<n; j++)
            {
                //循环保证行不重复,check保证列不重复
                if(str[i][j]=='.' || vis[j]==1)
                    continue;//不满足条件直接跳过
                vis[j] = 1;//标记
                dfs(i+1, k-1);//继续下一次标记
                vis[j] = 0;//恢复初始状态
            }
        }
    }
    
    int main(void)
    {
        while(1)
        {
            scanf("%d %d", &n, &k);
            getchar();
            if(n==-1 && k==-1) 
                break;
            memset(str, '\0', sizeof(str));
            memset(vis, 0, sizeof(vis));
            ans = 0;
    
            for(int i=0; i<n; i++)
            {
                for(int j=0; j<n; j++)
                    str[i][j] = getchar();
                getchar();
            }
    
            dfs(0, k);//从第0行开始放,此时手中还剩k个棋子
            printf("%d\n", ans);
        }
        return 0;
    }
    

    参考文章

    https://blog.csdn.net/ldx19980108/article/details/76324307#commentBox

    https://blog.csdn.net/qq_42815188/article/details/89258074

    https://www.jianshu.com/p/5cda08b4b391

    展开全文
  • BFS/DFS算法解析【算法入门]2018/6/21.前言和树的遍历类似,图的遍历也是从图中某点出发,...根据搜索路径的不同,我们可以将遍历图的方法分为两种:广度优先搜索和深度优先搜索。2.图的基本概念2.1.无向图和无向...

    BFS和DFS算法解析

    【算法入门】

    2018/6/2

    1.前言

    和树的遍历类似,图的遍历也是从图中某点出发,然后按照某种方法对图中所有顶点进行访问,且仅访问一次。

    但是图的遍历相对树而言要更为复杂。因为图中的任意顶点都可能与其他顶点相邻,所以在图的遍历中必须记录已被访问的顶点,避免重复访问。

    根据搜索路径的不同,我们可以将遍历图的方法分为两种:广度优先搜索和深度优先搜索。

    2.图的基本概念


    2.1.无向图和无向图

    顶点对(u,v)是无序的,即(u,v)和(v,u)是同一条边。常用一对圆括号表示。


    图2-1-1 无向图示例

    顶点对<u,v>是有序的,它是指从顶点u到顶点 v的一条有向边。其中u是有向边的始点,v是有向边的终点。常用一对尖括号表示。

    图2-1-2 有向图示例

    2.2.权和网

    图的每条边上可能存在具有某种含义的数值,称该数值为该边上的权。而这种带权的图被称为网。

    2.3.连通图与非连通图

    连通图:在无向图G中,从顶点v到顶点v'有路径,则称v和v'是联通的。若图中任意两顶点v、v'∈V,v和v'之间均联通,则称G是连通图。上述两图均为连通图。

    非连通图:若无向图G中,存在v和v'之间不连通,则称G是非连通图。


    图2-3 非连通图示例

    3.广度优先搜索


    3.1.算法的基本思路

    广度优先搜索类似于树的层次遍历过程。它需要借助一个队列来实现。如图2-1-1所示,要想遍历从v0到v6的每一个顶点,我们可以设v0为第一层,v1、v2、v3为第二层,v4、v5为第三层,v6为第四层,再逐个遍历每一层的每个顶点。

    具体过程如下:

      1.准备工作:创建一个visited数组,用来记录已被访问过的顶点;创建一个队列,用来存放每一层的顶点;初始化图G。

      2.从图中的v0开始访问,将的visited[v0]数组的值设置为true,同时将v0入队。

    3.只要队列不空,则重复如下操作:

        (1)队头顶点u出队。

        (2)依次检查u的所有邻接顶点w,若visited[w]的值为false,则访问w,并将visited[w]置为true,同时将w入队。

    3.2.算法的实现过程

    白色表示未被访问,灰色表示即将访问,黑色表示已访问。

    visited数组:0表示未访问,1表示以访问。

    队列:队头出元素,队尾进元素。

    1.初始时全部顶点均未被访问,visited数组初始化为0,队列中没有元素。



    图3-2-1

    2.即将访问顶点v0。


    图3-2-2


    3.访问顶点v0,并置visited[0]的值为1,同时将v0入队。


    图3-2-3

    4.将v0出队,访问v0的邻接点v2。判断visited[2],因为visited[2]的值为0,访问v2。


    图3-2-4

    5.将visited[2]置为1,并将v2入队。


    图3-2-5

    6.访问v0邻接点v1。判断visited[1],因为visited[1]的值为0,访问v1。


    图3-2-6

    7.将visited[1]置为0,并将v1入队。


    图3-2-7

    8.判断visited[3],因为它的值为0,访问v3。将visited[3]置为0,并将v3入队。


    图3-2-8

    9.v0的全部邻接点均已被访问完毕。将队头元素v2出队,开始访问v2的所有邻接点。

    开始访问v2邻接点v0,判断visited[0],因为其值为1,不进行访问。

    继续访问v2邻接点v4,判断visited[4],因为其值为0,访问v4,如下图:


    图3-2-9

    10.将visited[4]置为1,并将v4入队。


    图3-2-10

    11.v2的全部邻接点均已被访问完毕。将队头元素v1出队,开始访问v1的所有邻接点。

    开始访问v1邻接点v0,因为visited[0]值为1,不进行访问。

    继续访问v1邻接点v4,因为visited[4]的值为1,不进行访问。

    继续访问v1邻接点v5,因为visited[5]值为0,访问v5,如下图:


    图3-2-11

    12.将visited[5]置为1,并将v5入队。

    图3-2-12

    13.v1的全部邻接点均已被访问完毕,将队头元素v3出队,开始访问v3的所有邻接点。

    开始访问v3邻接点v0,因为visited[0]值为1,不进行访问。

    继续访问v3邻接点v5,因为visited[5]值为1,不进行访问。


    图3-2-13

    14.v3的全部邻接点均已被访问完毕,将队头元素v4出队,开始访问v4的所有邻接点。

    开始访问v4的邻接点v2,因为visited[2]的值为1,不进行访问。

    继续访问v4的邻接点v6,因为visited[6]的值为0,访问v6,如下图:


    图3-2-14

    15.将visited[6]值为1,并将v6入队。


    图3-2-15

    16.v4的全部邻接点均已被访问完毕,将队头元素v5出队,开始访问v5的所有邻接点。

    开始访问v5邻接点v3,因为visited[3]的值为1,不进行访问。

    继续访问v5邻接点v6,因为visited[6]的值为1,不进行访问。


    图3-2-16

    17.v5的全部邻接点均已被访问完毕,将队头元素v6出队,开始访问v6的所有邻接点。

    开始访问v6邻接点v4,因为visited[4]的值为1,不进行访问。

    继续访问v6邻接点v5,因为visited[5]的值文1,不进行访问。


    图3-2-17

    18.队列为空,退出循环,全部顶点均访问完毕。


    图3-2-18
    3.3具体代码的实现
    3.3.1用邻接矩阵表示图的广度优先搜索
    /*一些量的定义*/
    queue<char> q;				//定义一个队列,使用库函数queue
    #define MVNum 100			//表示最大顶点个数
    bool visited[MVNum];		        //定义一个visited数组,记录已被访问的顶点
    /*邻接矩阵存储表示*/
    typedef struct AMGraph
    {
    	char vexs[MVNum];            //顶点表
    	int arcs[MVNum][MVNum];      //邻接矩阵
    	int vexnum, arcnum;          //当前的顶点数和边数
    }AMGraph;
    /*找到顶点v的对应下标*/
    int LocateVex(AMGraph &G, char v)
    {
    	int i;
    	for (i = 0; i < G.vexnum; i++)
    		if (G.vexs[i] == v)
    			return i;
    }
    /*采用邻接矩阵表示法,创建无向图G*/
    int CreateUDG_1(AMGraph &G)
    {
    	int i, j, k;
    	char v1, v2;
    	scanf("%d%d", &G.vexnum, &G.arcnum);	                //输入总顶点数,总边数
    	getchar();				   	        //获取'\n’,防止其对之后的字符输入造成影响
    	for (i = 0; i < G.vexnum; i++)			
    		scanf("%c", &G.vexs[i]);			//依次输入点的信息
    	for (i = 0; i < G.vexnum; i++)
    		for (j = 0; j < G.vexnum; j++)
    			G.arcs[i][j] = 0;			//初始化邻接矩阵边,0表示顶点i和j之间无边
    	for (k = 0; k < G.arcnum; k++)
    	{
    		getchar();
    		scanf("%c%c", &v1, &v2);			//输入一条边依附的顶点
    		i = LocateVex(G, v1);				//找到顶点i的下标
    		j = LocateVex(G, v2);				//找到顶点j的下标
    		G.arcs[i][j] = G.arcs[j][i] = 1;	        //1表示顶点i和j之间有边,无向图不区分方向
    	}
    	return 1;
    }
    /*采用邻接矩阵表示图的广度优先遍历*/
    void BFS_AM(AMGraph &G,char v0)
    {
    /*从v0元素开始访问图*/
    
    	int u,i,v,w;
    	v = LocateVex(G,v0);                            //找到v0对应的下标
    	printf("%c ", v0);                              //打印v0
    	visited[v] = 1;		                        //顶点v0已被访问
    	q.push(v0);			                //将v0入队
    
    	while (!q.empty())
    	{
    		u = q.front();				//将队头元素u出队,开始访问u的所有邻接点
    		v = LocateVex(G, u);			//得到顶点u的对应下标
    		q.pop();				//将顶点u出队
    		for (i = 0; i < G.vexnum; i++)
    		{
    			w = G.vexs[i];
    			if (G.arcs[v][i] && !visited[i])//顶点u和w间有边,且顶点w未被访问
    			{
    				printf("%c ", w);	//打印顶点w
    				q.push(w);		//将顶点w入队
    				visited[i] = 1;		//顶点w已被访问
    			}
    		}
    	}
    }
    
    3.3.2用邻接表表示图的广度优先搜索
    /*找到顶点对应的下标*/
    int LocateVex(ALGraph &G, char v)
    {
    	int i;
    	for (i = 0; i < G.vexnum; i++)
    		if (v == G.vertices[i].data)
    			return i;
    }
    /*邻接表存储表示*/
    typedef struct ArcNode	        //边结点
    {
    	int adjvex;		//该边所指向的顶点的位置
    	ArcNode *nextarc;	//指向下一条边的指针
    	int info;		//和边相关的信息,如权值
    }ArcNode;
    
    typedef struct VexNode		//表头结点
    {
    	char data;				
    	ArcNode *firstarc;	//指向第一条依附该顶点的边的指针
    }VexNode,AdjList[MVNum];	//AbjList表示一个表头结点表
    
    typedef struct ALGraph
    {
    	AdjList vertices;
    	int vexnum, arcnum;
    }ALGraph;
    /*采用邻接表表示法,创建无向图G*/
    int CreateUDG_2(ALGraph &G)
    {
    	int i, j, k;
    	char v1, v2;
    	scanf("%d%d", &G.vexnum, &G.arcnum);	        //输入总顶点数,总边数
    	getchar();
    	for (i = 0; i < G.vexnum; i++)			//输入各顶点,构造表头结点表
    	{
    		scanf("%c", &G.vertices[i].data);	//输入顶点值
    		G.vertices[i].firstarc = NULL;		//初始化每个表头结点的指针域为NULL
    	}
    	for (k = 0; k < G.arcnum; k++)			//输入各边,构造邻接表
    	{
    		getchar();
    		scanf("%c%c", &v1, &v2);			//输入一条边依附的两个顶点
    		i = LocateVex(G, v1);				//找到顶点i的下标
    		j = LocateVex(G, v2);				//找到顶点j的下标
    		ArcNode *p1 = new ArcNode;			//创建一个边结点*p1
    		p1->adjvex = j;						//其邻接点域为j
    		p1->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p1; // 将新结点*p插入到顶点v1的边表头部
    		ArcNode *p2 = new ArcNode;			//生成另一个对称的新的表结点*p2
    		p2->adjvex = i;
    		p2->nextarc = G.vertices[j].firstarc;
    		G.vertices[j].firstarc = p1;
    	}
    	return 1;
    }
    /*采用邻接表表示图的广度优先遍历*/
    void BFS_AL(ALGraph &G, char v0)
    {
    	int u,w,v;
    	ArcNode *p;
    	printf("%c ", v0);		                                        //打印顶点v0
    	v = LocateVex(G, v0);	                                                //找到v0对应的下标
    	visited[v] = 1;			                                        //顶点v0已被访问
    	q.push(v0);				                                //将顶点v0入队
    	while (!q.empty())
    	{
    		u = q.front();		                                        //将顶点元素u出队,开始访问u的所有邻接点
    		v = LocateVex(G, u);                                            //得到顶点u的对应下标
    		q.pop();			//将顶点u出队
    		for (p = G.vertices[v].firstarc; p; p = p->nextarc)		//遍历顶点u的邻接点
    		{
    			w = p->adjvex;	
    			if (!visited[w])	//顶点p未被访问
    			{
    				printf("%c ", G.vertices[w].data);	        //打印顶点p
    				visited[w] = 1;				        //顶点p已被访问
    				q.push(G.vertices[w].data);			//将顶点p入队
    			}
    		}
    	}
    }
    3.4.非联通图的广度优先遍历的实现方法
    /*广度优先搜索非连通图*/
    void BFSTraverse(AMGraph G)
    {
    	int v;
    	for (v = 0; v < G.vexnum; v++)
    		visited[v] = 0;							//将visited数组初始化
    	for (v = 0; v < G.vexnum; v++)
    		if (!visited[v]) BFS_AM(G, G.vexs[v]);	                        //对尚未访问的顶点调用BFS
    }


    4.深度优先搜索


    4.1算法的基本思路

    深度优先搜索类似于树的先序遍历,具体过程如下:


    准备工作:创建一个visited数组,用于记录所有被访问过的顶点。


    1.从图中v0出发,访问v0。

    2.找出v0的第一个未被访问的邻接点,访问该顶点。以该顶点为新顶点,重复此步骤,直至刚访问过的顶点没有未被访问的邻接点为止。

    3.返回前一个访问过的仍有未被访问邻接点的顶点,继续访问该顶点的下一个未被访问领接点。

    4.重复2,3步骤,直至所有顶点均被访问,搜索结束。


    4.2算法的实现过程

    1.初始时所有顶点均未被访问,visited数组为空。




    图4-2-1

    2.即将访问v0。


    图4-2-2

    3.访问v0,并将visited[0]的值置为1。


    图4-2-3

    4.访问v0的邻接点v2,判断visited[2],因其值为0,访问v2。


    图4-2-4

    5.将visited[2]置为1。


    图4-2-5

    6.访问v2的邻接点v0,判断visited[0],其值为1,不访问。

    继续访问v2的邻接点v4,判断visited[4],其值为0,访问v4。


    图4-2-6

    7.将visited[4]置为1。


    图4-2-7

    8.访问v4的邻接点v1,判断visited[1],其值为0,访问v1。



    图4-2-8

    9.将visited[1]置为1。


    图4-2-9

    10.访问v1的邻接点v0,判断visited[0],其值为1,不访问。

    继续访问v1的邻接点v4,判断visited[4],其值为1,不访问。

    继续访问v1的邻接点v5,判读visited[5],其值为0,访问v5。


    图4-2-10

    11.将visited[5]置为1。


    图4-2-11

    12.访问v5的邻接点v1,判断visited[1],其值为1,不访问。

    继续访问v5的邻接点v3,判断visited[3],其值为0,访问v3。


    图4-2-12

    13.将visited[1]置为1。


    图4-2-13

    14.访问v3的邻接点v0,判断visited[0],其值为1,不访问。

    继续访问v3的邻接点v5,判断visited[5],其值为1,不访问。

    v3所有邻接点均已被访问,回溯到其上一个顶点v5,遍历v5所有邻接点。

    访问v5的邻接点v6,判断visited[6],其值为0,访问v6。


    图4-2-14

    15.将visited[6]置为1。


    图4-2-15

    16.访问v6的邻接点v4,判断visited[4],其值为1,不访问。

    访问v6的邻接点v5,判断visited[5],其值为1,不访问。

    v6所有邻接点均已被访问,回溯到其上一个顶点v5,遍历v5剩余邻接点。


    图4-2-16

    17.v5所有邻接点均已被访问,回溯到其上一个顶点v1。

    v1所有邻接点均已被访问,回溯到其上一个顶点v4,遍历v4剩余邻接点v6。

    v4所有邻接点均已被访问,回溯到其上一个顶点v2。

    v2所有邻接点均已被访问,回溯到其上一个顶点v1,遍历v1剩余邻接点v3。

    v1所有邻接点均已被访问,搜索结束。


    图4-2-17

    4.3具体代码实现

    4.3.1用邻接矩阵表示图的深度优先搜索

    邻接矩阵的创建在上述已描述过,这里不再赘述

    void DFS_AM(AMGraph &G, int v)
    {
    	int w;
    	printf("%c ", G.vexs[v]);
    	visited[v] = 1;
    	for (w = 0; w < G.vexnum; w++)
    		if (G.arcs[v][w]&&!visited[w]) //递归调用
    			DFS_AM(G,w);
    }
    4.3.2用邻接表表示图的深度优先搜素

    邻接表的创建在上述已描述过,这里不再赘述。

    void DFS_AL(ALGraph &G, int v)
    {
    	int w;
    	printf("%c ", G.vertices[v].data);
    	visited[v] = 1;
    	ArcNode *p = new ArcNode;
    	p = G.vertices[v].firstarc;
    	while (p)
    	{
    		w = p->adjvex;
    		if (!visited[w]) DFS_AL(G, w);
    		p = p->nextarc;
    	}
    }


    展开全文
  • 深度优先搜索Or深度优先遍历详解

    万次阅读 多人点赞 2018-08-13 17:53:44
    深度优先搜索(DFS, Depth First Search)是一个针对图和树的遍历算法。早在19世纪就被用于解决迷宫问题。 对于下面的树而言,DFS方法首先从根节点1开始,其搜索节点顺序是1,2,3,4,5,6,7,8(假定左分枝和右分枝中优先...

    学习过程中发现这篇文章写得特别好,立转

     

    深度优先搜索(DFS, Depth First Search)是一个针对图和树的遍历算法。早在19世纪就被用于解决迷宫问题。

    对于下面的树而言,DFS方法首先从根节点1开始,其搜索节点顺序是1,2,3,4,5,6,7,8(假定左分枝和右分枝中优先选择左分枝)。 
    这里写图片描述
    DFS的实现方式相比于BFS应该说大同小异,只是把queue换成了stack而已,stack具有后进先出LIFO(Last Input First Output)的特性,DFS的操作步骤如下: 
    1、把起始点放入stack; 
    2、重复下述3步骤,直到stack为空为止:

    • 从stack中访问栈顶的点;
    • 找出与此点邻接的且尚未遍历的点,进行标记,然后全部放入stack中;
    • 如果此点没有尚未遍历的邻接点,则将此点从stack中弹出。

    下面结合一个图(graph)的实例,说明DFS的工作过程和原理: 
    (1)将起始节点1放入栈stack中,标记为已遍历。 
    这里写图片描述
    (2)从stack中访问栈顶的节点1,找出与节点1邻接的节点,有2,9两个节点,我们可以选择其中任何一个,选择规则可以人为设定,这里假设按照节点数字顺序由小到大选择,选中的是2,标记为已遍历,然后放入stack中。 
    这里写图片描述
    (3)从stack中取出栈顶的节点2,找出与节点2邻接的节点,有1,3,5三个节点,节点1已遍历过,排除;3,5中按照预定的规则选中的是3,标记为已遍历,然后放入stack中。 
    这里写图片描述
    (4)从stack中取出栈顶的节点3,找出与节点3邻接的节点,有2,4两个节点,节点2已遍历过,排除;选中的是节点4,标记为已遍历,然后放入stack中。 
    这里写图片描述
    (5)从stack中取出栈顶的节点4,找出与节点4邻接的节点,有3,5,6三个节点,节点3已遍历过,排除;选中的是节点5,标记为已遍历,然后放入stack中。 
    这里写图片描述
    (6)从stack中取出栈顶的节点5,找出与节点5邻接的节点,有2,4两个节点,节点2,4都已遍历过,因此节点5没有尚未遍历的邻接点,则将此点从stack中弹出。 
    这里写图片描述
    (7)当前stack栈顶的节点是4,找出与节点4邻接的节点,有3,5,6三个节点,节点3,5都已遍历过,排除;选中的是节点6,标记为已遍历,然后放入stack中。 
    这里写图片描述
    (8)当前stack栈顶的节点是6,找出与节点6邻接的节点,有4,7,8三个节点,4已遍历,按照规则选中的是7,标记为已遍历,然后放入stack中。 
    这里写图片描述
    (9)当前stack栈顶的节点是7,找出与节点7邻接的节点,只有节点6,已遍历过,因此没有尚未遍历的邻接点,将节点7从stack中弹出。 
    这里写图片描述
    (10)当前stack栈顶的节点是6,找出与节点6邻接的节点,有节点7,8,7已遍历过,因此将节点8放入stack中。 
    这里写图片描述
    (11)当前stack栈顶的节点是8,找出与节点8邻接的节点,有节点1,6,9,1,6已遍历过,因此将节点9放入stack中。 
    这里写图片描述
    (12)当前stack栈顶的节点是9,没有尚未遍历的邻接点,将节点9弹出,依次类推,栈中剩余节点8,6,4,3,2,1都没有尚未遍历的邻接点,都将弹出,最后栈为空。 
    (13)DFS遍历完成。

    展开全文
  • 广度优先搜索与深度优先搜索

    千次阅读 2018-11-04 17:39:25
    广度优先搜索(宽度优先搜索,BFS)和深度优先搜索(DFS)算法的应用非常广泛,本篇文章主要介绍BFS与DFS的原理、实现和应用。 深度优先搜索 图的深度优先搜索(Depth First Search),和树的先序遍历比较类似。 它的...
  • dfs深度优先搜索Depth First Search (DFS) is an algorithm that searches a graph/tree, in a depth-wise manner. 深度优先搜索 ( DFS )是一种以深度方式搜索图/树的算法。 There are many ways through which ...
  • 一)深度优先搜索的特点是: (1)无论问题的内容和性质以及求解要求如何不同,它们的程序结构都是相同的,即都是深度优先算法(一)和深度优先算法(二)中描述的算法结构,不相同的仅仅是存储结点数据结构和...
  • 深度优先搜索 简称:DFS 基本思路 深度优先遍历图的方法是,从图中某顶点v出发: (1)访问顶点v; (2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;...
  • 深度优先搜索的图文介绍 1. 深度优先搜索介绍 图的深度优先搜索(Depth First Search),和树的先序遍历比较类似。 它的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从...
  • 为了解决路径生成问题,比较了深度优先搜索,广度优先搜索,爬山搜索和束搜索的优劣
  • 宽度优先搜索和深度优先搜索

    千次阅读 2020-09-12 18:53:58
    Maze试验台的设计与实现(宽度优先搜索和深度优先搜索的理解) 一、 宽度优先搜索 BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整...
  • 本周学习了一下图的搜索算法,包括无信息搜索算法:深度优先搜索、迭代加深的深度优先搜索、广度优先搜索以及代价一致搜索;有信息搜索算法:A*搜索。 一、需求分析 分别用深度优先搜索、迭代加深的深度优先搜索、...
  • 邻接表 邻接矩阵 广度优先搜索 深度优先搜索
  • 探索广度优先搜索和深度优先搜索,队列和栈讲解
  • “生动”讲解——深度优先搜索与广度优先搜索

    万次阅读 多人点赞 2015-04-21 00:25:44
    通过GIF图“生动”介绍深度优先搜索与广度优先搜索
  • 深度优先搜索(DFS)与广度优先搜索(BFS)详解

    千次阅读 多人点赞 2020-11-07 18:44:06
    深度优先搜索与宽度优先搜索详解 深度优先搜索(DFS)和宽度优先搜索(BFS)都是常见的搜索算法。在学习DFS和BFS之前,我们首先得知道递归函数的概念。 1. 递归函数 通俗地讲,一个函数自己调用自己的行为就叫递归,...
  • 图的遍历(深度优先搜索

    万次阅读 多人点赞 2017-10-19 16:52:01
    1、深度优先搜索遍历过程 图的深度优先搜索(Depth First Search),和树的先序遍历比较类似。 它的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的...
  • 深度优先搜索&&广度优先搜索

    千次阅读 2018-05-30 22:41:38
    深度优先搜索dfs:   深度优先搜索算法(Depth First Search),是图论中的经典算法。   深度优先搜索的核心是栈   为了实现深度优先搜索,首先选择一个起始顶点并需要遵守三个规则: 非递归的情况: 1. ...
  • 深度优先搜索(1)

    千次阅读 2019-01-19 17:18:38
    深度优先搜索(1) 深度优先搜索概念: 深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。 讲通俗一点,深度优先搜索其实像在走迷宫,遇到一个岔路口,先选则一条路,当发现这条路是死路时,又返回岔路口选择第...
  • 对于二叉树有两种搜索方式:深度优先搜索与广度优先搜索,而深度优先搜索分为前序,中序,后序三种遍历方式,下面给几种遍历方式一 一解释。 深度优先搜索: 前序遍历,访问节点顺序:根节点--->左子节点--->...
  • 图的深度优先搜索

    千次阅读 2016-12-07 17:50:49
    深度优先搜索(Depth First Search)遍历类似于树的先序遍历,是树的先序遍历的推广。 无向图的深度优先搜索算法的过程如下: 首先访问出发顶点v,然后选择一个与v相邻接且未被访问过的顶点w访问之,再从w出发...
  • 深度优先搜索算法

    万次阅读 多人点赞 2018-05-07 17:23:07
    深度优先搜索算法的概念: 深度优先搜索属于图算法的一种,英文缩写为DFS(Depth First Search.)其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。如下例: 该图为一个...
  • 深度优先搜索的图文介绍 1. 深度优先搜索介绍 图的深度优先搜索(Depth First Search),和树的先序遍历比较类似。 它的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 88,676
精华内容 35,470
关键字:

深度优先搜索