精华内容
下载资源
问答
  • 深度优先遍历和广度优先遍历

    万次阅读 多人点赞 2019-05-29 21:24:38
    深度优先遍历和广度优先遍历 什么是 深度/广度 优先遍历? 深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。 这两...

    深度优先遍历和广度优先遍历
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    什么是 深度/广度 优先遍历?

    深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。

    这两种遍历方式有什么不同呢?我们来举个栗子:

    我们来到一个游乐场,游乐场里有11个景点。我们从景点0开始,要玩遍游乐场的所有景点,可以有什么样的游玩次序呢?

    在这里插入图片描述
    第一种是一头扎到底的玩法。我们选择一条支路,尽可能不断地深入,如果遇到死路就往回退,回退过程中如果遇到没探索过的支路,就进入该支路继续深入。

    在图中,我们首先选择景点1的这条路,继续深入到景点7、景点8,终于发现走不动了(景点旁边的数字代表探索次序):
    在这里插入图片描述
    于是,我们退回到景点7,然后探索景点10,又走到了死胡同。于是,退回到景点1,探索景点9:
    在这里插入图片描述
    按照这个思路,我们再退回到景点0,后续依次探索景点2、3、5、4、6,终于玩遍了整个游乐场:
    在这里插入图片描述
    像这样先深入探索,走到头再回退寻找其他出路的遍历方式,就叫做深度优先遍历(DFS)。
    在这里插入图片描述
    在这里插入图片描述
    除了像深度优先遍历这样一头扎到底的玩法以外,我们还有另一种玩法:首先把起点相邻的几个景点玩遍,然后去玩距离起点稍远一些(隔一层)的景点,然后再去玩距离起点更远一些(隔两层)的景点…

    在图中,我们首先探索景点0的相邻景点1、2、3、4:
    在这里插入图片描述
    接着,我们探索与景点0相隔一层的景点7、9、5、6:
    在这里插入图片描述
    最后,我们探索与景点0相隔两层的景点8、10:
    在这里插入图片描述
    像这样一层一层由内而外的遍历方式,就叫做广度优先遍历(BFS)。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    深度优先遍历

    首先说说深度优先遍历的实现过程。这里所说的回溯是什么意思呢?回溯顾名思义,就是自后向前,追溯曾经走过的路径。

    我们把刚才游乐场的例子抽象成数据结构的图,假如我们依次访问了顶点0、1、7、8,发现无路可走了,这时候我们要从顶点8退回到顶点7。

    在这里插入图片描述
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/20190529211147549.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyMjE3MDE4MTAz,size_16,color_FFFFFF,t_70

    而后我们探索了顶点10,又无路可走了,这时候我们要从顶点10退回到顶点7,再退回到顶点1。
    在这里插入图片描述
    像这样的自后向前追溯曾经访问过的路径,就叫做回溯。

    要想实现回溯,可以利用栈的先入后出特性,也可以采用递归的方式(因为递归本身就是基于方法调用栈来实现)。

    下面我们来演示一下具体实现过程。

    首先访问顶点0、1、7、8,这四个顶点依次入栈,此时顶点8是栈顶:
    在这里插入图片描述
    从顶点8退回到顶点7,顶点8出栈:
    在这里插入图片描述
    接下来访问顶点10,顶点10入栈:
    在这里插入图片描述
    从顶点10退到顶点7,从顶点7退到顶点1,顶点10和顶点7出栈:
    在这里插入图片描述
    探索顶点9,顶点9入栈:
    在这里插入图片描述
    以此类推,利用这样一个临时栈来实现回溯,最终遍历完所有顶点。

    广度优先遍历

    接下来该说说广度优先遍历的实现过程了。刚才所说的重放是什么意思呢?似乎听起来和回溯差不多?其实,回溯与重放是完全相反的过程。

    仍然以刚才的图为例,按照广度优先遍历的思想,我们首先遍历顶点0,然后遍历了邻近顶点1、2、3、4:

    在这里插入图片描述
    接下来我们要遍历更外围的顶点,可是如何找到这些更外围的顶点呢?我们需要把刚才遍历过的顶点1、2、3、4按顺序重新回顾一遍,从顶点1发现邻近的顶点7、9;从顶点3发现邻近的顶点5、6。
    在这里插入图片描述
    像这样把遍历过的顶点按照之前的遍历顺序重新回顾,就叫做重放。同样的,要实现重放也需要额外的存储空间,可以利用队列的先入先出特性来实现。

    下面我们来演示一下具体实现过程。
    首先遍历起点顶点0,顶点0入队:
    在这里插入图片描述
    接下来顶点0出队,遍历顶点0的邻近顶点1、2、3、4,并且把它们入队:
    在这里插入图片描述
    然后顶点1出队,遍历顶点1的邻近顶点7、9,并且把它们入队:
    在这里插入图片描述
    然后顶点2出队,没有新的顶点可入队:
    在这里插入图片描述
    以此类推,利用这样一个队列来实现重放,最终遍历完所有顶点。

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    /**

    图的顶点
    
    / private static class Vertex { int data; Vertex(int data) {    this.data = data; } } /*
    
    图(邻接表形式)
    
    / private static class Graph { private int size; private Vertex[] vertexes; private LinkedList adj[]; Graph(int size){    this.size = size;    //初始化顶点和邻接矩阵    vertexes = new Vertex[size];    adj = new LinkedList[size];    for(int i=0; i*
    
    深度优先遍历
    
    / public static void dfs(Graph graph, int start, boolean[] visited) { System.out.println(graph.vertexes[start].data); visited[start] = true; for(int index : graph.adj[start]){    if(!visited[index]){        dfs(graph, index, visited);    } } } /*
    
    广度优先遍历
    
    */
    
    public static void bfs(Graph graph, int start, boolean[] visited, LinkedList queue) {
    
    queue.offer(start);
    
    while (!queue.isEmpty()){
    
       int front = queue.poll();
    
       if(visited[front]){
    
           continue;
    
       }
    
       System.out.println(graph.vertexes[front].data);
    
       visited[front] = true;
    
       for(int index : graph.adj[front]){
    
           queue.offer(index);;
    
       }
    
    }
    
    }
    
    public static void main(String[] args) {
    
    Graph graph = new Graph(6);
    
    graph.adj[0].add(1);
    
    graph.adj[0].add(2);
    
    graph.adj[0].add(3);
    
    graph.adj[1].add(0);
    
    graph.adj[1].add(3);
    
    graph.adj[1].add(4);
    
    graph.adj[2].add(0);
    
    graph.adj[3].add(0);
    
    graph.adj[3].add(1);
    
    graph.adj[3].add(4);
    
    graph.adj[3].add(5);
    
    graph.adj[4].add(1);
    
    graph.adj[4].add(3);
    
    graph.adj[4].add(5);
    
    graph.adj[5].add(3);
    
    graph.adj[5].add(4);
    
    System.out.println("图的深度优先遍历:");
    
    dfs(graph, 0, new boolean[graph.size]);
    
    System.out.println("图的广度优先遍历:");
    
    bfs(graph, 0, new boolean[graph.size], new LinkedList());
    
    }
    

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 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遍历完成。

    展开全文
  • 深度优先遍历(DFS)和广度优先遍历(BFS)

    万次阅读 多人点赞 2019-05-09 10:46:23
    图的搜索有两种方式,一种是深度优先搜索(Depth-First-Search),另一种是广度优先搜索(Breadth-First-Search),接下来,我们来写一下这些搜索方式的Java实现,同样的,这里的代码均继承了自定义的EnhanceModual...
  • 深度优先算法

    2014-10-13 16:13:26
    深度优先算法C语言实现,为大家提供深度优先算法的具体编译内容。
  • 深度优先搜索

    2013-04-27 08:19:39
    深度优先搜索
  • 主要介绍了python实现图的深度优先搜索和广度优先搜索相关知识点,对此有兴趣的朋友学习下。
  • 爬虫深度优先与广度优先.rar
  • 数据结构深度优先.rar

    2020-07-16 20:31:37
    数据结构中图的深度优先算法 深度优先遍历, 刷过题的朋友应该都很熟悉了,难是不难,但是理解起来还是要费一些功夫的. 深度优先遍历的实现方法有递归和非递归两种, 这里我们用可视化的角度,讲解前一种: 递归的深度优先...
  • 广度优先遍历和深度优先遍历等js函数
  • 深度优先搜索算法

    2016-04-09 17:56:52
    深度优先C代码
  • 天津理工大学实验报告 学院系名称 计算机与通信工程学院 姓名 学号 专业 计算机科学与技术 班级 2009 级 1 班 实验项目 实验四 图的深度优先与广度优先遍历 课程名称 数据结构与算法 课程代码 实验时间 2011 年 5 月...
  • 主要介绍了python图的深度优先和广度优先算法,结合实例形式分析了图的深度优先算法与广度优先算法相关概念、原理、实现技巧与操作注意事项,需要的朋友可以参考下
  • Java实现深度优先遍历和广度优先遍历

    万次阅读 多人点赞 2018-08-16 15:38:33
    深度优先遍历:深度优先遍历是图论中的经典算法。其利用了深度优先搜索算法可以产生目标图的相应拓扑排序表,采用拓扑排序表可以解决很多相关的图论问题,如最大路径问题等等。 根据深度优先遍历的特点我们利用Java...
  • 深度优先算法DFS.cpp

    2021-04-22 08:23:30
    深度优先算法C/C++实现
  • C#深度优先搜索算法

    2020-08-30 04:28:24
    主要介绍了C#深度优先搜索算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 主要介绍了python实现树的深度优先遍历与广度优先遍历,详细分析了树的深度优先遍历与广度优先遍历原理及Python相关实现技巧,需要的朋友可以参考下
  • 实现深度优先广度优先算法
  • 主讲人 李 刚 图的深度优先遍历 C 目 录 ONTENTS 01 深度优先遍历实例演示 深度优先遍历实例演示 1 1 2 3 4 5 6 7 8 9 02 深度优先遍历实现过程 深度优先遍历实现过程 2 操作步骤 V1 V2 V5 V3 V0 V7 V6 V4 V8 在图中...
  • 主要介绍了JavaScript树的深度优先遍历和广度优先遍历算法,结合实例形式分析了JavaScript树的深度优先遍历、广度优先遍历递归与非递归相关实现技巧,需要的朋友可以参考下
  • 主要介绍了python数据结构之图深度优先和广度优先,较为详细的分析了深度优先和广度优先算法的概念与原理,并给出了完整实现算法,具有一定参考借鉴价值,需要的朋友可以参考下
  • 深度优先遍历 广度优先遍历 的实现 深度优先遍历 广度优先遍历 的实现 深度优先遍历 广度优先遍历 的实现
  • 狼和鸡 使用广度优先,深度优先,迭代加深深度优先和A星图搜索算法来解决狼和小鸡游戏。
  • 1 深度优先搜索 2 广度优先搜索 3 深度优先和广度优先的比较 前言 最近面试,被问到了深度优先和广度优先搜索,这个我似曾相识,曾经大学的时候学到过,但是由于这几年的工作都未接触到,所以就已经忘的差不多了...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 166,035
精华内容 66,414
关键字:

深度优先