深度优先搜索 订阅
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的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] 
收起全文
精华内容
下载资源
问答
  • 深度优先搜索
    千次阅读 多人点赞
    2022-03-11 11:53:46

    图的遍历,

    即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略: (1)深度优先遍历

    (2)广度优先遍历

    图的深度优先搜索(Depth First Search)

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

    1. 深度优先遍历,从初始访问结点出发,初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点, 可以这样理解:每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
    2. 我们可以看到,这样的访问策略是优先往纵向挖掘深入,而不是对一个结点的所有邻接结点进行横向访问。
    3. 显然,深度优先搜索是一个递归的过程

    深度优先遍历算法步骤

    1. 访问初始结点v,并标记结点v为已访问。
    2. 查找结点v的第一个邻接结点w。
    3. 若w存在,则继续执行4,
    4. 如果w不存在,则回到第1步,将从v的下一个结点继续。
    5. 若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)。
    6. 查找结点v的w邻接结点的下一个邻接结点,转到步骤3。

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

    API设计

    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顶点相通

    代码实现

    1、实现图:

    package 基本图;
    
    import 队列.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 < adj.length; i++) {
                adj[i] = new Queue<>();
            }//为邻接表赋值
        }
    
        //获取顶点的数目
        public int v(){
            return v;
        }
    
        //获取边的数目
        public int E(){
            return E;
        }
    
        //向图中添加一条边
        public void addEdge(int v,int w){
            //在无向图中,边是没有方向的,所以该边既可以说是从v到w,也可以是w到v
            adj[v].enqueue(w) ;
            adj[w].enqueue(v) ;
            //边的数量+1
            E++;
        }
    
        //获取和顶点v相邻的所有顶点
        public Queue<Integer> adj(int v){
            return adj[v];
        }//返回邻接表里的值
    }
    

    2、深度优先搜索处理办法

    package 深度优先搜索;
    
    import 基本图.Graph;
    
    public class DepthFirstSearch {
        //索引代表顶点,值表示当前顶底是否已经被搜索过
        private boolean[] marked;
        //记录有多少个顶点与s顶点相通
        private int count;
    
        //构造深度优先搜索对象,使用深度优先搜索找出G图中顶点的所有相邻顶点(找兄弟节点)
        //s为起点5
        public DepthFirstSearch(Graph G, int s){
            //初始化marked数组
            this.marked = new boolean[G.v()];
            //初始化跟顶点s相通的顶点的数量
            this.count = 0;
            dfs(G,s);
        }
    
        //使用深度优先搜索找出G图中v顶点的所有相通的顶点(找子节点)
        private void dfs(Graph G,int v){
            //把v标识为已搜索
            marked[v] = true;
    
            for (Integer w : G.adj(v)) {
                //判断当前w顶点有没有被搜索过,如果没有被搜索过 ,则递归调用dfs方法进行深度搜索
                if(!marked[w]){
                    dfs(G,w);
                }
            }
            //相通顶点的数量+1,找到兄弟节点
            count++;
        }
    
        //判断w顶点与s顶点是否相通
        public boolean marked(int w){
            return marked[w];
        }
    
        //获取与顶点s相通的所有顶点的总数
        public int count(){
            return count;
        }
    }
    

    核心代码

      //使用深度优先搜索找出G图中v顶点的所有相通的顶点(找子节点)
        private void dfs(Graph G,int v){
            //把v标识为已搜索
            marked[v] = true;
    
            for (Integer w : G.adj(v)) {
                //判断当前w顶点有没有被搜索过,如果没有被搜索过 ,则递归调用dfs方法进行深度搜索
                if(!marked[w]){
                    dfs(G,w);
                }
            }
            //相通顶点的数量+1,找到兄弟节点
            count++;
        }

    测试代码(Demo)

    package 深度优先搜索;
    
    import 基本图.Graph;
    
    public class DepthFirstSearchTest {
        public static void main(String[] args) {
            //准备Graph对象
            Graph G = new Graph(13);
            G.addEdge(0,5);
            G.addEdge(0,1);
            G.addEdge(0,2);
            G.addEdge(0,6);
            G.addEdge(5,3);
            G.addEdge(5,4);
            G.addEdge(3,4);
            G.addEdge(4,6);
    
            G.addEdge(7,8);
    
            G.addEdge(9,11);
            G.addEdge(9,10);
            G.addEdge(9,12);
            G.addEdge(11,12);
    
            //准备深度优先搜索对象
            DepthFirstSearch search = new DepthFirstSearch(G,0);
    
            //准备深度优先搜索对象
            int count = search.count();
            System.out.println("与起点0相通的顶点的数量为:" + count);
    
            //测试与某个顶点相通的顶点数量
            boolean marked1 = search.marked(5);
            System.out.println("顶点5和0是否相通:" + marked1);
    
            //测试某个顶点与起点是否相通
            boolean marked2 = search.marked(7);
            System.out.println("顶点7和0是否相通:" + marked2);
        }
    }
    

    导入的包

    package 队列;
    
    import java.util.Iterator;
    
    public class Queue<T> implements Iterable<T>{
        //记录首结点
        private Node head;
        //记录最后一个结点
        private Node last;
        //记录队列中元素的个数
        private int N;
    
    
        private class Node{
            public T item;
            public Node next;
    
            public Node(T item, Node next) {
                this.item = item;
                this.next = next;
            }
        }
        public Queue() {
            this.head = new Node(null,null);
            this.last=null;
            this.N=0;
        }
    
        //判断队列是否为空
        public boolean isEmpty(){
            return N==0;
        }
    
        //返回队列中元素的个数
        public int size(){
            return N;
        }
    
        //向队列中插入元素t
        public void enqueue(T t){
    
            if (last==null){
                //当前尾结点last为null
                last= new Node(t,null);
                head.next=last;
            }else {
                //当前尾结点last不为null
                Node oldLast = last;
                last = new Node(t, null);
                oldLast.next=last;
            }
    
            //元素个数+1
            N++;
        }
    
        //从队列中拿出一个元素
        public T dequeue(){
            if (isEmpty()){
                return null;
            }
    
            Node oldFirst= head.next;
            head.next=oldFirst.next;
            N--;
    
            //因为出队列其实是在删除元素,因此如果队列中的元素被删除完了,需要重置last=null;
    
            if (isEmpty()){
                last=null;
            }
            return oldFirst.item;
        }
    
    
        @Override
        public Iterator<T> iterator() {
            return new QIterator();
        }
    
        private class QIterator implements Iterator{
            private Node n;
    
            public QIterator(){
                this.n=head;
            }
            @Override
            public boolean hasNext() {
                return n.next!=null;
            }
    
            @Override
            public Object next() {
                n = n.next;
                return n.item;
            }
        }
    
    
    }
    
    

    更多相关内容
  • 本文实例讲述了图的遍历中深度优先搜索的C++实现方法,是一种非常重要的算法,具体实现方法如下: 首先,图的遍历是指从图中的某一个顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。...
  • 代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码...
  • 本文实例讲述了C语言使用深度优先搜索算法解决迷宫问题。分享给大家供大家参考,具体如下: 深度优先搜索 伪代码 (Pseudocode)如下: 将起点标记为已走过并压栈; while (栈非空) { 从栈顶弹出一个点p; if (p这个...
  • MATLAB源码集锦-基于深度优先搜索算法图论代码
  • 深度优先搜索与回溯算法 回溯是计算机解题中常用的算法,很多问题无法根据某种 确定的计算法则来求解,可以利用搜索与回溯的技术求解回溯 是搜索算法中的一种控制策略它的基本思想是:为了求得问题 的解,先选择某一种...
  • 8拼图 解决深度优先搜索,广度优先搜索,贪婪最佳优先搜索
  • 主要介绍了Python数据结构与算法之图的广度优先与深度优先搜索算法,结合实例形式分析了图的广度优先与深度优先搜索算法原理与相关实现技巧,需要的朋友可以参考下
  • Depth-First-Search)的缩写。深度优先(DFS)就是“不撞南墙不回头”.深度优先是用递归实现的,广度优先用的是迭代。
  • 这篇文章主要介绍了python 递归深度优先搜索与广度优先搜索算法模拟实现 ,非常不错,具有一定的参考借鉴价值,需要的朋友可以参考下 一、递归原理小案例分析 (1)# 概述 递归:即一个函数调用了自身,即实现了递归 ...
  • 人工只能作业,利用python实现深度优先搜索解决八数码问题,测试通过,
  • 深度优先搜索的实现原理: 实现代码: <?php class Search_Method { //无向图的数组描述 private $dfs_save; //全局记录数组 private $arr; //控制分支- private $k = 0; public function __construct()...
  • 深度优先搜索

    2014-07-30 15:03:01
    深度优先搜索算法,ACM培训教程,c/c+
  • 马踏棋盘问题(骑士巡游问题)的基于贪心算法优化深度搜索可视化实现 用c语言实现的,在命令台中会动态的显示棋盘上棋子路径
  • 基于python的深度优先搜索算法DFS设计与实现
  • 数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历 数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历.rar
  • 蓝桥杯深度优先搜索

    2019-01-23 12:00:19
    整合了几道蓝桥杯近几年的算法题,希望对大家熟悉了解这个算法有帮助
  • 广度优先搜索和深度优先搜索

    千次阅读 2021-11-22 09:59:27
    深度优先搜索算法框架1)二叉树深度优先搜索模板2)图深度优先搜索模板3)二维矩阵深度优先搜索模板4. 广度优先搜索算法框架1)单源广度优先搜索2)多源广度优先搜索3)双向广度优先搜索 1. 前言     深度优先...


    1. 前言

        深度优先搜索算法的基础是递归,如果你对递归还不熟悉的话,建议先去看看递归的概念,做一些递归的练习题,也可以看我之前写的递归的文章:递归算法详解


    2. 广度优先搜索和深度优先搜索

         在这篇文章中同时总结下广度优先搜索和深度优先搜索,这两种算法是针对 “图” 的遍历方法,当然这里的图是指的是广义上的图,可以是实际的图,可以是N叉树,甚至可以是二维矩阵。其中深度优先搜索是每一次按照一个方向进行穷尽式的搜索,当该方向上的搜索无法继续往前的时候,这时就退回到上一步,换一个方向继续搜索而广度优先走是按照层次由近及远的进行搜索,在当前层次所有可及节点都搜索完毕后才会继续往下搜索,其本质就是寻找从起点到终点的最短路径。下面以二叉树的遍历过程说明两种搜索算法之间的区别:

    1)深度优先搜索

        这种搜索方法会按照一个方向进行穷尽搜索,所以首先会一直搜索左子树,直到某个节点没有左子树为止,接着换个方向搜索右子树,图示如下:
    在这里插入图片描述

    2)广度优先搜索

        与深度搜索不同的是这种搜索的方式总是按照层次进行的,当前层所以节点都访问过后才会继续往下,图示如下:
    在这里插入图片描述


    3. 深度优先搜索算法框架

    void DFS(当前节点){
        对当前节点的访问;`在这里插入代码片`
        标记当前节点为已访问;
        for(下一节点 : 当前节点的邻接列表){
            剪枝(如果下一节点已经访问过就跳过);
            DFS(下一节点);
        }
    }
    

    1)二叉树深度优先搜索模板

    //二叉树前序DFS搜索
    void DFS(TreeNode* root){
        if(root == nullptr) return;
        cout << root->val << " "; //输出当前节点
        //这里不需要标记当前节点为已访问,因为二叉树不会往回走
        DFS(root->lchild); 
        DFS(root->rchild); 
    }
    

    调整输出节点的位置,还能得出另外两种二叉树DFS遍历:

    //二叉树中序DFS搜索
    void DFS(TreeNode* root){
        if(root == nullptr) return;
        DFS(root->lchild);
        cout << root->val << " "; //输出当前节点
        DFS(root->rchild);
    }
    
    //二叉树后序DFS搜索
    void DFS(TreeNode* root){
        if(root == nullptr) return;
        DFS(root->lchild);
        DFS(root->rchild);
        cout << root->val << " "; //输出当前节点
    }
    

    2)图深度优先搜索模板

    vector<int> visited; //用来标记已访问节点
    void DFS(Graph *G, int v){
        cout << v << " "; //输出当前节点
        visited[v] = 1; //标记当前节点为已访问
        for(int w = 0; w < G->vexnum; w++){
            if(!visited[w])
               DFS(G, w);
        }
    }
    

    3)二维矩阵深度优先搜索模板

    int m = matrix.size(); //行数
    int n = matrix[0].size();  //列数
    vector<vector<int>> visited(m, vector<int>(n, 0)); //用来标记已经访问过的节点
    int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //行进方向
    
    
    void DFS(vector<vector<int>> &matrix, int x, int y){
        if(matrix[x][y] == target)
            return;
        visited[x][y] = 1; //标记当前节点为已访问
        
        for(int i = 0; i < 4; i++){
            int new_x = x + directions[i][0];
            int new_y = y + directions[i][1];
            	//这里一定要把visites[new_x][new_y]放在最后,因为计算后的new_x和new_y值有可能已经超过visited的下标访问范围
            	if(new_x < 0 || new_x >= m || new_y < 0 || new_y >= n || visited[new_x][new_y]) continue; 
                	DFS(matrix, new_x, new_y);
        }
    }
    

    4. 广度优先搜索算法框架

        首先需要明确的就是,广度优先搜索是按照层次遍历的,所以广度优先搜索不能像深度优先搜索一样使用递归来实现,广度优先搜索需要申请辅助队列来记录下一层需要遍历的节点

    1)单源广度优先搜索

        从一个起点出发到一个终点结束

    //单源的广度优先搜索
    int BFS(elemType start, elemType target) {
        queue<elemType> q; //申请辅助队列
        set<elemType> visited; //标记已访问过的,避免走回头路
        q.push(start); //起点入队列
        visited.insert(start); //标记起点
        int step = 0; //记录步数
        while (!q.empty()) {
            int sz = q.size(); //每一层的元素个数
            for (int i = 0; i < sz; i++) {
                elemType cur = q.pop(); //获得队列中的元素
                if (cur == target) { //判断是否需要结束搜索
                    return step;
                }
                for (elemType x : cur.neighbor()) { //确定下一层需要搜索的节点
                    if (visited.find(x) == visited.end()) {
                        q.push(x);
                        visited.insert(x);
                    }
                }
            }
            step++; // 步数加一
        }
    }
    

    2)多源广度优先搜索

        顾名思义,多源广度优先搜索的意思是可以从多个起点开始向外进行搜索,是一种扩散式的搜索方法,如下图所示,图中值为0的点表示起点,则与每个0上下左右相邻的节点值就为1,同样与每个1上下左右相邻的节点值就为2。
    在这里插入图片描述

    vector<vector<int>> mulBFS(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> dist(m, vector<int>(n, 0)); //记录每个位置上的步数
        vector<vector<int>> visited(m, vector<int>(n, 0)); //用来标记是否访问过
        queue<pair<int, int>> q;
        //第一步就是将多个源点按顺序入队列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    q.push(pair<int, int>(i, j));
                    visited[i][j] = 1;
                }
            }
        }
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                auto [x, y] = q.front();
                q.pop();
                for (int j = 0; j < 4; j++) {
                    int new_x = x + directions[j][0];
                    int new_y = y + directions[j][1];
                    if (new_x < 0 || new_x >= m || new_y < 0 || new_y >= n ||  visited[new_x][new_y]) continue;
                    q.push(pair<int, int>(new_x, new_y));
                    visited[new_x][new_y] = 1;
                    dist[new_x][new_y] = dist[x][y] + 1;
                }
            }
        }
    }
    

    [注]:上述的两种广度优先搜索中我们给出了两个记录步长的方式,第一种是设置一个step,然后每向前一步就step++,这种比较适合单源的广度优先搜索;第二种是设置一个辅助dist数组,记录所有节点的距离,然后通过 dist[newNode] = dist[oldNode]+1 进行更新,这种比较适合多源的广度优先搜索。

    3)双向广度优先搜索

        广度优先搜索是求图中最短路径的方法,一般是从某个起点出发,一直穷举直到碰到某个结束值(也就是目标值),这样的搜索过程就是单向的搜索,而有的题目即会提供起点位置,也会提供终点的位置,这样的题目可以采用双向的广度优先搜索, 当发现某一时刻两边都访问过同一顶点时就停止搜索。比如下面这个题目:
        LeetCode 127. 单词接龙:在本题目中起始单词 beginword 和 结束单词 endword均已经给出,因此可以采用双向的广度优先搜索。
    双向广度优先搜索算法流程:
        1. 需要定义两个辅助队列,一个放前向搜索时的节点,一个存放逆向搜索时的节点
        2. 查看两个辅助队列中是否有相同的元素,以判断搜索是否结束
        3. 轮流进行搜索,也就是前向搜索进行一次后紧跟着就要做一次逆向搜索

    int BFS(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (wordSet.find(endWord) == wordSet.end()) return 0;
        unordered_set<string> q_start, q_end, visited; //双向搜索要定义两个set作为辅助队列
        q_start.insert(beginWord);
        q_end.insert(endWord);
        int step = 1;
        while (!q_start.empty() && !q_start.empty()) {
            unordered_set<string> temp; //定义一个temp为了将q_start将q_end交换
            for (string cur : q_start) {
                cout << cur << " ";
                if (q_end.find(cur) != q_end.end()) return step; //查看两个队列中是否有相同的元素,相同则结束遍历
                //这一步很关键,单向BFS中是在新节点入队的同时加入访问数组,这里不行,因为我们结束查找的条件就是两个队
                //列中是否有相同的条件,如果在新节点入队的同时加入访问数组,两个队列中就一定不会有相同的元素,因此要在判断后加
                visited.insert(cur); 
                for (int k = 0; k < cur.size(); k++) {
                    string newWord = cur;
                    for (int i = 0; i < 26; i++) {
                        newWord[k] = i + 'a';
                        if (wordSet.find(newWord) != wordSet.end() &&  visited.find(newWord) == visited.end()) {
                            temp.insert(newWord);
                        }
                    }
                }
            }
            step++;
            //交换搜索的方向
            q_start = q_end; 
            q_end = temp;
        }
        return 0;
    }
    
    展开全文
  • NULL 博文链接:https://128kj.iteye.com/blog/1663043
  • 深度优先搜索(DFS)与广度优先搜索(BFS)详解 1.广度优先搜索算法 1.1.前言 和树的遍历类似,图的遍历也是从图中某点出发,然后按照某种方法对图中所有顶点进行访问,且仅访问一次。 但是图的遍历相对树而言要更为...

    深度优先搜索(DFS)与广度优先搜索(BFS)详解

    1.广度优先搜索算法

    1.1.前言

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

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

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

    1.2.图及图的遍历

    概念

    线性表和树两类数据结构,线性表中的元素是“一对一”的关系,树中的元素是“一对多”的关系,本章所述的图结构中的元素则是“多对多”的关系。图(Graph)是一种复杂的非线性结构,在图结构中,每个元素都可以有零个或多个前驱,也可以有零个或多个后继,也就是说,元素之间的关系是任意的。

    图的遍历

    图的遍历是指从图中的某一顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。

    1.3.定义

    广度优先搜索算法类似于二叉树的层序遍历,是一种分层的查找过程,每向前一步可能访问一批顶点,没有回退的情况,因此不是一个递归的算法。首先访问起始顶点v,接着由v出发,依存访问v的各个未访问过的邻接顶点w1,w2,…,wi,然后依次访问w1,w2,…,wi的所有未被访问过的邻接顶点;再从这些访问过的顶点出发,访问它们所有未被访问过的邻接顶点······依次类推,直到图中所有顶点都被访问过为止

    1.4.算法图解

    在这里插入图片描述

    思路详解:

    1. 以节点1为起始顶点,开始访问
    2. 接着由v开始出发,依次次访问v的各个未访问过的邻接顶点 w 1 , w 2 , . . . , w i w1,w2,...,wi w1,w2,...,wi
    3. 然后依次访问 w 1 , w 2 , . . . , w i w1,w2,...,wi w1,w2,...,wi的所有未被访问的邻接顶点;
    4. 然后再从这些访问过的顶点出发,访问它们所有未被访问过的邻接顶点
    5. 直到所有顶点都被访问过为止;
    6. 如果此时图中尚有顶点未被访问,则另选图中一个未被访问过的顶点作为起始点,重复上述过程,直到图中所有顶点都被访问为止;

    广度优先搜索算法类似于二叉树的层序遍历,是一种分层的查找过程,每向前一步可能访问一批顶点,没有回退的情况,因此不是一个递归的算法。

    性能分析:

    空间复杂度:

    无论是邻接表还是邻接矩阵的存储方式,BFS算法都需要借助一个辅助队列Q,n个顶点均需入队一次,在最坏的情况下,空间复杂度为 O ( ∣ V ∣ ) O(|V|) O(V)

    时间复杂度:

    • 邻接表:采用邻接表存储方式时,每个顶点均需搜索一次(或入队一次),故时间复杂度为 O ( ∣ V ∣ ) O(|V|) O(V),在搜索任意顶点的邻接点事每条边至少访问一次,故时间复杂度为 O ( ∣ E ∣ ) O(|E|) O(E),算法的总时间复杂度为 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(V+E)
    • 邻接矩阵:采用邻接矩阵存储方式时,查找每个顶点的邻接点所需的时间为 O ( ∣ V ∣ ) O(|V|) O(V),故算法总的时间复杂度为 O ( ∣ V 2 ∣ ) O(|V^2|) O(V2)

    1.5.代码实现:

    使用广度优先搜索遍历下图:

    在这里插入图片描述

    /**
     * @ClassName BFS
     * @Author Fenglin Cai
     * @Date 2021 09 30 19
     * @Description 图的广度优先搜索算法
     **/
    import com.sun.istack.internal.NotNull;
    
    import java.util.*;
    //如同二叉树的层次遍历
    public class BFS {
    
        public static class Node implements Comparable<Node> {
    
            private String name;
    
            private TreeSet<Node> set = new TreeSet<>();//有序的集合
    
            public Node() {
            }
    
            public Node(String name) {
                this.name = name;
            }
    
            public String getName() {
                return name;
            }
    
            public void setName(String name) {
                this.name = name;
            }
    
            public Set<Node> getSet() {
                return set;
            }
    
            public void setSet(TreeSet<Node> set) {
                this.set = set;
            }
    
            @Override
            public int compareTo(@NotNull Node o) {//排序规则
                if(name.hashCode()>o.getName().hashCode()) {
                    return 1;
                }
                return 0;
            }
        }
    
        public Node init() {//初始化一个图及其节点
            Node nodeA = new Node("A");
            Node nodeB = new Node("B");
            Node nodeC = new Node("C");
            Node nodeD = new Node("D");
            Node nodeE = new Node("E");
            Node nodeF = new Node("F");
            Node nodeG = new Node("G");
            Node nodeH = new Node("H");
            nodeA.getSet().add(nodeB);
            nodeA.getSet().add(nodeC);
            nodeB.getSet().add(nodeD);
            nodeB.getSet().add(nodeE);
            nodeC.getSet().add(nodeF);
            nodeC.getSet().add(nodeG);
            nodeD.getSet().add(nodeH);
            nodeE.getSet().add(nodeH);
            return nodeA;
        }
    
        public void visite(Node node) {//访问每个节点
    
            System.out.print(node.getName()+" ");
    
        }
    
        public void bfs(Node start) {
            Queue<Node> queue = new LinkedList<>();//存储访问的节点
    
            Queue<Node> visite = new LinkedList<>();//存储访问过得节点
    
            queue.add(start);//起始节点添加到队列
    
            visite.add(start);//标识为访问过
            while (!queue.isEmpty()) {
    
                Node node = queue.poll();//队列头结点出队
    
                visite(node);
    
                Set<Node> set = node.getSet();//获取所有的直接关联的节点
    
                Iterator<Node> iterator = set.iterator();
    
                while(iterator.hasNext()) {
    
                    Node next = iterator.next();
    
                    if (!visite.contains(next)) {//不包含说明没有没有被访问
    
                        queue.add(next);
    
                        visite.add(next);
                    }
    
                }
            }
        }
    
        public static void main(String[] args) {
    
            BFS bfs = new BFS();
    
            bfs.bfs(bfs.init());
        }
    }
    

    2.深度优先搜索算法

    2.1.定义

    与广度优先搜索不同,深度优先搜索(Depth-First-Search,DFS)类似于树的先序遍历。

    思想从一个顶点V0开始,沿着一条路一直走到底,如果发现不能到达目标解,那就返回到上一个节点,然后从另一条路开始走到底,直到所有顶点被全部走完,这种尽量往深处走的概念即是深度优先的概念。

    实例:

    在这里插入图片描述

    假设按照以下的顺序来搜索:

    1.V0->V1->V4,此时到底尽头,仍然到不了V6,于是原路返回到V1去搜索其他路径;

    2.返回到V1后既搜索V2,于是搜索路径是V0->V1->V2->V6,,找到目标节点,返回有解。

    这样就搜索到了目标节点,当然这里在可以选择多个节点时,随意选择任一节点,如果走到V1节点选择V3的话,走的路径就是

    V0->V1->V3->V5->V6->V2。

    2.2.算法图解

    思路图解:

    思路如下所示:

    图1:

    根据深度优先搜索算法的思想,且在一个节点访问下一个节点有多个选择时选最小的规则下,路径就如图中给出所示,

    1. 从起始点节点1开始走,走过的路径:1->2->3->4->5
    2. 在走到第5个节点时因为节点2已经走过,所以无路可走了,然后回退到节点4,再走节点6,路径:1->2->3->4->5->4->6
    3. 到节点7时同样无路可走,回退到上一节点并继续走,路径:1->2->3->4->5->4->6->7->6->8->9

    图2:

    1. 按照图2所给的规则来,从起始节点1开始走1->4->6->5->3
    2. 到节点3时因为节点1和节点6都已经走过,所以无路可走,回退到上一节点5,继续走1->4->6->5->3->5->2,

    这样就遍历完了,搜索时,只需加个条件判断即可,满足条件直接跳出搜索。

    有向图转换为最小生成树

    在这里插入图片描述

    性能分析:

    空间复杂度:

    DFS算法是一个递归算法,需要借助一个递归工作栈,故其空闲复杂度为 O ( ∣ V ∣ ) O(|V|) O(V).

    时间复杂度:

    遍历图的过程实质上是对每个顶点查找其邻接点的过程,其耗费的时间取决于所用的存储结构。

    • 邻接矩阵:查找每个顶点的邻接点所需的时间为 O ( ∣ V ∣ ) O(|V|) O(V),故总的时间复杂度为 O ( ∣ V ∣ 2 ) O(|V|^2) O(V2)
    • 邻接表:查找所有顶点的邻接点所需的时间为 O ( ∣ E ∣ ) O(|E|) O(E),访问顶点所需的时间为 O ( ∣ V ∣ ) O(|V|) O(V),此时,总的时间复杂度为 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(V+E)

    2.3.代码实现

    题目描述

    在这里插入图片描述

    题目:图1是一个城堡的地形图。请你编写一个程序,计算城堡一共有多少房间(相通的所有方块为一个房间),最大的房间有多大。城堡被分割成m*n(m≤50,r≤50)个方块,每个方块可以有0~4面墙。
    输入

    程序从标准输入设备读入数据。第一行是两个整数,分别是南北向、东西向的方块数。在接下来的输入行里,每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙,1表示西墙,2表示北墙,4表示东墙,8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次,方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。

    输出

    城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。

    样例输入

    4
    7
    11 6 11 6 3 10 6
    7 9 6 13 5 15 5
    1 10 12 7 13 7 5
    13 11 10 8 10 12 13

    样例输出

    5 9

    思路:
    要想找到一个房间,就要遍历与这个房间相关联的每一个方块,假如方块1与方块2相同,方块2与方块3、方块4相同,方块1、2、3、4构成一份房间,那我们就要遍历每一个方块以求出房间大小。在遍历的时候还要标记当前方块,以便当前方块再次被遍历。

    代码实现

    如下:

    #include<iostream>
    #include<algorithm>
    using namespace std;
     
    int R, C;  //行数和列数
    int color[60][60];   //用来标记当前房间是否访问过
    int room[60][60];
    int maxRoomArea = 0;   //用来记录面积最大的房间
    int roomNumber = 0;    //房间数量
    int roomArea;      //用来记录房间的面积
     
    void dfs(int i, int k)
    {
    	if (color[i][k])
    	{
    		return;
    	}
    	roomArea++;    //房间的面积
    	color[i][k] = roomNumber; //标记当前结点,防止再次遍历该节点
     
    	//选择与当前结点相关联的另一个节点,继续dfs
    	if ((room[i][k] & 1) == 0)dfs(i, k - 1);    //向西
    	
    	if ((room[i][k] & 2) == 0)dfs(i - 1, k);    //向北
    	
    	if ((room[i][k] & 4) == 0)dfs(i, k + 1);    //向东
    	
    	if ((room[i][k] & 8) == 0)dfs(i + 1, k);    //向南
    	
    }
     
    int main()
    {
    	cin >> R >> C;
    	for (int i = 1; i <= R; i++) {
    		for (int j = 1; j <= C; j++) {
    			cin >> room[i][j];
    		}
    	}
    	memset(color, 0, sizeof(color));   //初始化
    	for (int i = 1; i <= R; i++) {
    		for (int j = 1; j <= C; j++) {
    			if (!color[i][j]) {    //当 当前结点没有被遍历过时
    				roomArea = 0;
    				roomNumber++;
    				dfs(i, j);
    				maxRoomArea = max(roomArea, maxRoomArea);
    			}
    		}
    	}
    	cout << roomNumber << endl;
    	cout << maxRoomArea << endl;
     
    	system("pause");
    	return 0;
    }
    

    3.深搜与广搜的比较

    3.1.深度优先搜索的特点

    1. 无论问题的内容和性质以及求解要求如何不同,它们的程序结构都是相同的,即都是深度优先算法(一)和深度优先算法(二)中描述的算法结构,不相同的仅仅是存储结点数据结构和产生规则以及输出要求。
    2. 深度优先搜索法有递归以及非递归两种设计方法。一般的,当搜索深度较小、问题递归方式比较明显时,用递归方法设计好,它可以使得程序结构更简捷易懂。当搜索深度较大时,当数据量较大时,由于系统堆栈容量的限制,递归容易产生溢出,用非递归方法设计比较好。
    3. 深度优先搜索方法有广义和狭义两种理解。广义的理解是,只要最新产生的结点(即深度最大的结点)先进行扩展的方法,就称为深度优先搜索方法。在这种理解情况下,深度优先搜索算法有全部保留和不全部保留产生的结点的两种情况。而狭义的理解是,仅仅只保留全部产生结点的算法。本书取前一种广义的理解。不保留全部结点的算法属于一般的回溯算法范畴。保留全部结点的算法,实际上是在数据库中产生一个结点之间的搜索树,因此也属于图搜索算法的范畴。
    4. 不保留全部结点的深度优先搜索法,由于把扩展望的结点从数据库中弹出删除,这样,一般在数据库中存储的结点数就是深度值,因此它占用的空间较少,所以,当搜索树的结点较多,用其他方法易产生内存溢出时,深度优先搜索不失为一种有效的算法。
    5. 从输出结果可看出,深度优先搜索找到的第一个解并不一定是最优解。

    如果要求出最优解的话,一种方法将是后面要介绍的动态规划法,另一种方法是修改原算法:把原输出过程的地方改为记录过程,即记录达到当前目标的路径和相应的路程值,并与前面已记录的值进行比较,保留其中最优的,等全部搜索完成后,才把保留的最优解输出。

    3.2.广度优先搜索法的特点

    1. 在产生新的子结点时,深度越小的结点越先得到扩展,即先产生它的子结点。为使算法便于实现,存放结点的数据库一般用队列的结构。
    2. 无论问题性质如何不同,利用广度优先搜索法解题的基本算法是相同的,但数据库中每一结点内容,产生式规则,根据不同的问题,有不同的内容和结构,就是同一问题也可以有不同的表示方法。
    3. 当结点到跟结点的费用(有的书称为耗散值)和结点的深度成正比时,特别是当每一结点到根结点的费用等于深度时,用广度优先法得到的解是最优解,但如果不成正比,则得到的解不一定是最优解。这一类问题要求出最优解,一种方法是使用后面要介绍的其他方法求解,另外一种方法是改进前面深度(或广度)优先搜索算法:找到一个目标后,不是立即退出,而是记录下目标结点的路径和费用,如果有多个目标结点,就加以比较,留下较优的结点。把所有可能的路径都搜索完后,才输出记录的最优路径。
    4. 广度优先搜索算法,一般需要存储产生的所有结点,占的存储空间要比深度优先大得多,因此程序设计中,必须考虑溢出和节省内存空间得问题。
    5. 比较深度优先和广度优先两种搜索法,广度优先搜索法一般无回溯操作,即入栈和出栈的操作,所以运行速度比深度优先搜索算法法要快些。

    总之,一般情况下,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快,在距离和深度成正比的情况下能较快地求出最优解。因此在选择用哪种算法时,要综合考虑。决定取舍。

    3.3.优缺点比较

    广搜优缺点

    优点

    • 对于解决最短或最少问题特别有效,而且寻找深度小
    • 每个结点只访问一遍,结点总是以最短路径被访问,所以第二次路径确定不会比第一次短

    缺点

    • 内存耗费量大(需要开大量的数组单元用来存储状态)

    使用场景:计算网络数据链路层的最短跳数,走迷宫的最短路径

    深搜优缺点

    优点

    • 能找出所有解决方案
    • 优先搜索一棵子树,然后是另一棵,所以和广搜对比,有着内存需要相对较少的优点

    缺点

    • 要多次遍历,搜索所有可能路径,标识做了之后还要取消。
    • 在深度很大的情况下效率不高

    Reference

    https://blog.csdn.net/qq_41738049/article/details/94338715

    https://blog.csdn.net/weixin_44341938/article/details/102250450

    展开全文
  • 并行DFS 图数据结构深度优先搜索的并行算法
  • C#深度优先搜索算法

    2020-12-31 04:14:31
    本文实例为大家分享了C#深度优先搜索算法的具体代码,供大家参考,具体内容如下 //论文要用到其改进算法,在此先demo测试一下 using System; using System.Collections.Generic; using System.Linq; using System....
  • 针对电网故障事件等级判定需要自动识别电力故障元器件的问题,文中提出了一种基于深度优先搜索算法的电力系统拓扑建模方法。首先根据电气元件端子数建立了各元器件的数据表;然后根据各端子连接情况,构建配电网拓扑...
  • 深度优先搜索例程:迷宫最短路径
  • 是非常有用的程序, 深度优先搜索可用于电网潮流,能运行,可在此基础上修改!
  • 第七章:深度优先搜索

    千次阅读 2022-02-13 15:46:38
    不撞南墙不回头-深度优先搜索 广度优先搜索BFS是每次将当前状态能够一步拓展出的所有状态,全部拓展出来依次存入队列。而深度优先搜索是将当前状态按照一定的规则顺序,先拓展一步得到一个新状态,再对这个这个新...

    不撞南墙不回头-深度优先搜索

    广度优先搜索BFS是每次将当前状态能够一步拓展出的所有状态,全部拓展出来依次存入队列。而深度优先搜索是将当前状态按照一定的规则顺序,先拓展一步得到一个新状态,再对这个这个新状态递归拓展下去。如果无法拓展,则退回一步到上一步的状态,再按照原先设定的规则顺序重新寻找一个状态拓展。如此搜索,直到找到目标状态,或者遍历完所有的状态。

    深度优先搜索

    深度优先搜索(Depth First Search,DFS),简称 深搜 ,其状态“退后一步”的顺序符合“后进先出”的特点,所以采用“栈”存储状态。深搜的空间复杂度较小,因为它只存储了初始状态到当前状态的一条搜索路径。但是,深搜找到的第一个解不一定是最优解,要找最优解必须搜索整棵“搜索树”。所以,深搜适用于要求所有解方案的题目。

    相信通过上面的描述,同学们还是对深度优先搜索一头雾水。下面我们结合一个例子,和大家一起探索下什么是深度优先搜索。深度优先搜索可以这样想,一个人迷路了,遇到很多分叉路口,他只有一个人,并且想走出去,所以他只能一个个路线的去尝试, 一条道路走到黑,发现到头了,然后再退回去走刚才这条路的其他分叉路口,最后发现这条路的所有分叉路口走完了,选择另外一条路继续以上操作,直到所有的路都走过了。

    而广度优先并不是这样,一个人迷路了,但是他有特异技能(就好比火影里面鸣人的影分身一样), 他遇到分叉路口,不是选一个走,而是分身多个人每个路口都去试试 ,比如有A、B、C三个分叉路口,A路走一步,紧接着B路也走一步,然后C路也赶紧走一步,步伐整齐统一,直到所有的路走过了。

    深度优先搜索的步骤

    深度优先搜索的步骤分为 1.递归下去 2.回溯上来。顾名思义,深度优先,则是以深度为准则,先一条路走到底,直到达到目标,这里称之为递归下去。否则既没有达到目标又无路可走了,那么则退回到上一步的状态,走其他路,这便是回溯上来。下面结合具体例子来理解。如图所示,在一个迷宫中,黑色块代表玩家所在位置,红色块代表终点,问是否有一条到终点的路径。

    我们用深度优先搜索的方法去解这道题,由图可知,我们可以走上下左右四个方向,我们规定按照 左下右上 的方向顺序走(逆时针方向),即如果左边可以走,我们先走左边。然后递归下去,没达到终点,我们再回溯上来,等又回溯到这个位置时,左边已经走过了,那么我们就走下边,按照这样的顺序与方向走。并且我们把走过的路标记一下代表走过,不能再走。所以我们从黑色起点首先向左走,然后发现还可以向左走,最后我们到达图示位置。

    已经连续向左走到左上角的位置了,这时发现左边不能走了,这时我们就考虑往下走,发现也不能走,同理,上边也不能走, 右边已经走过了也不能走,这时候无路可走了 ,代表这条路是死路不能帮我们解决问题, 所以现在要回溯上去,回溯到上一个位置。

    在这个位置我们由上可知走左边是死路不行,上下是墙壁不能走,而右边又是走过的路,已经被标记过了,不能走。所以只能再度回溯到上一个位置寻找别的出路。

    最终我们回溯到最初的位置,同理,左边证明是死路不必走了,上和右是墙壁, 所以我们走下边 。然后递归下去

    到了这个格子,因为按照左下右上的顺序,我们走左边,递归下去

    一直递归下去到最左边的格子,然后左边行不通,走下边,一直往下走,正好可以找到目标位置。

    广度优先搜索较之深度优先搜索之不同在于,深度优先搜索旨在不管有多少条岔路, 先一条路走到底,不成功就返回上一个路口然后就选择下一条岔路 ,而广度优先搜索旨在面临一个路口时,把所有的岔路口都记下来,然后选择其中一个进入,然后将它的分路情况记录下来,然后再返回来进入另外一个岔路,并重复这样的操作,用图形来表示则是这样的,例子同上。

    从黑色起点出发,记录所有的岔路口,并标记为走一步可以到达的。然后选择其中一个方向走进去,我们走黑点方块上面的那个,然后将这个路口可走的方向记录下来并标记为2,意味走两步可以到达的地方。

    接下来,我们回到黑色方块右手边的1方块上,并将它能走的方向也记录下来,同样标记为2,因为也是走两步便可到达的地方

    这样走一步以及走两步可以到达的地方都搜索完毕了,下面同理,我们可以迅速把三步的格子给标记出来

    再之后是四步,五步。

    我们便成功寻找到了路径,并且把所有可行的路径都求出来了。

    广度优先搜索和深度优先搜索的比较

    在广度优先搜索中,可以看出是逐步求解的,反复的进入与退出,将当前的所有可行解都记录下来,然后逐个去查看。 在DFS中我们说关键点是递归以及回溯,在BFS中,关键点则是状态的选取和标记。

    对于这两个搜索方法,其实我们是可以轻松的看出来,他们有许多差异与许多相同点的。

    1.数据结构上的运用

    DFS用递归的形式,用到了  结构,先进后出。

    BFS选取状态用 队列 的形式,先进先出。

    2.复杂度

    DFS的复杂度与BFS的复杂度大体一致,不同之处在于遍历的方式与对于问题的解决出发点不同,DFS适合目标明确,而BFS适合大范围的寻找。

    3.思想

    思想上来说这两种方法都是穷竭列举所有的情况。

    我相信很多同学看完上面的内容对深度优先搜索还不是很熟悉。下面我们通过几个例子带同学们更深入的了解什么是深度优先搜索。

    案例1:扑克牌游戏

    假如有编号为1、2、3的3张扑克牌和编号为1、2、3的3个盒子。现在需要将这3张扑克牌分别放到3个盒子里面,并且每个盒子有且只能放一张扑克牌。那么一共有多少种不同的放法呢?

    聪明的拓拓觉得这个题目很简答,于是他决定试一试。拓拓手拿 3张扑克牌,首先走到了1号盒子面前。此时拓拓心里想∶我是先放1号扑克牌,还是先放2号扑克牌,还是先放3号扑克牌呢?很显然这三种情况都需要去尝试,拓拓说那我们约定一个顺序吧∶每次到一个盒子面前时,都先放1号,再放2号,最后放3号扑克牌。说完拓拓走到了1号盒子前,将 1号扑克牌放到第1个盒子中。

    放好之后拓拓往后走一步,来到了2号盒子面前。本来按照之前约定的规则,每到一个新的盒子面前,要按照1号、2号、3号扑克牌的顺序来放。但是现在拓拓手中只剩下2号和3号扑克牌了,于是拓拓将2号扑克牌放入了2号盒子中。放好之后拓拓再往后走一步,来到了3号盒子面前。

    现在拓拓已经来到了3号盒子面前,按照之前约定的顺序,还是应该按照1号、2号、3号扑克牌的顺序来放,但是拓拓手中只有3号扑克牌了,于是只能往 3号盒子里面放3号扑克牌。放好后,拓拓再往后走一步,来到了4号盒子面前。咦!没有第4个盒子,其实我们并不需要第 4个盒子,因为手中的扑克牌已经放完了。我们发现当拓拓走到第4个盒子的时候,已经完成了一种排列,这个排列就是前面3个盒子中的扑克牌号码,即"123"。

    是不是游戏到此就结束了呢?肯定没有!产生了一种排列之后拓拓需要立即返回。现在拓拓需要退一步重新回到 3 号盒子面前。好!现在拓拓已经回到了3号盒子面前,需要取回之前放在3号盒子中的扑克牌,再去尝试看看还能否放别的扑克牌,从而产生一个新的排列。

    于是拓拓取回了3号扑克牌。当拓拓再想往3号盒子放别的扑克牌的时候,却发现手中仍然只有3号扑克牌,没有别的选择。于是拓拓不得不再往回退一步,回到2 号盒子面前。拓拓回到2号盒子后,收回了2号扑克牌。现在拓拓手里面有两张扑克牌了,分别是2号和3号扑克牌。按照之前约定的顺序,现在需要往2号盒子中放3号扑克牌(上一次放的是2号扑克牌)。放好之后拓拓又向后走一步,再次来到了3号盒子面前。拓拓再次来到3号盒子后,将手中仅剩的2号扑克牌放入了3号盒子。又来到4号盒子面前。当然了,这里并没有4号盒子。此时又产生了一个新的排列“132”。

    接下来按照刚才的步骤去模拟,便会依次生成所有排列∶"213""231""312"和"321"。

    说了半天,这么复杂的过程如何用程序实现呢?我们现在来解决最基本的问题∶如何往小盒子中放扑克牌。每一个小盒子都可能放1号、2号或者3号扑克牌,这需要一一去尝试,这里一个 for循环就可以解决。

    for(i=1;i<=n;i++)
    {
        a[step]=i;  //将第i号扑克牌放入第step个盒子中 
    } 
    

    Copy

    这里数组 a是用来表示小盒子的,变量 step 表示当前正处在第 step 个小盒子面前。 a[step]=i; 就是将第i号扑克牌放入到第step个盒子中。这里有一个问题那就是,如果一张扑克牌已经放到别的小盒子中了,那么此时就不能再放入同样的扑克牌到当前小盒子中,因为此时手中已经没有这张扑克牌了。因此还需要一个数组 book来标记哪些牌已经使用了。

    for(i=1;i<=n;i++)
    {
        if(book[i]==0)
        { 
            a[step]=i;  //将第i号扑克牌放入第step个盒子中
            book[i]=1;  //将book[i]设为1,表示滴i号牌已经不在手中了
        } 
    } 
    

    Copy

    OK,现在已经处理完第 step个小盒子了,接下来需要往下走一步,继续处理第 step+1个小盒子。那么如何处理第 step+1个小盒子呢?处理方法其实和我们刚刚处理第 step个小盒子的方法是相同的。因此就很容易想到(如果这个词伤害了您,我表示深深的歉意^^)把刚才的处理第 step 个小盒子的代码封装为一个函数,我们为这个函数起个名字,就叫做dfs 吧,如下。

    void dfs(int step)  //step表示现在站在第几个盒子面前
    {
        for(i=1;i<=n;i++)
        {
            //判断扑克牌i是否还在手上 
            if(book[i]==0)  //将book[i]等于0表示扑克牌仍然在手上 
            { 
                a[step]=i;  //将第i号扑克牌放入第step个盒子中
                book[i]=1;  //将book[i]设为1,表示滴i号牌已经不在手中了
            } 
        }
    } 
    

    Copy

    把这个过程写成函数后,刚才的问题就好办了。在处理完第 step个小盒子之后,紧接着处理第 step+1个小盒子,处理第step+1和小盒子的方法就是 dfs(step+1),请注意下面代码中第11行语句。

    void dfs(int step)  //step表示现在站在第几个盒子面前
    {
        for(i=1;i<=n;i++)
        {
            //判断扑克牌i是否还在手上 
            if(book[i]==0)  //将book[i]等于0表示扑克牌仍然在手上 
            { 
                a[step]=i;  //将第i号扑克牌放入第step个盒子中
                book[i]=1;  //将book[i]设为1,表示滴i号牌已经不在手中了
                dfs(step+1);  //这里通过函数的递归用来实现 
                book[i]=0;   //这是非常重要的一步,一定要将刚才尝试的扑克牌收回,才能进行下一次尝试 
            } 
        }
    } 
    

    Copy

    上面代码中的book[i]=0;这条语句非常重要,这句话的作用是将小盒子中的扑克牌收回,因为在一次摆放尝试结束返回的时候,如果不把刚才放入小盒子中的扑克牌收回,那将无法再进行下一次摆放。还剩下一个问题,就是什么时候该输出一个满足要求的序列呢。其实当我们处理到第 n+1个小盒子的时候(即 step等于n+1),那么说明前n个盒子都已经放好扑克牌了,这里就将 1-n个小盒子中的扑克牌编号打印出来就可以了,如下。注意!打印完毕一定要立即 return,不然这个程序就会永无止境地运行下去了,想一想为什么吧。

    完整的代码如下所示:

    #include<bits/stdc++.h>
    using namespace std;
    int a[10],book[10],n;
    void dfs(int step)  //step表示现在站在第几个盒子面前
    {
        int i;
        if(step==n+1)  //如果站在第n+1个盒子面前,则表示前n个盒子已经放在扑克牌 
        {
            //输出一种排列(1-n号盒子中的扑克牌编号)
            for(i=1;i<=n;i++)
            {
                cout<<a[i]<<" "; 
            } 
            cout<<endl;
            return;  //返回之前一步(最近一次调用dfs函数的地方) 
        } 
        //此时站在第step个盒子前,应该放哪张牌呢?
        //按照1、2、3...n的顺序一一尝试 
        for(i=1;i<=n;i++)
        {
            //判断扑克牌i是否还在手上 
            if(book[i]==0)  //将book[i]等于0表示扑克牌仍然在手上 
            { 
                //开始尝试使用扑克牌i 
                a[step]=i;  //将第i号扑克牌放入第step个盒子中
                book[i]=1;  //将book[i]设为1,表示滴i号牌已经不在手中了
                //第step个盒子已经放好扑克牌,接下来需要走到下一个盒子面前 
                dfs(step+1);  //这里通过函数的递归用来实现 
                book[i]=0;   //这是非常重要的一步,一定要将刚才尝试的扑克牌收回,才能进行下一次尝试 
            } 
        }
    }
    int main()
    {
        cin>>n;
        dfs(1);  //首先站在1号盒子前面
        return 0;
    } 
    

    Copy

    这个简单的例子,核心代码不超过20行,却饱含深度优先搜索(DepthFirst Search,DFS)的基本模型。理解深度优先搜索的关键在于解决当下该如何做。至于下一步如何做则与当下该如何做是一样的。比如我们这里写的dfs(step)函数的主要功能就是解决当你在第 step个盒子的时候你该怎么办。通常的方法就是把每一种可能都去尝试一遍(一般使用 for 循环来遍历)。当前这一步解决后便进入下一步dfs(step+1)。下一步的解决方法和当前这步的解决方法是完全一样的。下面的代码就是深度优先搜索的基本模型。

    void dfs(int step)
    {
        判断边界
        尝试每一种可能 for(i=1;i<=n;i++)
        {
            继续下一步 dfs(step+1); 
        } 
        返回 
    }
    

    Copy

    案例2:解救小拓

    有一天,小拓一个人去玩迷宫。但是方向感很不好的小拓很快就迷路了。小哼得知后便立即去解救无助的小拓。小哼当然是有备而来,已经弄清楚了迷宫的地图,现在小哼要以最快的速度去解救小拓。问题就此开始了……

    迷宫由n行m列的单元格组成(n和m都小于等于50),每个单元格要么是空地,要么是障碍物。你的任务是帮助小哼找到一条从迷宫的起点通往小拓所在位置的最短路径。注意障碍物是不能走的,当然小哼也不能走到迷宫之外。

    首先我们可以用一个二维数组来存储这个迷宫,刚开始的时候,小哼处于迷宫的入口处(1,1),小拓在(p,q)。其实,就是找从(1,1)到(p,q)的最短路径。如果你是小哼,你该怎么办呢?小哼最开始在(1,1),他只能往右走或者往下走,但是小哼是应该往右走呢还是往下走呢。此时要是能有两个小哼就好了,一个向右走,另外一个向下走。但是现在只有一个小哼,所以只能一个一个地去尝试。我们可以先让小哼往右边走,直到走不通的时候再回到这里,再去尝试另外一个方向。我们这里规定一个顺序,按照顺时针的方向来尝试(即按照右、下、左、上的顺序去尝试)。

    我们先来看看小哼一步之内可以达到的点有哪些?只有(1,2)和(2,1)。根据刚才的策略,我们先往右边走,小哼来到了(1,2)这个点。来到(1,2)之后小哼又能到达哪些新的点呢?只有(2,2)这个点。因为(1,3)是障碍物无法达到,(1,1)是刚才来的路径中已经走过的点,也不能走,所以只能到(2,2)这个点。但是小拓并不在(2,2)这个点上,所以小哼还得继续往下走,直至无路可走或者找到小拓为止。请注意!此处并不是一找到小拓就结束了。因为刚才只尝试了一条路,而这条路并不一定是最短的。刚才很多地方在选择方向的时候都有多种选择,因此我们需要返回到这些地方继续尝试往别的方向走,直到把所有可能都尝试一遍,最后输出最短的一条路径。例如下图就是一种可行的搜索路径。

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

    void dfs(int x,int y,int step)
    {
        return ;
    }
    

    Copy

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

    void dfs(int x,int y,int step)
    {
        //判断是否到达小拓的位置
        if(x==p && y==q)
        {
            //更新最小值
            if(step<min)
            {
                min=step;
             } 
             return ;  //请注意这里返回很重要 
         } 
        return ;
    }
    

    Copy

    如果没有到达小拓的位置,则找出下一步可以走的地方。因为有四个方向可以走,根据我们之前的约定,按照顺时针的方向来尝试(即按照右、下、左、上的顺序尝试)。这里为了编程方便,我定义了一个方向数组 next,如下。

    int next[4][2]={{0,1},   //向右走 
                    {1,0},   //向下走 
                    {0,-1},   //向左走 
                    {-1,0}};  //向上走 
    

    Copy

    通过这个方向数组,使用循环就很容易获得下一步的坐标。这里将下一步的横坐标用 tx存储,纵坐标用 ty 存储。

    for(k=0;k<=3;k++)
    {
        //计算的下一个点坐标
        tx=x+next[k][0];
        ty=y+next[k][1]; 
    } 
    

    Copy

    接下来我们就要对下一个点(x,ty)进行一些判断。包括是否越界,是否为障碍物,以及这个点是否已经在路径中(即避免重复访问一个点)。需要用book[tx][ty]来记录格子(tx,ty)是否已经在路径中。如果这个点符合所有的要求,就对这个点进行下一步的扩展,即 dfs(tx,ty,step+1),注意这里是 step+1,因为一旦你从这个点开始继续往下尝试,就意味着你的步数已经增加了1。

    完整的代码实现如下:

    #include<bits/stdc++.h>
    using namespace std;
    int n,m,p,q,mmin=999999;
    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<mmin)
            {
                mmin=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;
        cin>>n>>m;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                cin>>a[i][j];   //读入迷宫 
            }
        }
        cin>>startx>>starty>>p>>q;  //读入开始和结束坐标
        //从起点开始搜索
        book[startx][starty]=1;  //标记该点已经在路径中,反正后面重复走
        //第一个参数是起点的x的坐标,第二个参数是起点的y坐标,第三个参数是初始步数为0
        dfs(startx,starty,0); 
        //输出最短步数
        cout<<mmin;
        return 0; 
    } 
    

    Copy

    可以输入以下数据进行验证。第一行有两个数n和m。n表示迷宫的行,m表示迷宫的列。接下来的n行m列为迷宫,0表示空地,1表示障碍物。最后一行 4个数,前两个数为迷宫入口的x和y坐标。后两个为小拓的x和y坐标。运行结果是7。

    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
    

    Copy

    经典例题讲解:

    例题1:全排列问题(主题库2696)

    输出自然数 1\sim n1∼n 所有不重复的排列,即 nn 的全排列,要求所产生的任一数字序列中不允许出现重复数字。

    输入格式:一行,一个整数 nn。

    输出格式:输出由 1\sim n1∼n 组成的所有不重复的数字序列。每行一个序列,行内数字之间用空格隔开。

    样例输入:

    3
    

    Copy

    样例输出:

    1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 1 2
    3 2 1
    

    Copy

    数据范围:

    对于 100% 的测试数据满足:1≤n≤91≤n≤9。

    解题思路:看到这个题目,如果你还有一丝丝的疑惑就表示你对上面的第一个案例还没有弄明白,所谓的全排列的问题跟案例一扑克牌游戏其实是完全一样的题目。如果你直接把案例一的代码递交上去,会发现是可以直接ac的。

    完整的代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    int a[10],book[10],n;
    void dfs(int step)  //step表示现在站在第几个盒子面前
    {
        int i;
        if(step==n+1)  //如果站在第n+1个盒子面前,则表示前n个盒子已经放在扑克牌 
        {
            //输出一种排列(1-n号盒子中的扑克牌编号)
            for(i=1;i<=n;i++)
            {
                cout<<a[i]<<" "; 
            } 
            cout<<endl;
            return;  //返回之前一步(最近一次调用dfs函数的地方) 
        } 
        //此时站在第step个盒子前,应该放哪张牌呢?
        //按照1、2、3...n的顺序一一尝试 
        for(i=1;i<=n;i++)
        {
            //判断扑克牌i是否还在手上 
            if(book[i]==0)  //将book[i]等于0表示扑克牌仍然在手上 
            { 
                //开始尝试使用扑克牌i 
                a[step]=i;  //将第i号扑克牌放入第step个盒子中
                book[i]=1;  //将book[i]设为1,表示滴i号牌已经不在手中了
                //第step个盒子已经放好扑克牌,接下来需要走到下一个盒子面前 
                dfs(step+1);  //这里通过函数的递归用来实现 
                book[i]=0;   //这是非常重要的一步,一定要将刚才尝试的扑克牌收回,才能进行下一次尝试 
            } 
        }
    }
    int main()
    {
        cin>>n;
        dfs(1);  //首先站在1号盒子前面
        return 0;
    } 
    

    Copy

    例题2:素数环(主题库1348)

    如图所示为一个由 n个圆圈构成的圆环。将自然数 1,2,...,n放入圆圈内,并且要求任意两个相邻的圆圈内的数字之和为素数。请问给你圆圈数,你能给出放置自然数的所有正确方案吗?

    注意:圆圈中的数字一定是从1开始的,并且连续不重复。

    输入格式:n(1<=n<=17)。

    输出格式:把1放在第一位置,按照字典顺序不重复的输出所有解(顺时针,逆时针算不同的两种),相邻两数之间严格用一个整数隔开,每一行的末尾不能有多余的空格。 如果没有答案请输出"no answer"。

    样例输入:

    8
    

    Copy

    样例输出:

    1 2 3 8 5 6 7 4 
    1 2 5 8 3 4 7 6 
    1 4 7 6 5 8 3 2 
    1 6 7 4 3 8 5 2
    

    Copy

    解题思路:仔细分析本道题,其实会发现跟全排列的题目有相似的地方,同样是n个不同的数字,只是本道题目里面的数字需要满足任意两个相邻的圆圈内的数字之和为素数。根据题意,把1放在第一位置,因此第一位一定是1,所以我们可以从第2个数开始搜索,同时把1标记为用过use[1]=1;。接下来我们开始写dfs()函数,用cur表示当前搜索到第几个数,如果当前这个数大于n,则搜索结束,搜索结束就可以输出一种可能性,这里需要特别注意的是还需要判断一下最后一个数跟第一个数字1的和是不是也是素数,这一点特别容易忽视。接下来开始写循环语句,从第2个数循环到第n个数,限制条件很简单,包括两个,一个是这个点没有用过即use[i]==0;另一个是这个点跟上一个点之和为素数,即prime(i+a[cur-1])==1(你也可以用素数筛来判断素数)。如果i满足限制条件就可以把i存在a[cur]里面,同时把i标记为1,即use[i]=1;这个数搞定了,紧接着,我们就可以开始搜索下一个数了,下一个数完全跟上一个数的搜索方法一样,因此可以直接调用dfs()函数,即dfs(cur+1);接下来就是最重要的一步,将i再标记成0。

    完整代码如下所示:

    #include<bits/stdc++.h>
    using namespace std;
    int a[20],use[20];
    int n, ans=0;
    bool prime(int x){    //素数判断 
        for(int i=2;i<=sqrt(x);i++)
        {
            if(x%i==0) return 0;
        }
        return 1;
    }
    void print(){  //输出 
        for(int i=1;i<=n;i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    void dfs(int cur){   //cur表示当前是第几个数 
        if(cur>n){     //如果大于n,即n个数都输入环中,结束 
            if(prime(a[1]+a[n])==1){  //结束的时候,还需要判断第n个数跟第一个数之和是不是素数 
                ans++;
                print();   //如果成立,则输出这种排法 
                return;
            }
        }
        for(int i=2;i<=n;i++) //从第2个数开始搜索 
        {
            if(use[i]==0&&prime(i+a[cur-1])==1)  //这个点没有搜过并且这个点跟上个点加起来是素数 
            {
                a[cur]=i;   //i保存在当前位置 
                use[i]=1;   //这个数字搜过了,标记为1 
                dfs(cur+1);  //开始搜下一个数 
                use[i]=0;   //回溯,这个点又标记为0 
            }
        }
    }
    int main()
    {
        cin>>n;
        a[1]=1;   
        use[1]=1;  //1一开始就被搜了,容易忽视 
        dfs(2); //从2开始搜索
        if(ans==0) cout<<"no answer";
        return 0; 
    }
    

    Copy

    例题3:马走日(主题库2678)

    马在中国象棋以日字形规则移动。

    请编写一段程序,给定n×m大小的棋盘,以及马的初始位置(x,y),要求不能重复经过棋盘上的同一个点,计算马可以有多少途径遍历棋盘上的所有点。

    输入格式:第一行为整数T(T < 10),表示测试数据组数。

    每一组测试数据包含一行,为四个整数,分别为棋盘的大小以及初始位置坐标n,m,x,y。(0≤x≤n-1,0≤y≤m-1, m < 10, n < 10)。

    输出格式:每组测试数据包含一行,为一个整数,表示马能遍历棋盘的途径总数,0为无法遍历一次。

    样例输入:

    1
    5 4 0 0
    

    Copy

    样例输出:

    32
    

    Copy

    解题思路:类似于马走日这种题目,我们很明显想到用搜索的方法。题目里面问的是马能遍历棋盘的途径总数,所谓遍历棋盘就是马移动的步数是不是正好等于棋盘的大小。即搜索的结束条件为num==n*m。由于是多组测试数组,因此千万别忘记了清理,这里使用了memset(f,0,sizeof(f));进行清零。首先从起始点开始搜索,因此起始点标记为1。马移动有八个方向即dir[8][2]={{2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2},{-2,1},{-2,-1}}。对于每个点还需要判断是否越界,这里用一个check函数检测是否超过棋盘的界限。dfs()函数里面包含3个参数,分别是起始点的位置和点的数目。如果点数正好等于棋盘的格数则方法的数目加1,如果不是从八个方向开始搜索,搜索的限制条件同样为两个是否越界,以及这个点未走过。如果满足条件,则该点标记为1,开始搜索下一个点,同时清空。

    完整的代码如下所示:

    #include<bits/stdc++.h>
    using namespace std;
    const int dir[8][2]={{2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2},{-2,1},{-2,-1}}; //马可以走的八个方向 
    int t,n,m,x,y,ans=0;
    bool f[15][15];  //标记每个点是否走过 
    bool check(int x,int y){  //检测是否超过棋盘的界限 
        if(x>=0&&x<n&&y>=0&&y<m){
            return 1;
        }
        else 
            return 0;    
    } 
    void dfs(int x,int y,int num){  //xy表示马所在的位置,num表示点的数目 
        if(num==n*m){  //当数目等于棋盘数表示成立 
            ans++;  
            return;
        }
        else{
            for(int i=0;i<8;i++)  //不够的话开始搜索 
            {
                int dx=x+dir[i][0];  //横坐标的值为二维数组dir的00,10,20,30... 
                int dy=y+dir[i][1];  //纵坐标的值为二维数组dir的00,01,02,03... 
                if(check(dx,dy)==1&&f[dx][dy]==0){  //如果这个点没有越界并且这个点还没有走过 
                    f[dx][dy]=1;   //这个点走过了,标记 
                    dfs(dx,dy,num+1);  //开始搜索下一个点 
                    f[dx][dy]=0;   //清空标记 
                }
            }
        }
    }
    int main()
    {
        cin>>t;
        while(t--)
        {
            ans=0;
            memset(f,0,sizeof(f));  //多组输入的清零 
            cin>>n>>m>>x>>y;
            f[x][y]=1;  //开始位置肯定为1 
            dfs(x,y,1);  //从第一个点开始搜索 
            cout<<ans<<endl;
        } 
        return 0;
    }
    

    Copy

    展开全文
  • 深度优先搜索(DFS)与广度优先搜索(BFS)详解

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 112,199
精华内容 44,879
关键字:

深度优先搜索