精华内容
下载资源
问答
  • 一文带你了解dfs和bfs算法
    2022-01-21 22:11:43

    一文带你了解dfs和bfs算法

    寻路算法 00_00_00-00_00_30.gif

    如上图,dfs和bfs算法通常会用来解决迷宫问题,两种算法都可以找到一条通往重点的路,但又有不一样的地方。

    体验地址:http://120.79.163.94/demo/寻路算法.html

    可以自己定义迷宫是否可走,及起始点和终点。

    深度优先算法(dfs)

    简介

    dfs算法又称深度优先搜索,是计算机术语。

    1、dfs是一种在开发爬虫早期使用较多的方法,是搜索算法的一种。

    2、dfs的目的是要达到被搜索结构的叶结点,即那些不包含任何超链的HTML文件。

    3、dfs根据已有的邻接矩阵或邻接表用递归方法编写深度优先搜索遍历算法,并输出遍历结果

    作为搜索算法的一种,DFS对于寻找一个解的NP(包括NPC)问题作用很大。但是,搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法,它的效率非常低,在数据规模变大时,这种算法就显得力不从心了。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

    详细解释

    事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.

    图

    举例说明之:上图是一个无向图,如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C,D),则我们可能得到如下的一个访问过程:A->B->E(没有路了!回溯到A)->C->F->H->G->D(没有路,最终回溯到A,A也没有未访问的相邻节点,本次搜索结束).简要说明深度优先搜索的特点:每次深度优先搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.如果将每个节点在深度优先搜索过程中的"结束时间"排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下,将该节点加入list结尾,然后逆转整个链表),则我们可以得到所谓的"拓扑排序",即topological sort. [1]

    基本思路

    深度优先遍历图的方法是,从图中某顶点v出发:

    (1)访问顶点v;

    (2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;

    (3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。 当然,当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法,那就是广度优先搜索(BFS).

    实际应用

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

    代码

    function dfs(x, y) {
        const dx = [1, 0, -1, 0],
              dy = [0, 1, 0, -1];
        if (x < 0 || y < 0 || x >= map.length || y >= map[0].length) return;
        if (map[x][y] == 1 || flag[x][y] || findFlag) return;
        startCell.classList.add("now-in");
        if (x == targetX && y == targetY) {
            findFlag = true;
            canFind = true;
            return;
        }
        for (let i = 0; i < 4 && !findFlag; i++) {
            flag[x][y] = true;
            count++;
            if (!findFlag) dfs(x + dx[i], y + dy[i]);
            if (!findFlag) flag[x][y] = false;
            if (!findFlag) startCell.innerHTML = "";
            if (!findFlag) count--;
            if (!findFlag) startCell.classList.remove("pass");
        }
    }
    

    如上代码,我设置了算法遍历的方向为(这个可以自己规定),遍历过程类似于堆栈的过程不断试探,不符合则出栈回退,遍历的过程中需要防止走回头路,因此需要标记已经遍历过的坐标,这里我使用了flag来进行标记。

    const dx = [1, 0, -1, 0],
        dy = [0, 1, 0, -1];
    //即依次为上、右、下、左进行遍历,走不通则回溯
    

    广度优先算法(bfs)

    简介

    宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。

    BFS,其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点,所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里,其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中(例如队列或是链表),而被检验过的节点则被放置在被称为 closed 的容器中。(open-closed表)

    详细解释

    已知图G=(V,E)和一个源顶点s,宽度优先搜索以一种系统的方式探寻G的边,从而“发现”s所能到达的所有顶点,并计算s到所有这些顶点的距离(最少边数),该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。对从s可达的任意顶点v,宽度优先树中从s到v的路径对应于图G中从s到v的最短路径,即包含最小边数的路径。该算法对有向图无向图同样适用。

    之所以称之为宽度优先算法,是因为算法自始至终一直通过已找到和未找到顶点之间的边界向外扩展,就是说,算法首先搜索和s距离为k的所有顶点,然后再去搜索和S距离为k+l的其他顶点。

    为了保持搜索的轨迹,宽度优先搜索为每个顶点着色:白色、灰色或黑色。算法开始前所有顶点都是白色,随着搜索的进行,各顶点会逐渐变成灰色,然后成为黑色。在搜索中第一次碰到一顶点时,我们说该顶点被发现,此时该顶点变为非白色顶点。因此,灰色和黑色顶点都已被发现,但是,宽度优先搜索算法对它们加以区分以保证搜索以宽度优先的方式执行。若(u,v)∈E且顶点u为黑色,那么顶点v要么是灰色,要么是黑色,就是说,所有和黑色顶点邻接的顶点都已被发现。灰色顶点可以与一些白色顶点相邻接,它们代表着已找到和未找到顶点之间的边界。

    在宽度优先搜索过程中建立了一棵宽度优先树,起始时只包含根节点,即源顶点s.在扫描已发现顶点u的邻接表的过程中每发现一个白色顶点v,该顶点v及边(u,v)就被添加到树中。在宽度优先树中,我们称结点u 是结点v的先辈或父母结点。因为一个结点至多只能被发现一次,因此它最多只能有–个父母结点。相对根结点来说祖先和后裔关系的定义和通常一样:如果u处于树中从根s到结点v的路径中,那么u称为v的祖先,v是u的后裔。

    实际应用

    BFS在求解最短路径或者最短步数上有很多的应用,应用最多的是在走迷宫上。

    代码

    function bfs() {
          let quene = [[startX, startY]];
          step[startX][startY] = 0;
          let res = [];
          flag[startX][startY] = true;
          while (quene.length) {
            let p = quene.shift();
            res.push(p);
            let x = p[0],
              y = p[1];
            if (x == targetX && y == targetY) break;
            let f = false;
            for (let i = 0; i < 4; i++) {
              let nx = x + dx[i],
                ny = y + dy[i];
              if (nx < 0 || nx >= map.length || ny >= map[0].length || ny < 0) {
                continue;
              }
              if (map[nx][ny] == 1 || flag[nx][ny] == true) {
                continue;
              }
              flag[nx][ny] = true;
              step[nx][ny] = step[x][y] + 1;
              quene.push([nx, ny]);
              if (nx == targetX && ny == targetY) {
                f = true;
                canFind = true;
                break;
              }
            }
            if (f) break;
          }
        }
    

    如上代码,bfs使用的是队列数据结构来进行解决,每走一步便将这一步周边的有效坐标入队,优先判断了最近的路径,因此bfs得出的答案总是最短的路径,遍历的过程中还需要防止走回头路,因此需要标记已经遍历过的坐标,这里我使用了flag来进行标记,step记录的则是走到每一个位置的最短路径。

    对比

    dfs

    深度优先搜索用栈(stack)来实现,整个过程可以想象成一个倒立的树形:

    1、把根节点压入栈中。

    2、每次从栈中弹出一个元素,搜索所有在它下一级的元素,把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。

    3、找到所要找的元素时结束程序。

    4、如果遍历整个树还没有找到,结束程序。

    bfs

    广度优先搜索使用队列(queue)来实现,整个过程也可以看做一个倒立的树形:

    1、把根节点放到队列的末尾。

    2、每次从队列的头部取出一个元素,查看这个元素所有的下一级元素,把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。

    3、找到所要找的元素时结束程序。

    4、如果遍历整个树还没有找到,结束程序。

    html完整代码

    <html>
      <head>
        <title>寻路算法</title>
      </head>
      <body>
        <div class="body">
          <div class="body-content1">
            <div class="dfs-title">寻路算法</div>
            <div id="dfs-content" class="dfs-cell"></div>
            <div id="btn-list">
              <div id="btn-start-dfs" class="btn-start">dfs</div>
              <div id="btn-start-bfs" class="btn-start">bfs</div>
              <div id="btn-reset">重置</div>
            </div>
          </div>
          <div class="body-content2">
            <div class="dfs-title">.</div>
            <div class="start-point point">
              开始坐标:
              <input id="start-point-x" type="number" placeholder="" />
              <input id="start-point-y" type="number" placeholder="" />
            </div>
            <div class="target-point point">
              终点坐标:
              <input id="target-point-x" type="number" placeholder="" />
              <input id="target-point-y" type="number" placeholder="" />
            </div>
          </div>
        </div>
      </body>
      <script>
        let count = 0; //步数计数
        //迷宫地图
        let map = [
          [0, 0, 1, 0, 0, 0, 0, 0],
          [0, 0, 0, 0, 1, 0, 0, 0],
          [1, 0, 0, 0, 0, 1, 0, 0],
          [0, 0, 0, 0, 1, 0, 1, 0],
          [1, 0, 0, 0, 1, 0, 0, 0],
          [0, 0, 1, 0, 1, 0, 0, 0],
          [0, 1, 0, 0, 1, 1, 0, 1],
          [0, 0, 1, 1, 1, 0, 0, 0],
          [0, 0, 1, 0, 0, 0, 0, 0],
          [0, 0, 0, 0, 1, 0, 0, 0],
          [1, 0, 0, 0, 0, 1, 0, 0],
          [0, 0, 0, 0, 1, 0, 1, 0],
          [1, 0, 0, 0, 1, 0, 0, 0],
          [0, 0, 1, 0, 1, 0, 0, 0],
          [0, 1, 0, 0, 1, 1, 0, 1],
          [0, 0, 1, 1, 1, 0, 0, 0],
        ];
        let cellSize = 20; //px单元格大小
        let startX = 0, //开始坐标
          startY = 0;
        let targetX = 15, //结束坐标
          targetY = 7;
        let canFind = false;
    
        //遍历方向
        let dx = [0, 1, 0, -1],
          dy = [1, 0, -1, 0];
    
        let flag = new Array(map.length); //dfs标记走过的路径
        for (let i = 0; i < flag.length; i++) {
          flag[i] = new Array(map[i].length).fill(false);
        }
        //能否到达
        let findFlag = false;
    
        let step = new Array(map.length); //bfs标记走过的路径
        for (let i = 0; i < step.length; i++) {
          step[i] = new Array(map[i].length).fill(Infinity);
        }
        //单元格点击事件
        function cellClick(e) {
          let wFlag = 0;
          let classList = [...e.classList];
          if (classList.includes("now-in")) return;
          if (classList.includes("wall")) {
            e.classList.remove("wall");
            e.classList.add("space");
          } else if (classList.includes("space")) {
            e.classList.remove("space");
            e.classList.add("wall");
            wFlag = 1;
          }
          let id = e.id.split("-");
          let x = id[2],
            y = id[3];
          map[x][y] = wFlag;
          // console.log(map[x][y], x, y);
        }
        //初始化页面
        function init() {
          initPage();
          initData();
        }
        function initData() {
          const startPointX = document.getElementById("start-point-x");
          const startPointY = document.getElementById("start-point-y");
          const targetPointX = document.getElementById("target-point-x");
          const targetPointY = document.getElementById("target-point-y");
          startPointX.value = startX;
          startPointY.value = startY;
          targetPointX.value = targetX;
          targetPointY.value = targetY;
    
          startPointX.addEventListener("change", (e) => {
            if (
              e.target.value < 0 ||
              e.target.value >= map.length ||
              map[e.target.value][startY] == 1
            ) {
              alert("非法坐标,请重新输入");
              startPointX.value = startX;
              return;
            }
            startX = parseInt(e.target.value);
            initPage();
          });
          startPointY.addEventListener("change", (e) => {
            if (
              e.target.value < 0 ||
              e.target.value >= map[0].length ||
              map[startX][e.target.value] == 1
            ) {
              alert("非法坐标,请重新输入");
              startPointY.value = startY;
              return;
            }
            startY = parseInt(e.target.value);
            initPage();
          });
          targetPointX.addEventListener("change", (e) => {
            if (
              e.target.value < 0 ||
              e.target.value >= map.length ||
              map[e.target.value][targetY] == 1
            ) {
              alert("非法坐标,请重新输入");
              targetPointX.value = targetX;
              return;
            }
            targetX = parseInt(e.target.value);
            initPage();
          });
          targetPointY.addEventListener("change", (e) => {
            if (
              e.target.value < 0 ||
              e.target.value >= map[0].length ||
              map[targetX][e.target.value] == 1
            ) {
              alert("非法坐标,请重新输入");
              targetPointY.value = targetY;
              return;
            }
            targetY = parseInt(e.target.value);
            initPage();
          });
        }
        function initPage() {
          let innerHtml = ``;
          count = 0;
          findFlag = false;
          for (let i = 0; i < map.length; i++) {
            for (let j = 0; j < map[i].length; j++) {
              flag[i][j] = false;
              innerHtml += `<div id="${"dfs-id-" + i + "-" + j}" class="${
                map[i][j] == 0 ? "space" : "wall"
              } cell" style="width:${cellSize}px;height:${cellSize}px;" click="cellClick"></div>`;
            }
          }
          let dfsContent = document.getElementById("dfs-content");
          dfsContent.style.width = map[0].length * (cellSize + 2) + "px";
          dfsContent.innerHTML = innerHtml;
    
          let startCell = document.getElementById(
            "dfs-id-" + startX + "-" + startY
          );
          startCell.classList.add("now-in");
    
          let targetCell = document.getElementById(
            "dfs-id-" + targetX + "-" + targetY
          );
          targetCell.classList.add("target-in");
          let cell = document.getElementsByClassName("cell");
          for (let i = 0; i < cell.length; i++) {
            cell[i].addEventListener("click", () => {
              cellClick(cell[i]);
            });
          }
        }
        function dfs(x, y) {
          const dx = [1, 0, -1, 0],
            dy = [0, 1, 0, -1];
          if (x < 0 || y < 0 || x >= map.length || y >= map[0].length) return;
          if (map[x][y] == 1 || flag[x][y] || findFlag) return;
          let startCell = document.getElementById("dfs-id-" + x + "-" + y);
          startCell.classList.add("now-in");
          if (x == targetX && y == targetY) {
            findFlag = true;
            startCell.innerHTML = `<div style="font-size:small;text-align: center;">${count}</div>`;
            canFind = true;
            return;
          }
          for (let i = 0; i < 4 && !findFlag; i++) {
            flag[x][y] = true;
            startCell.innerHTML = `<div style="font-size:small;text-align: center;">${count}</div>`;
            count++;
            startCell.classList.add("pass");
            startCell.classList.remove("now-in");
    
            if (!findFlag) dfs(x + dx[i], y + dy[i]);
            if (!findFlag) flag[x][y] = false;
            if (!findFlag) startCell.innerHTML = "";
            if (!findFlag) count--;
            if (!findFlag) startCell.classList.remove("pass");
          }
        }
    
        function bfs() {
          let quene = [[startX, startY]];
          step[startX][startY] = 0;
          // console.log("开始bfs");
          let res = [];
          flag[startX][startY] = true;
          while (quene.length) {
            let p = quene.shift();
            res.push(p);
            let x = p[0],
              y = p[1];
            if (x == targetX && y == targetY) break;
            let f = false;
            for (let i = 0; i < 4; i++) {
              let nx = x + dx[i],
                ny = y + dy[i];
              if (nx < 0 || nx >= map.length || ny >= map[0].length || ny < 0) {
                continue;
              }
              if (map[nx][ny] == 1 || flag[nx][ny] == true) {
                continue;
              }
              flag[nx][ny] = true;
              step[nx][ny] = step[x][y] + 1;
              quene.push([nx, ny]);
              if (nx == targetX && ny == targetY) {
                f = true;
                canFind = true;
                break;
              }
            }
            if (f) break;
          }
          if (canFind) bfsDrawRoad();
        }
        //绘制路线
        function bfsDrawRoad() {
          let road = [[targetX, targetY]];
          while (road[0][0] != startX || road[0][1] != startY) {
            let x = road[0][0],
              y = road[0][1];
            for (let i = 0; i < 4; i++) {
              let nx = x + dx[i],
                ny = y + dy[i];
              if (nx < 0 || ny < 0 || nx >= step.length || ny >= step[0].length)
                continue;
              if (step[x][y] == step[nx][ny] + 1) {
                road.unshift([nx, ny]);
                break;
              }
            }
          }
          for (let i = 0; i < road.length; i++) {
            let startCell = document.getElementById(
              "dfs-id-" + road[i][0] + "-" + road[i][1]
            );
            if (i != road.length - 1) {
              startCell.classList.add("pass");
            } else {
              startCell.classList.add("now-in");
            }
    
            startCell.innerHTML = `<div style="font-size:small;text-align: center;">${i}</div>`;
          }
        }
        //页面初始化
        init();
        //开始dfs
        let startBtnDfs = document.getElementById("btn-start-dfs");
        startBtnDfs.addEventListener("click", () => {
          canFind = false;
          init();
          dfs(startX, startY);
          // console.log(canFind);
          if (!canFind) alert("无法达到");
        });
        //开始bfs
        let startBtnBfs = document.getElementById("btn-start-bfs");
        startBtnBfs.addEventListener("click", () => {
          canFind = false;
          init();
          bfs();
          // console.log(canFind);
          if (!canFind) alert("无法达到");
        });
        //重置页面
        let resetBtn = document.getElementById("btn-reset");
        resetBtn.addEventListener("click", () => {
          init();
        });
      </script>
      <style>
        .body {
          display: flex;
          margin: auto;
        }
        .body-content1 {
          flex: 1;
        }
        .body-content2 {
          flex: 1;
        }
        .point {
          margin-top: 1rem;
        }
        .dfs-cell {
          display: flex;
          flex-wrap: wrap;
          margin: auto;
        }
        .dfs-cell > .cell {
          border: 1px solid gray;
          cursor: pointer;
        }
        .dfs-cell > .wall {
          background-color: black;
        }
        .now-in {
          background-color: yellow;
        }
        .target-in {
          background-color: rgb(245, 162, 9);
        }
        .pass {
          background-color: yellowgreen;
        }
        .dfs-title {
          text-align: center;
          margin: 2rem;
        }
        #btn-list {
          display: flex;
          justify-content: space-between;
          width: 20rem;
          margin: auto;
        }
        .btn-start {
          padding: 1rem;
          margin: auto;
          margin-top: 2rem;
          text-align: center;
          background-color: violet;
          width: 2rem;
          cursor: pointer;
        }
        #btn-reset {
          padding: 1rem;
          margin: auto;
          margin-top: 2rem;
          text-align: center;
          background-color: violet;
          width: 2rem;
          cursor: pointer;
        }
      </style>
    </html>
    
    
    更多相关内容
  • 规格为A4纸或A3纸折叠 佛山科学技术学院用四号宋体 实 验 报 告用小二号黑体 课程名称 数据结构实验 实验项目 实现DFS和BFS算法 专业班级 姓 名 学 号 指导教师 成 绩 日 期 用小四号宋体 一目的与要求 1通过本实验...
  • DFS和BFS算法

    千次阅读 2018-01-05 01:10:19
    DFS和BFS异同比较 本质区别 BFS 的重点在于队列,而 DFS 的重点在于递归。这是它们的本质区别。...BFS算法 是一种利用队列(用队列来保存未访问的结点,先进先出)实现的搜索算法。简单来说...

    DFS和BFS异同比较

    本质区别

    BFS 的重点在于队列,而 DFS 的重点在于递归。这是它们的本质区别。

    DFS 算法
    是一种利用递归(实质上是用栈来保存未访问的结点,先进后出)实现的搜索算法,直到找到解或走不下去为止。简单来说,其搜索过程和 “不撞南墙不回头” 、“树的先序遍历”类似。

    这里写图片描述

    BFS算法
    是一种利用队列(用队列来保存未访问的结点,先进先出)实现的搜索算法。简单来说,其搜索过程和 “湖面丢进一块石头激起层层涟漪” 、“树的层次遍历”类似。

    这里写图片描述

    应用方向的不同

    BFS 常用于找单一的最短路线,它的特点是 “搜到就是最优解”;
    DFS 常用于找所有解的问题,找到的不一定是最优解。

    这里写图片描述
    比如:这道题:求绿点到红点的最短路径。就适合用BFS来做,而DFS虽能做出来但不适合。

    怎么学BFS和DFS?只有一个方法:去做题。

    DFS和BFS的代码框架

    BFS框架

    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<algorithm>
    using namespace std;
    const int maxn=100;
    bool vst[maxn][maxn]; // 访问标记
    int dir[4][2]={0,1,0,-1,1,0,-1,0}; // 方向向量
    
    struct State // BFS 队列中的状态数据结构
    {
        int x,y; // 坐标位置
        int Step_Counter; // 搜索步数统计器
    };
    State a[maxn];
    bool CheckState(State s) // 约束条件检验
    {
        if(!vst[s.x][s.y] && ...) // 满足条件
            return 1;
        else // 约束条件冲突
            return 0;
    }
    
    void bfs(State st)
    {
        queue <State> q; // BFS 队列
        State now,next; // 定义2 个状态,当前和下一个
        st.Step_Counter=0; // 计数器清零
        q.push(st); // 入队
        vst[st.x][st.y]=1; // 访问标记
        while(!q.empty())
        {
            now=q.front(); // 取队首元素进行扩展
            if(now==G) // 出现目标态,此时为Step_Counter 的最小值,可以退出即可
            {
                ...... // 做相关处理
                return;
            }
            for(int i=0;i<4;i++)
            {
                next.x=now.x+dir[i][0]; // 按照规则生成下一个状态
                next.y=now.y+dir[i][1];
                next.Step_Counter=now.Step_Counter+1; // 计数器加1
                if(CheckState(next)) // 如果状态满足约束条件则入队
                {
                    q.push(next);
                    vst[next.x][next.y]=1; //访问标记
                }
            }
            q.pop(); // 队首元素出队。其实前面取了q.front()就可让队首元素出队了。
        }
        return;
    }
    
    int main()
    {
        ......
        return 0;
    }

    DFS框架

    //该DFS 框架以2D 坐标范围为例,来体现DFS 算法的实现思想。
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    using namespace std;
    const int maxn=100;
    bool vst[maxn][maxn]; // 访问标记
    int map[maxn][maxn]; // 坐标范围
    int dir[4][2]={0,1,0,-1,1,0,-1,0}; // 方向向量,(x,y)周围的四个方向
    
    bool CheckEdge(int x,int y) // 边界条件和约束条件的判断
    {
        if(!vst[x][y] && ...) // 满足条件
            return 1;
        else // 与约束条件冲突
            return 0;
    }
    
    void dfs(int x,int y)
    {
        vst[x][y]=1; // 标记该节点被访问过
        if(map[x][y]==G) // 出现目标态G
        {
            ...... // 做相应处理
            return;
        }
        for(int i=0;i<4;i++)
        {
            if(CheckEdge(x+dir[i][0],y+dir[i][1])) // 按照规则生成下一个节点
                dfs(x+dir[i][0],y+dir[i][1]);
        }
        return; // 没有下层搜索节点,回溯
    }
    int main()
    {
        ......
        return 0;
    }

    参考

    BFS和DFS算法原理(通俗易懂版)
    https://blog.csdn.net/u011437229/article/details/53188837

    展开全文
  • java DFSBFS算法

    2022-04-17 13:24:20
    广度优先算法(BFS) BFS算法,它会对树或图进行"逐层"的遍历,也就是层序遍历,相较于DFS算法而言,BFS它不会直接到末尾,而是到下一层之前,会将节点的所有兄弟节点遍历完之后,再进入下一层。 ...

    深度优先遍历(DFS)
    DFS算法,一种用于遍历树或图的算法,它会沿着树的深度遍历树的节点,当访问到不满足条件的时候,就会进行回溯,然后重复执行该操作,直到所有节点都被遍历完;
    在这里插入图片描述
    该图取自于malanlllll
    下列是对二叉搜索树(BSTree)的探究

    //节点类型
    class Node {
        Node left;
        Node right;
        Object data;
        private boolean visited = false;
    
        public void add(Node p) {
            if ((int) p.data < (int) this.data) {
                if (this.left == null) {
                    this.left = p;
                } else
                    this.left.add(p);
            } else {
                if (this.right == null)
                    this.right = p;
                else
                    this.right.add(p);
            }
        }
    
    
        public Node() {
    
        }
    
        public Node(Object p) {
            data = p;
           	left=null;
           	right=null;
        }
    
    }
    
    //树类型	
    class Tree{
        private Node root;
    
        public void add(Object p){
            if(root==null){
                root=new Node(p);
            }
            else{
                root.add(new Node(p));
            }
        }
    }
    

    首先理解的是:如何沿着树的节点进行深度遍历;

    • 树的节点本质上是一个地址
    • 每一个节点都有它的子节点(也就是存放了子节点的地址)
    • 将当前节点指向子节点就会进行深度遍历

    这里用递归的方法实现DFS(代码短)

    	public void dfssearch(){
            if(root==null)//当root为空 就没必要对树进行遍历
                return;
            else{
                DfsSearch(root);
            }
        }
        private void DfsSearch(Node node) {//node存放当前的节点
            if (node.left != null)//先对左节点进行深度遍历
                DfsSearch(node.left);
                //直到左节点为Null
               	//就会输出当前节点的值
            System.out.println(node.data);
            	//输出后就对右节点进行深度遍历
            if (node.right != null)
                DfsSearch(node.right);
                //最后回溯返回到父节点
        }
    

    广度优先算法(BFS)
    BFS算法,它会对树或图进行"逐层"的遍历,也就是层序遍历,相较于DFS算法而言,BFS它不会直接到末尾,而是到下一层之前,会将节点的所有兄弟节点遍历完之后,再进入下一层。

    从这一个定义,不难发现进行BFS需要一个FIFO(先进先出)的数组,也就是队列,而在JAVA中LinkedList就符合这样的情况

     	public void bfsSearch(){
            if(root==null)
                return;
            else{
                BfsSearch();
            }
        }
        private void BfsSearch(){
            LinkedList queue=new LinkedList();
                    queue.add(root);//将根节点存放进队列中
            while(!queue.isEmpty()){//只要队列不为空,也就是说没有对树遍历完成
               Node cur=(Node) queue.removeFirst();//将队列移除的节点作为当前节点
               System.out.println(cur.data);
                //将子节点存放进队列
                if(cur.left!=null)
                    queue.add(cur.left);
                if(cur.right!=null)
                    queue.add(cur.right);
        }
    
    //主函数测试
    public static void main(String[] args) {
            Tree root=new Tree();
            root.add(5);
            root.add(3);
            root.add(9);
            root.add(4);
            root.add(2);
            root.add(8);
            root.add(7);
           
        }
    

    这就是该树的结构
    整颗树的结构
    DFS算法结果
    在这里插入图片描述
    BFS算法的结果
    在这里插入图片描述

    总结
    BFS用于搜索单一的最短路径,特点就是"搜到就是最优的解"
    DFS用于查找所有的解,空间效率高,但不一定是最优解

    展开全文
  • DFSBFS算法

    千次阅读 2022-02-05 09:09:47
    深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。下面分别介绍两种基本的搜索算法

    深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。下面分别介绍两种基本的搜索算法。

    理论介绍

    深度优先遍历DFS

    DFS属于图算法的一种,是针对图和树的遍历算法。深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。一般用堆或栈来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,如果遇到死路就往回退,回退过程中如果遇到没探索过的支路,就进入该支路继续深入,每个节点只能访问一次。

    广度优先遍历BFS

    广度优先搜索(也称宽度优先搜索)是连通图的一种遍历算法,也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和广度优先搜索类似的思想。属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。基本过程,BFS是从根节点开始,沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问,则算法中止。一般用队列数据结构来辅助实现BFS算法。

    广度优先搜索应用:层序遍历、最短路径、求二叉树的最大高度、
    由点到面遍历图、拓扑排序

    深度优先搜索应用:先序遍历,中序遍历,后序遍历

    图解

    假设从0开始访问所有节点,可能的路径有哪些?
    在这里插入图片描述(1)DFS方法
    首先选择1,然后到7、8,发现走不动了。
    在这里插入图片描述
    然后退回到7,再探索节点10。回退到1,探索9:在这里插入图片描述
    再退回到景点0,后续依次探索2、3、5、4、6,走完所有节点:在这里插入图片描述
    二叉树的前序、中序、后序遍历,本质上可以认为是深度优先遍历。是一种回溯思想。
    (2)BFS方法
    首先探索节点0的相邻节点1、2、3、4:
    在这里插入图片描述接着,探索与节点0相隔一层的7、9、5、6:
    在这里插入图片描述最后,探索与节点0相隔两层的节点8、10:
    在这里插入图片描述
    可以看出,BFS是一层一层的由内向外遍历,二叉树的层序遍历本质上可以认为是广度优先遍历。

    代码框架

    DFS

    非递归:
    1.利用栈实现
    2.从源节点开始把节点按照深度放入栈,然后弹出
    3.每弹出一个点,把该节点下一个没有进过栈的邻接点放入栈
    4.直到栈为空

    BFS

    1.利用队列实现
    2.从源节点开始依次按照宽度进队列,然后弹出
    3.每弹出一个节点,就把该节点所有没有进过队列的邻接点放入队列
    4.直到队列为空

    供参考:

    class Graph:
        # *args 把参数打包成tuple供函数调用。**kwargs把 x = a,y=b打包成字典{x:a,y:b}供函数调用
        def __init__(self, *args, **kwargs):
            self.neighbors = {}
            self.visited = {}
            
        def add_nodes(self, nodes):
            for node in nodes: 
                self.add_node(node)
        
        def add_node(self, node):
            print('self.nodes()',self.nodes())
            if node not in self.nodes():
                self.neighbors[node] = [node]
    
        def add_edge(self, edge):
            u, v = edge
            if u not in self.neighbors[v] and v not in self.neighbors[u]:
                self.neighbors[u].append(v)
                if u != v:  # 没有自环
                    self.neighbors[v].append(u)
        
        def nodes(self):
            return self.neighbors.keys()
       
        # 递归 DFS
        def depth_first_search(self, root = None):
            order = []
          
            def dfs(node):
                self.visited[node] = True
                order.append(node)
                for n in self.neighbors[node]:
                    if n not in self.visited:
                        dfs(n) 
            if root:
                dfs(root)  # dfs(0)
            # print('visited', self.visited) 
             #对于不连通的结点(即dfs(root)完仍是没有visit过的单独处理,再做一次dfs
            for node in self.nodes():
                if node not in self.visited:
                    dfs(node)
            self.visited = {}
            print(order)
            # print('final visited', self.visited)
            return order
        
        # 非递归 DFS
        def depth_first_search_2(self, root=None):
            stack = []
            order = []
            def dfs():
                while stack:
                    print('stack',stack)
                    node = stack[-1] # 栈顶元素
                    for n in self.neighbors[node]:
                        if n not in self.visited:
                            order.append(n)
                            stack.append(n)
                            # stack.append(self.neighbors[n])
                            self.visited[n] = True
                            print('self.visited', self.visited)
                            break
                    else: 
                        stack.pop() 
                    
            if root:
                stack.append(root)
                order.append(root)
                self.visited[root] = True
                dfs()    
            for node in self.nodes():
                if node not in self.visited:
                    stack.append(node)
                    order.append(node)
                    self.visited[node] = True    
                    dfs()       
            # self.visited = {}  # 非必须
            print(order)
            return order
        
        # BFS
        def breadth_first_search(self,root=None):
            que = []
            order = []
            def bfs():
                while len(que) > 0: # 队列非空
                    node = que.pop(0) # 从左侧开始弹出  list对象有pop但是没有popleft
                    self.visited[node] = True
                    for n in self.neighbors[node]:
                        print('self.visited', self.visited)
                        print('que', que)
                        if n not in self.visited and n not in que:
                            que.append(n)
                            order.append(n)
            if root:
                que.append(root)
                order.append(root)
                bfs()
                
            for node in self.nodes():
                if not node in self.visited:
                    que.append(node)
                    order.append(node)
                    
            self.visited = {}
            print(order)
            return order        
    

    参考:
    https://blog.csdn.net/weixin_40314737/article/details/80893507

    展开全文
  • 图文详解 DFS 算法 BFS 算法

    千次阅读 2020-04-19 12:15:00
    点击关注上方“五分钟学算法”,设为“置顶或星标”,第一时间送达干货。转自码海前言 深度优先遍历(Depth First Search, 简称 DFS) 与广度优先遍历(Breath F...
  • 其实将BFS和DFS放到一起来看,其实不管是BFS换上DFS,都是对线性表的操作,只不过DFS是利用栈的特性写的回溯函数而已,而BFS是利用队列的特性写的拓展函数而已。 (不是很懂DFS算法的兄弟们可以看我上一篇博客) ...
  • 这是山东大学可视化课程项目,用js实现的BFS和DFS,详细的展示了BFS和DFS的运行过程,网页可交互。
  • DFS(深度优先遍历)与BFS(广度优先遍历)算法是基于树图结构进行遍历的两种算法。 一般来说DFS在前中后遍历中运用比较明显,DFS的运用基本是要利用...所以为了更深入的理解DFS和BFS算法的精髓,这里针对这些数据
  • } void DFS(int v) { visit(v); // 访问顶点元素 visited[v] = true; for (int w = 0; w ; w++) { if (edge[v][w] == 1 && visited[w] == false) { visited[w] = true; DFS(w); } } } void BFS(int v) { visit(v); ...
  • dfs bfs算法区别

    2020-04-07 21:29:03
    首先这两种算法都是没有代码公式的,只是一种遍历查找思想!...深度优先搜索算法(Depth-First-Search,缩写为 DFS),是一种利用递归实现的搜索算法。简单来说,其搜索过程 “不撞南墙不回头” 类似。 BFS 的重...
  • 实现图结构的DFS和BFS遍历
  • dfs和bfs差别_BFS和DFS之间的区别

    千次阅读 2020-09-14 01:52:44
    Here you will learn aboutdifference between BFS and DFS ... 在这里,您将了解BFS和DFS算法BFSDFS之间的区别。 Breadth First Search (BFS) and Depth First Search (DFS) are two popular algorithms ...
  • bfs和dfs算法

    2021-10-11 20:59:29
    bfs(广度优先搜索) 从某一个顶点出发开始访问,被访问的顶点做相应的标记,输出访问顶点。 从被访问的顶点出发,搜索与该顶点有边的关联的某个未被访问的邻接点,并做相应标记。 再从根据上述中所有被访问的邻...
  • 定义采用邻接矩阵存储的图结构封装DFSBFS算法
  • 数据结构基础27:DFS和BFS算法总结

    千次阅读 2019-02-16 05:06:04
    前言:图的遍历算法DFS和BFS是许多图算法的基础,所以有必要单独拎出来总结一下。DFS和BFS主要是运用于对于图树的搜索,很多问题模型都是可以建模变成一个图或者树的,所以差不多不少问题都会涉及到这两个。比如求...
  • 1.什么是DFS和BFSDFS DFS,通俗来讲,就是深度优先搜索,它可以通过栈来实现。 举个例子: 图中的例子以A为出发点。 那么DFS的其中一个结果就是ABDFEC。 简单点概括就是一条路走到黑,如果无路可走了,就会有...
  • 今天我们来聊一下,dfs和bfs,连着两天leetcode每日一题给到dfs,着实让我领略到了dfs查找功能的强大,那么我们先一起来看看这两道题。 22. 括号生成 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成...
  • 一文弄懂搜索算法中的DFS和BFS

    万次阅读 多人点赞 2020-03-21 15:22:15
    0x01.前序 有一位小伙伴问我,迷宫问题怎么解决,我说DFS或者...0x02.DFS和BFS简要介绍 首先,回答一下那位小伙伴的问题,这个算法确实属于图里面的算法,但并不是说是专门针对图的算法,它在算法领域应用非常广泛,...
  • BFS算法和DFS算法(含图解:简单易懂)

    万次阅读 多人点赞 2020-08-30 13:54:17
    图解BFS算法和DFS算法BFS算法算法思路实现过程Python代码实现DFS算法算法思路实现过程Python代码实现 BFS算法 BFS类似于树的层次遍历过程,从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法...
  • * 本节主要描述的dfs和bfs的方法。 * 1.DFS * dfs其实就是在一种情况下一直搜寻直到碰壁,用递归实现dfs可以从递归边界 * 递归体进行考虑,递归边界即碰壁情况,递归体则是选或者不选,注意可以在递归体中进行...
  • 数据结构中重要的部分之一——图,这里主要完成一个无向无环图的建立,然后进行DFS BFS的遍历,输出结果,初学图和DFS BFS的小伙伴可以来看看噢
  • 图的DFS和BFS算法解析

    千次阅读 2018-03-07 16:04:24
    在图的基本算法中,最初需要接触的就是图的遍历算法,根据访问节点的顺序,可分为广度优先搜索(BFS深度优先搜索(DFS)。 本文将给出给出BFS和DFS的以下几种实现方式: 1、使用队列Queue实现图的BFS遍历 2...
  • 图的DFS和BFS算法

    千次阅读 2018-05-02 09:45:51
    文章主要介绍数据结构知识板块中图的两种不同存储结构下(邻接表邻接矩阵)BFS和DFS遍历算法BFS和DFS应用领域不再说明,深搜和广搜的遍历算法十分重要。 DFS 原理:深度优先搜索,顾名思义...
  • java实现dfsbfs算法

    2021-04-29 11:17:23
    dfs(深度优先搜索算法)主要是通过栈的方式来实现的,主要规则是选择一个初始顶点,如果可能(若存在),访问该顶点的一个邻接顶点,标记它,并把它放入栈中。当不能执行 第一步时(原顶点不存在未访问的邻接顶点),如果...
  • } } BFS void BFS(AGraph *G,int v,int visit[maxSize]) { ArcNode *p; int que[maxSize],front=0,rear=0; int j; printf("%c\n",G->adjlist[v].data); visit[v]=1; rear=(rear+1)%maxSize; que[rear]=v; ...
  • DFS递归方法: //DFS /// <param name="G">要遍历的图对象</param> /// <param name="v">开始遍历的顶点</param> void DFS(Graph& G, const int& v) { int i, loc, n = G....
  • 搜索算法dfs和bfs解析(附有例题)

    千次阅读 2022-02-07 11:12:26
    本文我们主要来介绍dfs和bfs的基础知识在加以几个必要的习题说明,搜索算法dfs和bfs dfs 深度优先搜索算法(简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当...
  • DFS和BFS(C++)

    2022-02-11 19:15:01
    事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次. 宽度优先搜索(Breadth First Search): ...
  • 标准C的图的实现+BFS和DFS遍历+Dijkstra算法+Prim算法+Kruskal算法实现,纯手写!下载后如有疑问可以私信联系!全部手撸,一键运行,都封装成函数了,易读性很强

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 43,948
精华内容 17,579
关键字:

dfs和bfs算法的区别