精华内容
下载资源
问答
  • 先摘抄一段概述的话:  搜索一个图是有序地...另外还有一些图的算法实际上是由基本的图搜索算法经过简单扩充而成。因此,图的搜索技术是图算法领域的核心。 BFS:  是Prim最小生成树和Dijkstra单源最短路的原型。

    先摘抄一段概述的话:

            搜索一个图是有序地沿着图的边访问所有顶点。图的搜索算法可以使我们发现图的很多结构信息。许多图的算法在开始时,都是通过搜索输入的图来获取结构信息。另外还有一些图的算法实际上是由基本的图搜索算法经过简单扩充而成。因此,图的搜索技术是图算法领域的核心。


    BFS:

            是Prim最小生成树和Dijkstra单源最短路的原型。

            用三种颜色表示顶点:白色(未访问),灰色(已访问但子节点或许有未访问的白节点),黑色(已访问并子节点也已访问)。以此确保节点只被访问一次。

            用一个队列控制访问顺序。


    代码模版:

    BFS(G,s)

    //初始化
    for each u from V[G]-{s}
      do color[u] <- WHITE
           d[u] <- infinity
           pre[u] <- NIL
    color[s] <- GRAY
    d[s] <- 0
    pre[s] <- NIL
    Q <- empty
    //开始bfs
    ENQUEUE(Q,s)
    while Q != empty
      do u <- DEQUEUE(Q)
        for each v from Adj[u]
          do if color[v] == WHITE
               then color[v] <- GRAY
                       d[v] <- d[u] + 1
                       pre[v] <- u
                       ENQUEUE(Q,v)
          color[u] <- BLACK

            其中d[]给出了最短路径长度,pre[]给出路径,也可以pre[]构建出广度优先树(最短路径树),则此时d[]就代表了深度。
            显然,这代码本身并没有对图顶点遍历,它只能遍历s所在的连通分量。如果实在要遍历,可以参照下面的DFS,在外层加一个循环,对白色节点进行BFS(G,s)操作,可以生成森林。但是从常见的用法而言,基本不这么做。通常我们只是以此找最短路。




    DFS:
            一般来讲,遍历就用的DFS,也是我们常说的“回溯法”,通常DFS被用在另一个算法中的子程序,比如做一个拓扑排序(按节点完成遍历的时间的倒序放入,或者记录入度,在遍历的时候依次放入入度为0的节点),是要求遍历的。所以在代码中我们的版本为遍历。同样是三种颜色,可以用递归,也可以栈控制访问顺序(毕竟递归也是依靠栈实现的,而我们使用栈存节点可以使得程序开销更小)。

            同时,用两次DFS可以分解强连通分支(很多有向图的算法都是在分解强连通分支之后,再用分治分别处理各个分支)。第一次DFS做拓扑排序,第二次DFS按拓扑排序的顺序,分解出的深度优先树则为强连通分支。


    代码模板:
    DFS(G)

    //初始化
    for each u from V[G]
      do color[u] <- WHITE
         pre[u] <- NIL
    time <- 0
    //遍历
    for each u from V[G]
      do if color[u] == WHITE
        then DFS_VISIT(u)

    //递归版
    DFS_VISIT(u):
    
    color[u] <- GRAY
    time <- time + 1
    d[u] <- time
    for each v from Adj[u]
      do if color[v] == WHITE
            then pre[v] <- u
                 DFS_VISIT(v)
    color[u] <- BLACK
    time <- time + 1
    f[u] <- time

    DFS_VISIT(u):
    //栈版
    S <- empty
    
    color[u] <- GRAY
    time <- time + 1
    d[u] <- time
    ENSTACK(S,u)
    
    while S != empty
       for each v from Adj[u]
          do if color[v] == WHITE 
               then color[v] <- GRAY
                    pre[v] <- u
                    time <- time + 1
                    d[v] <- time
                    ENSTACK(S,v)
                    u <- TOPSTACK(S)
       time <- time + 1
       f[u] <- time
       color[u] <- BLACK
       DESTACK(S,u)    

            这里我们加上了时间戳,分别为开始访问时间d[],结束访问时间(访问了所有子节点)f[],即为变灰时间和变黑时间,在栈版中还对应入栈时间和出栈时间。时间戳可以用于一些后续的应用,比如判断节点v是否为u的后裔(v为u的后裔当且仅当d[u]<d[v]<f[v]<f[u])。当然,在栈版中,只需要两种颜色,白和非白,即是否访问,而是对于访问了的节点否在栈中则天然地说明了它是否访问完毕。

            在DFS过程中可以同时将边分类,以用于以后的算法(如无回路就是无反向边)。首先我们给出四类边的定义:
    1. 树边(tree edge),是深度优先森林中的边。
    2. 反向边(back edge),是树中,连接v到祖先u的边。
    3. 正向边(forward edge),是连接u到后裔v的非树边。
    4. 交叉边(cross edge),其他类型的边,即连接两个非祖先后裔关系的点的边。
           分类方法:根据该边被第一次探寻到时,所到达顶点的v的颜色
    1. 白色表明树边
    2. 灰色表面反向边
    3. 黑色表面正向边或交叉边

           同时,DFS中无向图只有树边和反向边。

    展开全文
  • 0.1) 本文总结于 数据结构与算法分析, 源代码均为原创, 旨在 理解 “DFS应用——查找强分支” 的idea 并用源代码加以实现 ; 【1】查找强分支 1.1)如何检测一个图是否是强连通的: 通过执行两次DFS, 我们可以...

    【0】README

    0.1) 本文总结于 数据结构与算法分析, 源代码均为原创, 旨在 理解 “DFS应用——查找强分支” 的idea 并用源代码加以实现 ;


    【1】查找强分支

    1.1)如何检测一个图是否是强连通的: 通过执行两次DFS, 我们可以检测一个有向图是否是强连通的, 如果它不是强连通的,那么我们实际上可以得到顶点的一个子集, 它们到其自身是强连通的;
    1.2)首先, 在输入的图G上执行一次 DFS。 通过对深度优先生成森林的后序遍历将G的顶点编号, 然后再把G 的所有边反向,形成 Gr(如何构建 Gr)
    20151124154606528
    1.3)上述算法通过对 Gr 执行一次深度优先搜索而完成, 总是在编号最高的顶点开始一次新的DFS。于是,我们在顶点G 开始对 Gr 的DFS, G的编号为10。
    1.4)但该顶点不通向任何顶点, 因此下一次搜索在H 点开始(以下查找强分支的过程仅仅是一个可能的case,仅举例而已)。 这次调用访问 I 和 J。 下一次调用在B点开始并访问 A、C 和 F。 此后的调用时 DFS(D)以及最终调用DFS(E)。
    20151124154639366
    1.5)结果得到的深度优先生成森林如下图所示:
    这里写图片描述
    1.6)对深度优先生成森林中的分析:
    在该深度优先生成森林中的每棵树形成一个强连通分支。 对于我们的例子, 这些强连通分支为 {G}, {H,I,J}, {B,A,C,F},{D} 和 {E};
    1.7)为了理解上述算法为什么成立?

    • 1.7.1)首先,注意到, 如果两个顶点v 和 w 都在同一个强连通分支中,那么在原图G中就存在从 v到w 和从w到v的路径,因此, 在Gr中也存在。
    • 1.7.2)现在,如果两个顶点v 和 w 不在Gr的同一个深度优先生成树中,那么显然它们也不可能在同一个强连通分支中;

    【2】source code + printing results

    2.1)download source code: https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter9/p249_dfs_strong_component
    2.2)source code at a glance:(for complete code , please click the given link above)

    // finding the strong component from the reverse graph and strongComponent derives from dfs
    void strongComponent(Vertex vertex, int depth)
    {
        int i;
        AdjTable temp;
        Vertex adjVertex;   
        
        //printf("\n\t visited[%c] = 1 ", flag[vertex]);
        visited[vertex] = 1; // update visited status of vertex
        vertexIndex[vertex] = counter++; // number the vertex with counter
        temp = reverseAdj[vertex];  
            
        while(temp->next)
        {
            printf("   ");
            adjVertex = temp->next->vertex;     
            if(visited[adjVertex]) // judge whether the adjVertes was visited before        
            {
                if(vertexIndex[vertex] > vertexIndex[adjVertex] && parent[vertex] != adjVertex)     
                {
                    parent[adjVertex] = vertex; // building back side, attention of condition of building back side above
                    
                    // just for printing effect
                    for(i = 0; i < depth; i++)  
                        printf("      ");
                    printf("v[%c]->v[%c] (backside) \n", flag[vertex], flag[adjVertex]);
                }
            }
            
            else
            {
                parent[adjVertex] = vertex;
                
                // just for printing effect
                for(i = 0; i < depth; i++)  
                    printf("      ");
                printf("v[%c]->v[%c] (building edge)\n", flag[vertex], flag[adjVertex]);            
                strongComponent(adjVertex, depth+1);
            }       
            temp = temp->next;      
        }   
    }

    2.3)printing results:
    这里写图片描述
    这里写图片描述

    转载于:https://www.cnblogs.com/pacoson/p/4992619.html

    展开全文
  • DFS算法由来: 发明深度优先算法的是John E.Hopcroft 和 Robert E.Tarjan。1971~1972年,他们在斯坦福大学研究图的连通性(任意两点是否可以相互到达)和平面性(图中所有的边相互不交叉。在电路板上设计布线的时候...

    DFS算法由来:

    发明深度优先算法的是John E.Hopcroft 和 Robert E.Tarjan。1971~1972年,他们在斯坦福大学研究图的连通性(任意两点是否可以相互到达)和平面性(图中所有的边相互不交叉。在电路板上设计布线的时候,要求线与线不能交叉,这就是平面性的一个实际应用),发明了这个算法。他们也因此获得了1986年的图灵奖。

    实例1:迷宫搜救

    问题描述:A处于迷宫的入口处(1,1),B在(p,q)。找从(1,1)到(p,q)的最短路径(步长),如图:

    输入描述:

    整数n m:分别代表迷宫的行和列;

    a[n][m]:用1表示有障碍,0表示无障碍;

    start end p q:分别代表起始坐标和终点坐标;

    输出描述:

    整数step 最短步长

    例如:

    输入:

    3 3

    0 0 0

    0 1 0

    0 0 0

    1 1 2 3

    输出:

    3

    代码(c/c++):

    #include<stdio.h>
    int n,m,p,q,min=99999999;
    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<=3;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;
        scanf("%d %d",&n,&m);  //读入n和m,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;  //标记起点已经在路径中,防止后面重复走
        dfs(startx,starty,0);  //第一个参数是起点的x坐标,以此类推是起点的y坐标,初始步数为0
        printf("%d",min);  //输出最短步数
        return 0; 
    }

    测试:

     实例2:单位分数(题目来自蓝桥杯)

    题目描述:

    可以把1分解为若干个互不相同的单位分数之和。

    例如:
    1 = 1/2 + 1/3 + 1/9 + 1/18
    1 = 1/2 + 1/3 + 1/10 + 1/15
    1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/35 + 1/45 + 1/231
    等等,类似这样的分解无穷无尽。
    我们增加一个约束条件:最大的分母必须不超过30(说明:这个应该是包含30,但是下面举例的时候又没包含30)
    请你求出分解为n项时的所有不同分解法。
    数据格式要求:
     
    例如,
    输入:
    4
    程序应该输出:
    1/2 1/3 1/8 1/24
    1/2 1/3 1/9 1/18
    1/2 1/3 1/10 1/15
    1/2 1/4 1/5 1/20
    1/2 1/4 1/6 1/12
    再例如,
    输入:
    5
    程序应该输出:
    1/2 1/3 1/12 1/21 1/28
    1/2 1/4 1/6 1/21 1/28
    1/2 1/4 1/7 1/14 1/28
    1/2 1/4 1/8 1/12 1/24
    1/2 1/4 1/9 1/12 1/18
    1/2 1/4 1/10 1/12 1/15
    1/2 1/5 1/6 1/12 1/20
    1/3 1/4 1/5 1/6 1/20


    代码:

    #include <iostream>
    #include <cmath>
    using namespace std;
     
    int n,ans[15];
    const double eps=1e-9;
    //深度优先算法  记住(背) 
    void dfs(double sum,int cnt,double now)
    {
        if(cnt==n){
            if(abs(sum-1)<eps){
                for(int i=0;i<n;i++)
                    cout<<1<<'/'<<ans[i]<<' ';
                cout<<endl;
            }
            return ;
        }
        if(sum>=1||cnt>n||now>30)
            return ;
        dfs(sum,cnt,now+1);
        ans[cnt]=now;
        dfs(sum+1/now,cnt+1,now+1);
        return ;
    }
     
    int main()
    {
        cin>>n;
        dfs(0,0,1);
        return 0;
    }
    

    测试:

     实例3:方块分割(题目来自蓝桥杯) 

    题目描述:

    6x6的方格,沿着格子的边线剪开成两部分。

    要求这两部分的形状完全相同。

    如图:就是可行的分割法。

    试计算:

    包括这3种分法在内,一共有多少种不同的分割方法。

    注意:旋转对称的属于同一种分割法。

    请提交该整数,不要填写任何多余的内容或说明文字。

    思路:

    仔细思考,你会发现其实一道dfs的题目,建立坐标系,从坐标(3,3)移动,每移动一点,对称坐标锁住。

     代码:

    #include<cstdio>
    #include <cstdlib>
    #include <iostream>
    #include <queue>
    #include <map>
    #include <algorithm>
    using namespace std;
    
    
    bool book[23][23] = {};
    int cnt = 0;
    int nextx[4] = {-1, 0, 1, 0};
    int nexty[4] = {0, -1, 0, 1};
    void dfs(int stx, int sty)
    {
        if(stx == 0 || stx == 6 || sty == 0 || sty == 6)
        {
            cnt++;
            return;
        }
        for(int i = 0; i < 4; i++)
        {
            int xx = stx + nextx[i];
            int yy = sty + nexty[i];
            if(!book[xx][yy])
            {
                book[xx][yy] = true;            //锁 
                book[6 - xx][6 - yy] = true;    //锁 
                dfs(xx, yy);
                book[xx][yy] = false;         //取消锁      
                book[6 - xx][6 - yy] = false; //取消锁  
            }
        }
    }
    int main()
    {
        book[3][3] = true;
        dfs(3, 3);
        cout << cnt / 4 << endl;      //考虑旋转 
        return 0;
    
    }

    测试:

    展开全文
  • 搜索就是用问题的所有可能去试探,按照一定的顺序、规则,不断去试探,直到找到问题的解,试完了也没有找到解,那就是无解,试探时一定要试探完所有的情况(实际上就是穷举)。 对于问题的第一个状态,叫初始状态,...

    在我们遇到的一些问题当中,有些问题我们不能够确切的找出数学模型,即找不出一种直接求解的方法,解决这一类问题,我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探,按照一定的顺序、规则,不断去试探,直到找到问题的解,试完了也没有找到解,那就是无解,试探时一定要试探完所有的情况(实际上就是穷举)。

    对于问题的第一个状态,叫初始状态,要求的状态叫目标状态。
    搜索就是把规则应用于实始状态,在其产生的状态中,直到得到一个目标状态为止。

    感谢杭电刘老师的ppt

    什么是深度优先搜索

    所有的搜索算法从其最终的算法实现上来看,都可以划分成两个部分──控制结构和产生系统。正如前面所说的,搜索算法简而言之就是穷举所有可能情况并找到合适的答案,所以最基本的问题就是罗列出所有可能的情况,这其实就是一种产生式系统。

    从根开始计算,到找到位于某个节点的解,回溯法(深度优先搜索)作为最基本的搜索算法,其采用了一种“一只向下走,走不通就掉头”的思想(体会“回溯”二字),相当于采用了先根遍历的方法来构造搜索树。

    借用刘老师的话

    基本思想:从初始状态S开始,利用规则生成搜索树下一层任一个结点,检查是否出现目标状态G,若未出现,以此状态利用规则生成再下一层任一个结点,再检查是否为目标节点G,若未出现,继续以上操作过程,一直进行到叶节点(即不能再生成新状态节点),当它仍不是目标状态G时,回溯到上一层结果,取另一可能扩展搜索的分支。生成新状态节点。若仍不是目标状态,就按该分支一直扩展到叶节点,若仍不是目标,采用相同的回溯办法回退到上层节点,扩展可能的分支生成新状态,…,一直进行下去,直到找到目标状态G为止。

    DFS算法

    • 把起始节点S线放到OPEN表中。
    • 如果OPEN是空表,则失败退出,否则继续。
    • 从OPEN表中取最前面的节点node移到CLOSED 表中。
    • 若node节点是叶结点(若没有后继节点),则转向(2)。
    • 扩展node的后继节点,产生全部后继节点,并把他们放在OPEN表的前面。各后继结点指针指向node节点。
    • 若后继节点中某一个是目标节点,则找到一个解,成功退出。否则转向(2)循环。

    DFS最重要的就是回溯,它的本质是递归!

    我认为实质就是暴力枚举多种可能。

    减枝

    对于深度优先搜索来说减枝也是极为重要的。如果遍历了一些无关紧要的节点的话就会很浪费时间,如果数据小的话还看不出。一旦数据大,减枝所带来的优化将变得极为重要。

    HDU-1010-Tempter of the Bone为例

    题目

    小狗在一个古老的迷宫中发现了一根骨头,这使他非常着迷。但是,当他捡起它时,迷宫开始摇晃,小狗可以感觉到地面下沉。他意识到骨头是一个陷阱,他拼命试图摆脱这个迷宫。

    迷宫是一个矩形,大小为N×M。迷宫中有一扇门。刚开始时,门是关闭的,它将在第T秒打开一小段时间(少于1秒)。因此,小狗必须在第T秒精确到达门。每秒钟,他可以将一个块移动到上,下,左和右相邻的块之一。一旦他进入一个街区,该街区的地面将开始下沉并在下一秒消失。他不能在一个街区停留超过一秒钟,也不能搬到一个拜访的街区。可怜的小狗可以生存吗?请帮助他。

    输入

    输入包含多个测试用例。每个测试用例的第一行包含三个整数N,M和T(1<N,M<7;0<T<50),分别表示迷宫的大小和门打开的时间。接下来的N行给出迷宫布局,每行包含M个字符。角色是以下字符之一:

    ‘X’:小狗无法进入的墙块;
    ‘S’:小狗的起点;
    ‘D’:门;或
    “.”:空白块。

    输入以三个0终止。该测试用例将不被处理。

    输出

    对于每个测试用例,如果小狗可以存活,则在一行中打印“YES”,否则打印“NO”。

    样例输入

    4 4 5
    S.X.
    …X.
    …XD

    3 4 5
    S.X.
    …X.
    …D
    0 0 0

    样例输出

    NO
    YES

    典型的迷宫式搜索,每一步都只能走一次,并且只有时间刚刚好时,才能成功!

    深搜代码(DFS)

    无减枝版本

    #include<bits/stdc++.h>
    using namespace std;
    char Map[15][15];
    int n,m,t,qx,qy,zx,zy;
    int flag;
    int dir[4][2]={-1,0,0,-1,1,0,0,1};//上下左右四个方向 
    void dfs(int x,int y,int cnt){      //搜索
    	if(x==zx&&y==zy&&cnt==t){   //如果位置和出口一样并且时间一样则为成功
    		flag=1;
    	}
    	if(flag){               //只要有一次成功则直接return
    		return;
    	}   
    	if(cnt>t){              //如果时间超出限制
    		return;
    	}
    	for(int i=0;i<4;i++){       //四个方向寻求可以走的地方
    		int xx=x+dir[i][0];
    		int yy=y+dir[i][1];
    		if(xx<0||yy<0||xx>n-1||yy>m-1){     //如果超出地图
    			continue;
    		}
    		else if(Map[xx][yy]!='X'){      //如果可以走
    			Map[xx][yy]='X';            //标记为下次不能走
    			dfs(xx,yy,cnt+1);       //进入搜索
    			Map[xx][yy]='.';        //取消标记
    		}
    	}
    }
    int main(){
    	while(scanf("%d %d %d",&n,&m,&t)!=EOF&&(n||m||t)){
    		for(int i=0;i<n;i++){
    			scanf("%s",Map[i]);
    			for(int j=0;j<m;j++){
    				if(Map[i][j]=='S'){
    					qx=i;
    					qy=j;
    				}
    				if(Map[i][j]=='D'){
    					zx=i;
    					zy=j;
    				}
    			}
    		}
    		flag=0;
    		Map[qx][qy]='X';    //将起点标记为不能走
    		dfs(qx,qy,0);       /进入搜索
    		if(flag){
    			printf("YES\n");
    		}
    		else{
    			printf("NO\n"); 
    		}
    	}
    	return 0;
    }
    

    如果没有减枝也能搜索出来,但是会超时,因为浪费了很多不必要的时间

    广度和深度优先搜索有一个很大的缺陷,就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法,可是当状态空间十分大,且不预测的情况下就不可取了。他的效率实在太低,甚至不可完成。

    所以,在这里再次强调“剪枝”!

    减枝

    可以把map看成这样:

    • 0 1 0 1 0 1
    • 1 0 1 0 1 0
    • 0 1 0 1 0 1
    • 1 0 1 0 1 0
    • 0 1 0 1 0 1

    从为 0 的格子走一步,必然走向为 1 的格子
    从为 1 的格子走一步,必然走向为 0 的格子
    即:

    0->1或1->0 必然是奇数步
    0->0 走1->1 必然是偶数步

    所以当遇到从 0 走向 0 但是要求时间是奇数的,或者, 从 1 走向 0 但是要求时间是偶数的 都可以直接判断不可达!

    则我们可以,判断他终点和起点是否一致。来进行减枝,减去一些不必要浪费的时间

    伪代码

    int sum=t-abs(zx-qx)-abs(zy-qy);
    if(sum>=0&&sum%2==0){
    	dfs(qx,qy,0);
    }
    

    完整代码

    #include<bits/stdc++.h>
    using namespace std;
    char Map[15][15];
    int n,m,t,qx,qy,zx,zy;
    int flag;
    int dir[4][2]={-1,0,0,-1,1,0,0,1};//上下左右四个方向 
    void dfs(int x,int y,int cnt){
    	if(x==zx&&y==zy&&cnt==t){
    		flag=1;
    	}
    	if(flag){
    		return;
    	}
    	if(cnt>t){
    		return;
    	}
    	for(int i=0;i<4;i++){
    		int xx=x+dir[i][0];
    		int yy=y+dir[i][1];
    		if(xx<0||yy<0||xx>n-1||yy>m-1){
    			continue;
    		}
    		else if(Map[xx][yy]!='X'){
    			Map[xx][yy]='X';
    			dfs(xx,yy,cnt+1);
    			Map[xx][yy]='.';
    		}
    	}
    }
    int main(){
    	while(scanf("%d %d %d",&n,&m,&t)!=EOF&&(n||m||t)){
    		for(int i=0;i<n;i++){
    			scanf("%s",Map[i]);
    			for(int j=0;j<m;j++){
    				if(Map[i][j]=='S'){
    					qx=i;
    					qy=j;
    				}
    				if(Map[i][j]=='D'){
    					zx=i;
    					zy=j;
    				}
    			}
    		}
    		flag=0;
    		Map[qx][qy]='X';
    		int sum=t-abs(zx-qx)-abs(zy-qy);
    		if(sum>=0&&sum%2==0){
    			dfs(qx,qy,0);
    		}
    		if(flag){
    			printf("YES\n");
    		}
    		else{
    			printf("NO\n"); 
    		}
    	}
    	return 0;
    } 
    
    展开全文
  • 搜索算法不仅在实际应用中非常重要,也是各大公司编程笔试题目重头戏,本文聚焦于两大经典的图算法:广度优先搜索(Breadth First Search)和深度优先搜索(Depth First Search)。我在学习数据结构的时候初识这两种...
  • 16.8.6 方法graph::dfs的复杂性分析 16.9 应用 16.9.1 寻找一条路径 16.9.2 连通图及其构成 16.9.3 生成树 第三部分 算法设计方法 第17章 贪婪算法 17.1 最优化问题 17.2 贪婪算法思想 17.3 应用 17.3.1 货箱装载...
  • 数据结构和算法Python 指数 1.资源- 图书 数据结构-Reema Thareja 竞争编码 ... DFS 二等分搜索 5.文件处理和OOPS 文件+班级演示 6.项目 作业调度器 电子邮件专案 哈希项目 递归小型项目 运行时分析器
  • DFS_study

    2018-09-03 11:02:30
    DFS实际中的应用关键是设置合理的递归边界和递归式,例如在PATA 1103中,要考虑数可以重复的情况,就不能想当然的在所有递归入口都把index+1,有一个入口的index是不会变化的,同时要注意剪枝,降低算法的时间...
  • 认识了二叉树,也学会了一些遍历算法DFS、BFS),可是二叉树可以干什么呢,那么其中一个实际应用他来了-堆(Heap). 堆的特点 堆是完全二叉树(逻辑上)。 堆的底层实现,其实是顺序表(元素顺序为二叉树的层序...
  • c++dfs代替枚举题解

    2018-01-29 20:30:16
    深度优先搜索(depth-first-search)简称 dfs,应该算是应用得最广泛的搜索算法,也是竞赛中经常考察的一个难点。dfs 按照深度优先的方式搜索,通俗的说就是一条路走到黑。dfs 是一种穷举的手段,实际上就是把所有的...
  • DFS 深度搜索

    2015-04-04 16:30:01
    虽然在课上学习过深度搜索,但也没在实际敲代码时应用过,在看了阿哈磊的算法书,用深度搜索的方法解决全排列的问题。“理解深度优先搜索的关键在于解决“当下该如何做”。至于“下一步该怎么做”则与“当下该如何做...
  • 本部分介绍“贪心算法“ 。 接下来会介绍动态规划。回顾一下之前脉络: 什么是递归?...首先,贪心、动规和dfs这样的搜素算法实际很相似,是为了搜索解空间获得(满足条件)的解。DFS是按照一定的(深度优
  • 马踏棋盘算法介绍和游戏演示 1)马踏棋盘算法也被称为骑士周游问题 ...1)马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。 ● 2)如果使用回溯(就是深度优先搜索)来解决,假如马儿踏了...
  • C算法(第2卷)(图算法)

    2012-12-31 10:58:13
    18.5 DFS算法 练习 18.6 分离性和双连通性 练习 18.7 广度优先搜索 练习 18.8 通用图搜索 练习 18.9 图算法的分析 练习 第19章 有向图和DAG 练习 19.1 术语和游戏规则 练习 19.2 有向图中DFS的剖析 练习 19.3 ...
  • 我们优秀的前辈们开始设计算法来解决这个实际问题。这次要介绍的Kruskal和Prim同样也是以作者名字命名的算法。 这两个算法的逻辑都很简单,关键点是要明白为什么这两个算法是可行的,也就是要验证算法的正确性。同时...
  • 游戏中的算法

    2020-08-16 21:00:18
    游戏中的两个常用算法A*算法的介绍代码实现排序算法应用 A*算法的介绍 游戏中的寻路通常由深度优先搜索(DFS)、广度优先搜索(BFS)或者A算法实现。其中DFS与BFS属于状态式搜索,A算法属于启发式搜索。今天给大家介绍...
  • 马踏棋盘算法

    2021-04-18 19:22:34
    马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。 如果使用回溯(就是深度优先搜索)来解决,假如马儿踏了 53 个点,如图:走到了第 53 个,坐标(1,0),发 现已经走到尽头,没办法,那就只能回退...
  • 常用十大算法(十)— 踏棋盘算法 博客说明 ...马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。 如果使用回溯(就是深度优先搜索)来解决,假如马儿踏了53个点,如图:走到了第5
  • 马踏棋盘算法介绍 马踏棋盘算法也被称为骑士周游问题 ...马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。 如果使用回溯(就是深度优先搜索)来解决,假如马儿踏了53个点,如图:走到了第...
  • 马踏棋盘算法介绍和游戏演示 ...马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。 如果使用回溯(就是深度优先搜索)来解决,假如马儿踏了53 个点,如图:走到了第53 个,坐标(1
  • 马踏棋盘算法实现

    2021-04-19 20:35:03
    一游戏介绍 ...1 马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。 2 如果使用回溯(就是深度优先搜索)来解决,假如马儿踏了53个点,发现已经走到尽头,没办法,那就只能回退了,...
  • 算法笔记

    2017-10-30 11:22:18
    动态规划穷竭搜索(一 )深度优先(DFS),递归实现 定义 某个状态一直转移直到无法转移,再回到上一个状态 应用 1.求解数独 2.部分和(加和不加,变成二叉树) 3….. 特点 1.有多个结果 2.每个结果可以先后...
  • 前言需求今天我们学习的是马踏棋盘算法...走遍棋盘上全部64个方格小游戏体验网址:4399:马踏棋盘小游戏一、马踏棋盘问题马踏棋盘问题(骑士周游问题)实际上是:图的深度优先搜索(DFS)的应用还记得图的深度优先搜索(D...
  • 然后学习了一段时间,感觉基本上了解了DFS和BFS的基础实现原理以及应用(不过我认为还是得通过做题来培养自己的感觉,什么时候该采取DFS,什么时候该采用BFS),它们两者间各自的优势需要通过实际的问题来具体分析,...
  • 搜索算法总结

    2016-04-25 09:47:56
    老师上课讲理论知识的时候觉着好简单啊,也很容易理解,但是一到实际应用上,一做题就懵了。  搜索有两种:首先是广度优先搜索--BFS。BFS的主要思想是逐层搜索,层层进行。对每层的结点进行检查,一层一层向下展开...
  • 图论 指数 深度优先搜索及其变体 先决条件:递归。 DFS实际应用包括周期检查,排序,连接组件,强连接组件,铰接点,铰接桥等。 下一组问题之前要讨论的主题 1. 设置1 : : : :
  •  搜索算法是我们经常要用到的算法,比如深度优先搜索、广度优先搜索算法等等,当然搜索算法千变万化,往往根据实际应用会加一些优化等等。例如,A*算法就是加了启发函数的广度优先搜索。回溯算法解决四皇后问题就...

空空如也

空空如也

1 2 3 4
收藏数 67
精华内容 26
关键字:

dfs算法实际应用