精华内容
下载资源
问答
  • 深度优先搜索广度优先搜索详解+代码实现
    2021-05-29 18:16:43

    前言

    深度优先搜索其实不止可以用在图,也可以用在树,因为树可以看成一种特殊的,较为简单的图。在leetcode上,关于树的题目中经常会用到DFS和BFS以及它们的变体,所以掌握代码是很重要的

    深度优先搜索

    理解

    所谓深度优先,就是优先往下一层走。

    步骤

    理解起来很容易,让我们来看看步骤:

    1. 挑一个顶点开始(一般按顶点存在数组中的顺序来,或者abcd…,1234…这种)
    2. 访问它
    3. 将该顶点入栈,并使用visited数组进行标记
    4. 将栈中的顶点出栈
    5. 访问它的有边的顶点
    6. 重复第二个步骤至第五个步骤直到所有顶点均已被访问(在visited数组中)

    代码

    树(代码是根据leetcode结构写的)

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    void DFS(TreeNode* root) {
        	if(!root)
            	return;
            vector<int> v;
            stack<TreeNode*> s;
            s.push(root);// 初始化
            while(!s.empty())
            {
                int len = s.size();
                for(int i = 0; i < len; i++)
                {
                    TreeNode* temp = s.top();
                    s.pop();
                    v.push_back(temp->val);
                    if(temp->right)
                        s.push(temp->right);
                    if(temp->left)
                        s.push(temp->left);
                }
            }
            
            // print v // 也可以定义个打印函数
            for(auto x: v){
            	cout << x << ", ";	
            }
            cout << endl;
        }
    

    广度优先搜索

    理解

    所谓广度优先,就是优先往同一层的其他节点走。

    步骤

    理解起来很容易,让我们来看看步骤:

    1. 挑一个顶点开始
    2. 访问它
    3. 将该顶点入队,并使用visited数组进行标记
    4. 将队列中的顶点出队
    5. 访问该与该顶点有边的顶点
    6. 重复第二个步骤至第五个步骤直到所有顶点均已被访问(在visited数组中)

    代码

    树(代码是从我自己在某题leetcode上复制下来的)

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        void BFS(TreeNode* root) {
        	if(!root)
            	return;
            vector<int> v;
            queue<TreeNode*> q;
            q.push(root);// 初始化
            while(!q.empty())
            {
                int len = q.size();
                for(int i = 0; i < len; i++)
                {
                    TreeNode* temp = q.front();
                    q.pop();
                    v.push_back(temp->val);
                    if(temp->left)
                        q.push(temp->left);
                    if(temp->right)
                        q.push(temp->right);
                }
            }
            
            // print v // 也可以定义个打印函数
            for(auto x: v){
            	cout << x << ", ";	
            }
            cout << endl;
        }
    };
    

    总结

    DFS和BFS总体上还是很简单的,它灵活地运用了队列和栈这两个前面我们学习过的数据结构来实现。这给了我挺大的启发,原来我们可以将不同的数据结构结合在一起,从而创造出更加有趣的应用。

    PS:
    图的代码可以参考我另一篇博客代码实现:用C语言实现Stack,Queue,Graph的邻接矩阵,BFS和DFS还有拓扑排序如果有时间,我也会在这里用c++写图的代码

    更多相关内容
  • 主要介绍了Python数据结构与算法之广度优先与深度优先搜索算法,结合实例形式分析了广度优先与深度优先搜索算法原理与相关实现技巧,需要的朋友可以参考下
  • 主要介绍了python实现深度优先搜索广度优先搜索相关知识点,对此有兴趣的朋友学习下。
  • 主要介绍了python深度优先广度优先算法,结合实例形式分析了深度优先算法与广度优先算法相关概念、原理、实现技巧与操作注意事项,需要的朋友可以参考下
  • 这篇文章主要介绍了python 递归深度优先搜索广度优先搜索算法模拟实现 ,非常不错,具有一定的参考借鉴价值,需要的朋友可以参考下 一、递归原理小案例分析 (1)# 概述 递归:即一个函数调用了自身,即实现了递归 ...
  • ①使用深度优先搜索来解决八数码问题 ②使用广度优先搜索来解决八数码问题 ③使用过程式表示和实现八数码问题 以及相关代码详细注释 过程式知识表示是将有关某一问题领域的知识, 连同如何使用这些知识的方法,均...
  • 广度优先搜索和宽度优先搜索的动画演示,均为gif,大家可以自行看看,理解思路或者放Ppt里很好用,怎么分数是5分,编辑不了了? 请管理员修改为1分,谢谢
  • 主要介绍了Java编程实现基于深度优先搜索广度优先搜索完整代码,具有一定借鉴价值,需要的朋友可以了解下。
  • 1.前言 和树的遍历类似,的遍历也是从中某点出发...根据搜索路径的不同,我们可以将遍历的方法分为两种:广度优先搜索和深度优先搜索。 2.的基本概念 无向:顶点对(u,v)是无序的,即(u,v)和(v,u)是...

    1.前言

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

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

    根据搜索路径的不同,我们可以将遍历图的方法分为两种:广度优先搜索和深度优先搜索。
    2.图的基本概念
    无向图:顶点对(u,v)是无序的,即(u,v)和(v,u)是同一条边。常用一对圆括号表示。如图所示:
    在这里插入图片描述
    有向图:顶点对<u,v>是有序的,它是指从顶点u到顶点 v的一条有向边。其中u是有向边的始点,v是有向边的终点。常用一对<>表示。如图所示:
    在这里插入图片描述
    连通图:在无向图G中,从顶点v到顶点v’有路径,则称v和v’是联通的。若图中任意两顶点v、v’∈V,v和v’之间均联通,则称G是连通图。上述两图均为连通图。如图所示:
    在这里插入图片描述
    非连通图:若无向图G中,存在v和v’之间不连通,则称G是非连通图。如图所示:
    在这里插入图片描述
    3.广度优先搜索
    基本思想:宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。
    广度优先搜索算法的搜索步骤一般是:
    (1)从队列头取出一个结点,检查它按照扩展规则是否能够扩展,如果能则产生一个新结点。
    (2)检查新生成的结点,看它是否已在队列中存在,如果新结点已经在队列中出现过,就放弃这个结点,然后回到第(1)步。否则,如果新结点未曾在队列中出现过,则将它加入到队列尾。
    (3)检查新结点是否目标结点。如果新结点是目标结点,则搜索成功,程序结束;若新结点不是目标结点,则回到第(1)步,再从队列头取出结点进行扩展。
    最终可能产生两种结果:找到目标结点,或扩展完所有结点而没有找到目标结点。
    如果目标结点存在于解答树的有限层上,广度优先搜索算法一定能保证找到一条通向它的最佳路径,因此广度优先搜索算法特别适用于只需求出最优解的问题。当问题需要给出解的路径,则要保存每个结点的来源,也就是它是从哪一个节点扩展来的。
    对于广度优先搜索算法来说,问题不同则状态结点的结构和结点扩展规则是不同的,但搜索的策略是相同的。
    广度优先搜索如图所示:
    1.初始时全部顶点均未被访问,visited数组初始化为0,队列中没有元素。
    在这里插入图片描述
    2.即将访问顶点v0。
    在这里插入图片描述
    3.访问顶点v0,并置visited[0]的值为1,同时将v0入队。
    在这里插入图片描述
    4.将v0出队,访问v0的邻接点v2。判断visited[2],因为visited[2]的值为0,访问v2。
    在这里插入图片描述
    5.将visited[2]置为1,并将v2入队。
    在这里插入图片描述
    6.访问v0邻接点v1。判断visited[1],因为visited[1]的值为0,访问v1。
    在这里插入图片描述
    7.将visited[1]置为0,并将v1入队。
    在这里插入图片描述
    8.判断visited[3],因为它的值为0,访问v3。将visited[3]置为0,并将v3入队。
    在这里插入图片描述
    9.v0的全部邻接点均已被访问完毕。将队头元素v2出队,开始访问v2的所有邻接点。

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

    继续访问v2邻接点v4,判断visited[4],因为其值为0,访问v4,如下图:
    在这里插入图片描述
    10.将visited[4]置为1,并将v4入队。
    在这里插入图片描述
    11.v2的全部邻接点均已被访问完毕。将队头元素v1出队,开始访问v1的所有邻接点。

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

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

    继续访问v1邻接点v5,因为visited[5]值为0,访问v5,如下图:
    在这里插入图片描述
    12.将visited[5]置为1,并将v5入队。
    在这里插入图片描述
    13.v1的全部邻接点均已被访问完毕,将队头元素v3出队,开始访问v3的所有邻接点。

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

    继续访问v3邻接点v5,因为visited[5]值为1,不进行访问。
    在这里插入图片描述
    14.v3的全部邻接点均已被访问完毕,将队头元素v4出队,开始访问v4的所有邻接点。

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

    继续访问v4的邻接点v6,因为visited[6]的值为0,访问v6,如下图:
    在这里插入图片描述
    15.将visited[6]值为1,并将v6入队。
    在这里插入图片描述
    16.v4的全部邻接点均已被访问完毕,将队头元素v5出队,开始访问v5的所有邻接点。

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

    继续访问v5邻接点v6,因为visited[6]的值为1,不进行访问
    在这里插入图片描述
    17.v5的全部邻接点均已被访问完毕,将队头元素v6出队,开始访问v6的所有邻接点。

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

    继续访问v6邻接点v5,因为visited[5]的值文1,不进行访问。
    在这里插入图片描述
    18.队列为空,退出循环,全部顶点均访问完毕。
    在这里插入图片描述
    广度优先搜索例题:
    【例一】 有一个宽为W、高为H的矩形平面,用黑色和红色两种颜色的方砖铺满。一个小朋友站在一块黑色方块上开始移动,规定移动方向有上、下、左、右四种,且只能在黑色方块上移动(即不能移到红色方块上)。编写一个程序,计算小朋友从起点出发可到达的所有黑色方砖的块数(包括起点)。
    例如,如图1所示的矩形平面中,“#”表示红色砖块,“.”表示黑色砖块,“@”表示小朋友的起点,则小朋友能走到的黑色方砖有28块。
    在这里插入图片描述
    代码如下:

    #include <iostream>
    using namespace std;
    
    #define N 21
    struct Node
    {
        int x;
        int y;
    };
    
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,-1,1};
    char map[N][N];
    int visit[N][N];
    int bfs(int startx, int starty,int w,int h)
    {
    	Node q[N*N],cur,next;   // q为队列
           int  front,rear;        // front为队头指针,rear为队尾指针
           int i,x,y,sum;    
           front=rear=0;           // 队列q初始化
           sum=0;
           cur.x=startx;   cur.y=starty; 
           visit[startx][starty]=1;
           q[rear++]=cur;          // 初始结点入队
           while(rear!=front)      // 队列不为空
           {
                  cur=q[front++];     // 队头元素出队
                  sum++;              // 方砖计数
                  for (i=0;i<4;i++)
                  {
                      x=cur.x+dx[i];  y=cur.y+dy[i];
                     if(x >=0 && x<h && y>=0 && y<w && map[x][y]!='#' && visit[x][y]==0)
                     {
                            visit[x][y] = 1;
                            next.x=x;  next.y=y;  // 由cur扩展出新结点next
                            q[rear++]=next;       // next结点入队
                      } 
                  }
           }
           return sum;
    }
    
    int main()
    {
       int i,j,pos_x,pos_y,w,h,sum;
       while(1)
       {
        cin>>w>>h; 
        if(w==0 && h==0) break;
           for(i=0;i<h;i++)
           {
            	for(j=0;j<w;j++)
    	        {
    				cin>>map[i][j];
    	            if(map[i][j]=='@')
    	            {
    	               pos_x = i;
    	               pos_y = j;
    	            }
    	            visit[i][j] = 0;
    	        }
          }
          sum=bfs(pos_x, pos_y,w,h);
          cout<<sum<<endl;
       }
       return 0;
    }
    

    4.深度优先搜索
    基本思想:深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止,然后返回到某一个HTML文件,再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时,说明搜索已经结束。
    深度优先搜索DFS(Depth First Search)是从初始结点开始扩展,扩展顺序总是先扩展最新产生的结点。这就使得搜索沿着状态空间某条单一的路径进行下去,直到最后的结点不能产生新结点或者找到目标结点为止。当搜索到不能产生新的结点的时候,就沿着结点产生顺序的反方向寻找可以产生新结点的结点,并扩展它,形成另一条搜索路径。
    为了便于进行搜索,要设置一个表存储所有的结点。由于在深度优先搜索算法中,要满足先生成的结点后扩展的原则,所以存储结点的表一般采用栈这种数据结构。
    深度优先搜索算法的搜索步骤一般是:
    (1)从初始结点开始,将待扩展结点依次放到栈中。
    (2)如果栈空,即所有待扩展结点已全部扩展完毕,则问题无解,退出。
    (3)取栈中最新加入的结点,即栈顶结点出栈,并用相应的扩展原则扩展出所有的子结点,并按顺序将这些结点放入栈中。若没有子结点产生,则转(2)。
    (4)如果某个子结点为目标结点,则找到问题的解(这不一定是最优解),结束。如果要求得问题的最优解,或者所有解,则转(2),继续搜索新的目标结点。
    深度优先搜索如图所示:
    1.初始时所有顶点均未被访问,visited数组为空。
    在这里插入图片描述
    2.即将访问v0。
    在这里插入图片描述
    3.访问v0,并将visited[0]的值置为1。
    在这里插入图片描述
    4.访问v0的邻接点v2,判断visited[2],因其值为0,访问v2。
    在这里插入图片描述
    5.将visited[2]置为1。
    在这里插入图片描述
    6.访问v2的邻接点v0,判断visited[0],其值为1,不访问。

    继续访问v2的邻接点v4,判断visited[4],其值为0,访问v4。
    在这里插入图片描述
    7.将visited[4]置为1。
    在这里插入图片描述
    8.访问v4的邻接点v1,判断visited[1],其值为0,访问v1。
    在这里插入图片描述
    9.将visited[1]置为1。
    在这里插入图片描述
    10.访问v1的邻接点v0,判断visited[0],其值为1,不访问。

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

    继续访问v1的邻接点v5,判读visited[5],其值为0,访问v5。
    在这里插入图片描述
    11.将visited[5]置为1。
    在这里插入图片描述
    12.访问v5的邻接点v1,判断visited[1],其值为1,不访问。

    继续访问v5的邻接点v3,判断visited[3],其值为0,访问v3。
    在这里插入图片描述
    13.将visited[1]置为1。
    在这里插入图片描述
    14.访问v3的邻接点v0,判断visited[0],其值为1,不访问。

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

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

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

    在这里插入图片描述
    15.将visited[6]置为1。
    在这里插入图片描述
    16.访问v6的邻接点v4,判断visited[4],其值为1,不访问。

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

    v6所有邻接点均已被访问,回溯到其上一个顶点v5,遍历v5剩余邻接点。
    在这里插入图片描述
    17.v5所有邻接点均已被访问,回溯到其上一个顶点v1。

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

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

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

    v1所有邻接点均已被访问,搜索结束。
    在这里插入图片描述
    深度优先搜索例题:
    【例1】黑色方块

    有一个宽为W、高为H的矩形平面,用黑色和红色两种颜色的方砖铺满。一个小朋友站在一块黑色方块上开始移动,规定移动方向有上、下、左、右四种,且只能在黑色方块上移动(即不能移到红色方块上)。编写一个程序,计算小朋友从起点出发可到达的所有黑色方砖的块数(包括起点)。

    例如,如图1所示的矩形平面中,“#”表示红色砖块,“.”表示黑色砖块,“@”表示小朋友的起点,则小朋友能走到的黑色方砖有28块。
    在这里插入图片描述
    代码如下:

    #include <iostream>
    using namespace std;
    
    #define N 21
    struct Node
    {
           int x;
           int y;
    };
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,-1,1};
    char map[N][N];
    int visit[N][N];
    int dfs(int startx, int starty,int w,int h)
    {
           Node s[N*N],cur,next;     // s为栈
           int  top,i,x,y,sum;        // top为栈顶指针
           top=-1;                 // 栈S初始化
           sum=0;
           cur.x=startx;   cur.y=starty; 
           visit[startx][starty]=1;
           s[++top]=cur;           // 初始结点入栈;
           while(top>=0)           // 栈不为空
           {
                  cur=s[top--];        // 栈顶元素出栈
                  sum++;           // 方砖计数
                  for (i=0;i<4;i++)
                  {
                        x=cur.x+dx[i];  y=cur.y+dy[i];
                        if(x >=0 && x<h && y>=0 && y<w && map[x][y]!='#' && visit[x][y]==0)
                       {
                            visit[x][y] = 1;
                            next.x=x;  next.y=y;  // 由cur扩展出新结点next
                            s[++top]=next;        // next结点入栈
                        }
                  }
           }
           return sum;
    }
    
    int main()
    {
       int i,j,pos_x,pos_y,w,h,sum;
       while(1)
       {
              cin>>w>>h;
              if (w==0 && h==0) break;
              for(i=0;i<h;i++)
              {
                  for(j=0;j<w;j++)
                  {
                           cin>>map[i][j];
                            if (map[i][j]=='@')
                           {
                                pos_x = i;   pos_y = j;
                           }
                           visit[i][j] = 0;
                    }
              }
              sum=dfs(pos_x, pos_y,w,h);
              cout<<sum<<endl;
       }
       return 0;
    }
    

    对于同样的问题,如果深搜和广搜都可以的话,推荐使用广搜,因为广搜不用递归调用系统栈,所以它的速度更快一些。
    参考博客:
    https://blog.csdn.net/weixin_40953222/article/details/80544928
    https://www.cnblogs.com/cs-whut/p/11147213.html
    努力加油a啊,(o)/~

    展开全文
  • 广度优先搜索构建迷宫(BFS算法)动态构建过程的python 源代码,详情请移步本人博客<迷宫与寻路可视化(二)广度优先搜索构建迷宫(BFS算法)>
  • 深度优先搜索 类似树的深度优先遍历,所谓深度优先即递归的对相邻节点进行访问。从来访问的越来越深。... * 深度优先搜索 * @author yjw * @date 2019/5/16/016 */ public class DepthF...

    引言

    本文介绍了无向图的深度优先搜索和使用广度优先搜索寻找图中的路径,它们分别借助了栈(先进后出)和队列(先进先出)的特性来实现。

    有关图的概念可参考博文数据结构之图的概述

    深度优先搜索

    类似树的深度优先遍历,所谓深度优先即递归的对相邻节点进行访问。从图来看即访问的越来越深,不撞南墙不回头!!

    在这里插入图片描述
    在访问某个顶点时:

    • 将它标记为已访问
    • 递归地访问它的所有没有标记过的邻接顶点
    package com.algorithms.graph;
    
    /**
     * 图的深度优先搜索
     * @author yjw
     * @date 2019/5/16/016
     */
    public class DepthFirstSearch {
        /**
         * 标记是否被访问过
         */
        private boolean[] marked;
        private int count;
    
        public DepthFirstSearch(Graph g,int s) {
            marked = new boolean[g.vertexNum()];
            dfs(g,s);
        }
    
        public boolean marked(int v) {
            return marked[v];
        }
    
        public int count() {
            return count;
        }
    
        private void dfs(Graph g,int v) {
            marked[v] = true;
            System.out.print(v + " ");
            count++;
            /**
             * 深度就是递归调用,
             * 访问某个顶点时,将它标记为已访问;
             * 递归地访问它所有没有被标记过的邻接点
             */
            for (int w: g.adj(v)) {
                if (!marked[w]) {
                    dfs(g,w);
                }
            }
        }
    }
    
    

    因为存在递归调用,因此底层是利用了栈来实现的。

    使用广度优先搜索寻找图中的路径

    给定一个起点s,若想寻找从s到某个顶点v的最短路径(所含边数最少),那么就要用到广度优先搜索。

    从图来看是优先访问某顶点的相邻顶点,有点像生活中玻璃的裂缝效果。

    上面说了深度优先搜索是基于栈的,而广度优先搜索是基于队列的。

    在这里插入图片描述
    先将起点加入队列,然后重复下列步骤直到队列为空:

    • 取队列中的下一个顶点v并标记它为已访问;
    • 将与v相邻的所有未被标记过的顶点加入队列
    package com.algorithms.graph;
    
    import com.algorithms.queue.Queue;
    import com.algorithms.stack.Stack;
    
    /**
     * @author yjw
     * @date 2019/5/20/020
     */
    public class BreadthFirstPaths {
        private boolean[] marked;
        /**
         * 到达当前顶点的最近顶点
         */
        private int[] edgeTo;
        private final int s;
    
        public BreadthFirstPaths(Graph g, int s) {
            marked = new boolean[g.vertexNum()];
            edgeTo = new int[g.vertexNum()];
            this.s = s;
            bfs(g, s);
        }
    
        private void bfs(Graph g, int s) {
            Queue<Integer> queue = new Queue<>();
            marked[s] = true;
            queue.enqueue(s);
            while (!queue.isEmpty()) {
                int v = queue.dequeue();
                /**
                 * 将与v相邻的所有未被标记的顶点加入队列
                 */
                for (int e: g.adj(v)) {
                    if (!marked[e]) {
                        marked[e] = true;
                        edgeTo[e] = v;
                        queue.enqueue(e);
                    }
                }
            }
        }
    
        public boolean hasPathTo(int v) {
            return marked[v];
        }
    
        public Iterable<Integer> pathTo(int v) {
            if (!hasPathTo(v)) {
                return null;
            }
            Stack<Integer> path = new Stack<>();
            /**
             * 从路径终点一步步寻找前一个顶点
             */
            for (int x = v; x != s ; x = edgeTo[x]) {
                path.push(x);
            }
            /**
             * 利用栈后进先出刚好可以顺序打印路径上所有顶点
             */
            path.push(s);
            return path;
        }
    }
    
    

    其中QueueStack的实现见 栈和队列的实现

    展开全文
  • 一、递归原理小案例分析 (1)# 概述 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! (2)# 写递归的过程 1、写出临界条件 2、找出这一次和上一次关系 3、假设当前函数已经能用...
  • 一、无向 1.1 的相关术语 相邻顶点: 当两个顶点通过一条边相连时,我们称这两个顶点是相邻的,并且称这条边依附于这两个顶点。 度: 某个顶点的度就是依附于该顶点的边的个数。 子图: 是一幅的所有边的子集...

    一、无向图

    1.1 图的相关术语

    相邻顶点

    当两个顶点通过一条边相连时,我们称这两个顶点是相邻的,并且称这条边依附于这两个顶点。

    度:

    某个顶点的度就是依附于该顶点的边的个数。

    子图:

    是一幅图的所有边的子集(包含这些边依附的顶点)组成的图。

    路径:

    是由边顺序连接的一系列的顶点组成。

    环:

    是一条至少含有一条边且终点和起点相同的路径。

    连通图:

    如果图中任意一个顶点都存在一条路径到达另外一个顶点,那么这幅图就称之为连通图。

    连通子图:

    一个非连通图由若干连通的部分组成,每一个连通的部分都可以称为该图的连通子图。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vQi7JjAp-1629734965759)(images/image61.png)]

    1.2 图的存储结构

    要表示一幅图,只需要表示清楚以下两部分内容即可:

    1. 图中所有的顶点;
    2. 所有连接顶点的边;

    常见的图的存储结构有两种:邻接矩阵和邻接表

    1.2.1 邻接矩阵

    1. 使用一个V*V的二维数组int[V] [V] adj,把索引的值看做是顶点;
    2. 如果顶点v和顶点w相连,我们只需要将adj[v] [w]和adj[w] [v]的值设置为1,否则设置为0即可。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PDDBqvdJ-1629734965765)(images/image62.png)]

    很明显,邻接矩阵这种存储方式的空间复杂度是V^2的,如果我们处理的问题规模比较大的话,内存空间极有可能不够用。

    1.2.2 邻接表

    使用一个大小为V的数组 Queue[V] adj,把索引看做是顶点

    每个索引处adj[v]存储了一个队列,该队列中存储的是所有与该顶点相邻的其他顶点

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8webW48G-1629734965769)(images/image63.png)]

    很明显,邻接表的空间并不是是线性级别的

    1.3 图的实现

    1.3.1 图的API设计

    类名Graph
    构造方法Graph(int V):创建一个包含V个顶点但不包含边的图
    成员方法1.public int V():获取图中顶点的数量
    2.public int E():获取图中边的数量
    3.public void addEdge(int v,int w):向图中添加一条边 v-w
    4.public Queue adj(int v):获取和顶点v相邻的所有顶点
    成员变量1.private final int V: 记录顶点数量
    2.private int E: 记录边数量
    3.private Queue[] adj: 邻接表

    1.3.2 代码实现

    package cn.itcast.algorithm.graph;
    
    import cn.itcast.algorithm.linear.Queue;
    
    /**
     * 无向图
     */
    public class Graph {
        // 顶点数目
        private final int V;
        // 边的数目
        private int E;
        // 邻接表
        private Queue<Integer>[] adj;
    
        public Graph(int v) {
            // 初始化顶点的数量
            this.V = v;
            // 初始化边的数量
            this.E = 0;
            // 初始化邻接表
            this.adj = new Queue[V];
            for (int i = 0; i < V; i++) {
                adj[i] = new Queue<Integer>();
            }
        }
    
        // 获取顶点的数目
        public int V() {
            return V;
        }
    
        // 获取边的数目
        public int E() {
            return E;
        }
    
        // 向图中添加一条边 v-w
        public void addEdge(int v, int w) {
            // 无向图中边是无方向的,所以可以说该边是从v到w的,也可以说是从w到v的,所以要让w出现在v的邻接表中,也要让v出现在w的邻接表中
            adj[v].enqueue(w);
            adj[w].enqueue(v);
            // 边的数量+1
            E++;
        }
    
        // 获取和顶点v相邻的所有的顶点
        public Queue<Integer> adj(int v) {
            return adj[v];
        }
    
    }
    

    1.4 图的搜索

    在很多情况下,我们需要遍历图,得到图的一些性质,例如,找出图中与指定的顶点相连的所有顶点,或者判定某个顶点与指定顶点是否相通,是非常常见的需求。

    有关图的搜索,最经典的算法有深度优先搜索和广度优先搜索,接下来我们分别讲解这两种搜索算法。

    1.4.1 深度优先搜索

    所谓的深度优先搜索,指的是在搜索时,如果遇到一个结点既有子结点,又有兄弟结点,那么先找子结点,然后找兄弟结点。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rok8eOyL-1629734965771)(images/image64.png)]

    很明显,在由于边是没有方向的,所以,如果4和5顶点相连,那么4会出现在5的相邻链表中,5也会出现在4的相邻链表中,那么为了不对顶点进行重复搜索,应该要有相应的标记来表示当前顶点有没有搜索过,可以使用一个布尔类型的数组 boolean[V] marked,索引代表顶点,值代表当前顶点是否已经搜索,如果已经搜索,标记为true,如果没有搜索,标记为false;

    API设计:

    类名DepthFirstSearch
    构造方法DepthFirstSearch(Graph G,int s):构造深度优先搜索对象,使用深度优先搜索找出G图中s顶点的所有相通顶点
    成员方法1.private void dfs(Graph G, int v):使用深度优先搜索找出G图中v顶点的所有相通顶点
    2.public boolean marked(int w):判断w顶点与s顶点是否相通
    3.public int count():获取与顶点s相通的所有顶点的总数
    成员变量1.private boolean[] marked: 索引代表顶点,值表示当前顶点是否已经被搜索
    2.private int count:记录有多少个顶点与s顶点相通

    代码:

    /**
     * 深度优先搜索--无向图
     */
    public class DepthFirstSearch {
        // 索引代表顶点,值表示当前顶点是否已经被搜索
        private boolean[] marked;
        // 记录有多少个顶点与s顶点相通
        private int count;
    
        //构造深度优先搜索对象,使用深度优先搜索找出G图中s顶点的所有相邻顶点
        public DepthFirstSearch(Graph G, int s) {
            // 初始化与s顶点相通的顶点的个数
            this.count = 0;
            // 创建一个和图的顶点数一样大小的布尔数组
            this.marked = new boolean[G.V()];
            // 搜索G图中与顶点s相同的所有顶点
            dfs(G, s);
        }
    
        // 使用深度优先搜索找出G图中v顶点的所有相邻顶点
        private void dfs(Graph G, int v) {
            // 将当前结点标记为true
            marked[v] = true;
            // 遍历v顶点的邻接表,得到每一个顶点w
            for (Integer w : G.adj(v)) {
                // 如果当前顶点w没有被搜索过,则递归搜索与w顶点相通的其他顶点
                if (!marked[w]) {
                    // 相通的顶点数量+1
                    count++;
                    dfs(G, w);
                }
            }
        }
    
        // 判断w顶点与s顶点是否相通
        public boolean marked(int w) {
            return marked[w];
        }
    
        // 获取与顶点s相通的所有顶点的总数
        public int count() {
            return count;
        }
    }
    

    1.4.2 广度优先搜索

    所谓的深度优先搜索,指的是在搜索时,如果遇到一个结点既有子结点,又有兄弟结点,那么先找兄弟结点,然后找子结点。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wTRPyCyW-1629734965773)(images/image65.png)]

    API设计

    类名BreadthFirstSearch
    构造方法BreadthFirstSearch(Graph G,int s):构造广度优先搜索对象,使用广度优先搜索找出G图中s顶点的所有相邻顶点
    成员方法1.private void bfs(Graph G, int v):使用广度优先搜索找出G图中v顶点的所有相邻顶点
    2.public boolean marked(int w):判断w顶点与s顶点是否相通
    3.public int count():获取与顶点s相通的所有顶点的总数
    成员变量1.private boolean[] marked: 索引代表顶点,值表示当前顶点是否已经被搜索
    2.private int count:记录有多少个顶点与s顶点相通
    3.private Queue waitSearch: 用来存储待搜索邻接表的点

    代码:

    /**
     * 广度优先搜索--无向图
     */
    public class BreadthFirstSearch {
        // 索引代表顶点,值表示当前顶点是否已经被搜索
        private boolean[] marked;
        // 记录有多少个顶点与s顶点相通
        private int count;
        // 用来存储待搜索邻接表的点
        private Queue<Integer> waitSearch;
    
        // 构造广度优先搜索对象,使用广度优先搜索找出G图中s顶点的所有相邻顶点
        public BreadthFirstSearch(Graph G, int s) {
            // 初始化与s顶点相通的顶点的个数
            this.count = 0;
            // 创建一个和图的顶点数一样大小的布尔数组
            this.marked = new boolean[G.V()];
            // 初始化待搜索顶点的队列
            waitSearch = new Queue<Integer>();
            // 搜索G图中与顶点v相通的所有顶点
            dfs(G, s);
        }
    
        // 使用广度优先搜索找出G图中v顶点的所有相邻顶点
        private void dfs(Graph G, int v) {
            // 将当前顶点标记为true
            marked[v] = true;
            // 将当前顶点v入队列,待搜索
            waitSearch.enqueue(v);
            // 队列不为空,则从队列中弹出一个待搜索的顶点进行搜索
            while (!waitSearch.isEmpty()) {
                // 弹出待搜索的顶点
                Integer wait = waitSearch.dequeue();
                // 遍历当前顶点的连通顶点
                for (Integer w : G.adj(wait)) {
                    // 未被搜索过的顶点进行入队列,并进行已搜索标识
                    if (!marked(w)) {
                        waitSearch.enqueue(w);
                        marked[w] = true;
                        // 连通顶点数量+1
                        count++;
                    }
                }
            }
        }
    
        // 判断w顶点与s顶点是否相通
        public boolean marked(int w) {
            return marked[w];
        }
    
        // 获取与顶点s相通的所有顶点的总数
        public int count() {
            return count;
        }
    }
    

    1.5 路径查找

    在实际生活中,地图是我们经常使用的一种工具,通常我们会用它进行导航,输入一个出发城市,输入一个目的地城市,就可以把路线规划好,而在规划好的这个路线上,会路过很多中间的城市。这类问题翻译成专业问题就是:从s顶点到v顶点是否存在一条路径?如果存在,请找出这条路径。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MhoTRcnu-1629734965774)(images/image66.png)]

    例如在上图上查找顶点0到顶点4的路径用红色标识出来,那么我们可以把该路径表示为 0-2-3-4。

    1.5.1 路径查找API设计

    类名DepthFirstPaths
    构造方法DepthFirstPaths(Graph G,int s):构造深度优先搜索对象,使用深度优先搜索找出G图中起点为s的所有路径
    成员方法1.private void dfs(Graph G, int v):使用深度优先搜索找出G图中v顶点的所有相邻顶点
    2.public boolean hasPathTo(int v):判断v顶点与s顶点是否存在路径
    3.public Stack pathTo(int v):找出从起点s到顶点v的路径(就是该路径经过的顶点)
    成员变量1.private boolean[] marked: 索引代表顶点,值表示当前顶点是否已经被搜索
    2.private int s:起点
    3.private int[] edgeTo:索引代表顶点,值代表从起点s到当前顶点路径上的最后一个顶点

    1.5.2 路径查找的实现

    我们实现路径查找,最基本的操作还是得遍历并搜索图,所以,我们的实现暂且基于深度优先搜索来完成。其搜索的过程是比较简单的。我们添加了edgeTo[]整型数组,这个整型数组会记录从每个顶点回到起点s的路径。如果我们把顶点设定为0,那么它的搜索可以表示为下图:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EhSck804-1629734965774)(images/image67.png)]
    根据最终edgeTo的结果,我们很容易能够找到从起点0到任意顶点的路径;

    /**
     * 无向图--深度优先搜索路径
     */
    public class DepthFirstPaths {
        // 索引代表顶点,值表示当前顶点是否已经被搜索
        private boolean[] marked;
        // 起点
        private int s;
        // 索引代表顶点,值代表深度优先搜索条件下的其上一个顶点
        private int[] edgeTo;
    
        // 构造深度优先搜索对象,使用深度优先搜索找出G图中起点为s的所有路径
        public DepthFirstPaths(Graph G, int s) {
            // 创建一个和图的顶点数一样大小的布尔数组
            this.marked = new boolean[G.V()];
            // 创建一个和图顶点数一样大小的整型数组
            this.edgeTo = new int[G.V()];
            // 初始化顶点
            this.s = s;
            // 搜索G图中起点为s的所有路径
            dfs(G, s);
        }
    
        // 使用深度优先搜索找出G图中v顶点的所有相邻顶点,并为其指定上一个顶点
        private void dfs(Graph G, int v) {
            // 将当前结点标记为true
            marked[v] = true;
            // 遍历v顶点的邻接表,得到每一个顶点w
            for (Integer w : G.adj(v)) {
                // 如果当前顶点w没有被搜索过,则递归搜索与w顶点相通的其他顶点,并指定其上一个顶点
                if (!marked[w]) {
                    // 指定其上一个顶点
                    edgeTo[w] = v;
                    dfs(G, w);
                }
            }
        }
    
        // 判断w顶点与s顶点是否存在路径(也就是是否相通)
        public boolean hasPathTo(int w) {
            return marked[w];
        }
    
        // 找出从起点s到顶点v的路径(就是该路径经过的顶点)
        public Stack<Integer> pathTo(int v) {
            // 如果当前顶点与起点s不连通,直接返回null
            if (!hasPathTo(v)) {
                return null;
            }
            // 定义一个栈,用来记录路径中经过顶点的容器
            Stack<Integer> path = new Stack<>();
            // 将v顶点存进栈中,使用逆推法,从edgeTo中找出上一个顶点存入栈中,直至找到起点s为止
            for (int i = v; i != s; i = edgeTo[i]) {
                // 将当前顶点压进栈中
                path.push(i);
            }
            // 把起点压入栈中
            path.push(s);
            return path;
        }
    }
    
    展开全文
  • 深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历当中所有顶点的两种方式。 深度优先一般是解决连通性问题,而广度优先一般是解决最短路径问题 代码实现 ...
  • 广度优先搜索和深度优先搜索

    千次阅读 2020-06-19 12:09:49
    我们知道,算法是作用于具体数据结构之上的,深度优先搜索算法和广度优先搜索算法都是基于“”这种数据结构的。这是因为,这种数据结构的表达能力很强,大部分涉及搜索的场景都可以抽象成“”。 上的搜索...
  • 深度优先搜索算法框架1)二叉树深度优先搜索模板2)图深度优先搜索模板3)二维矩阵深度优先搜索模板4. 广度优先搜索算法框架1)单源广度优先搜索2)多源广度优先搜索3)双向广度优先搜索 1. 前言     深度优先...
  • 1.深度优先搜索 深度优先搜索,Depth First Search,简称DFS。 对于一个连通,深度优先遍历的过程: 从中一个顶点 vvv 出发并访问 vvv 。 找到刚访问顶点的第一个未被访问的邻接点并访问,并继续以该邻接点...
  • BFS/DFS算法解析【算法入门]2018/6/21.前言和树的遍历类似,的遍历也是从中某点出发,...根据搜索路径的不同,我们可以将遍历的方法分为两种:广度优先搜索和深度优先搜索。2.的基本概念2.1.无向和无向...
  • 的存储结构 一、邻接矩阵 (Adjacency Matrix)表示(数组表示法) 基本思想: 用一个一维数组存储中顶点的信息,用一个二维数组(称为邻接矩阵)存储中各顶点之间的邻接关系。假设G=(V,E)有n个顶点,则邻接...
  • 在无向中,若中任意一对顶点都是连通的,则称此是连通。 在有向中,若任意一对顶点u和v间存在一条从u到v的路径和从v到u的路径,则称此是强连通。 无向的一个极大连通子图称为该的一个连通分量。...
  • 无向的宽度优先搜索算法和深度优先搜索算法,c++实现
  • 适用范围: 无权重的,与深度优先搜索相比,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快 复杂度: 时间复杂度为O(V+E),V为顶点数,E为边数 思路 广度优先搜索是以层为顺序,将某一层...
  • 由两种算法可以对图进行遍历:广度优先搜索(breadth-first search,BFS)和深度优先搜索(depth-first search,DFS)。遍历可以用来寻找特定的顶点或寻找两个顶点之间的路径,检查路径是否相同,检查是否有环,...
  • 8拼图 解决深度优先搜索广度优先搜索,贪婪最佳优先搜索
  • java实现深度优先搜索广度优先搜索 深度优先搜索属于算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次. 宽度优先...
  • 深度优先搜索算法和广度优先搜索算法都是基于“”这种数据结构的。 作为的搜索算法,既可用于有向,也可用于无向,以下均用无向讲解。 广度优先搜索 Breadth-First-Search,BFS。 一种“地毯式”层层推进...
  • 广度优先搜索(BFS)

    2021-01-06 21:53:42
    广度优先搜索(BFS)的数据结构是队列queue。算法思路是用vector来记录每层结点,然后清空当前队列,再将该层队列的下一层加入队列。 算法思路: public class BreadthFirstPaths { private boolean[] marked; // ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 124,582
精华内容 49,832
关键字:

图的广度优先搜索

友情链接: carmanager.rar