广度优先算法，深度优先算法和DijKstra算法

广度优先算法，深度优先算法和DijKstra算法

引用

CSDN

1.

https://blog.csdn.net/sallyxyl1993/article/details/57077512

我们经常会碰到最短路径问题，而最短路径问题的解决方法多种多样，广度优先搜索（BFS），深度优先搜索（DFS）和DijKstra算法貌似都能解决这个问题，这里就简单介绍一下这些算法，分析一下它们的适用范围。

一、原理剖析：

1. 广度优先搜索（BFS）

广度优先搜索依赖的是队列解决问题。队列中的每一个节点需要包含记录以下内容：该节点到起点的距离dist，该节点的前驱节点past，该节点在当前路径下是否被访问过visit（0表示没有访问过，1表示当前路径下正在访问，2表示该节点周围的所有节点都已经被访问过）。

编程逻辑大致如下：

初始化：
起点值初始化（past=NULL，dist=0，visit=1）
其他节点值初始化（past=NULL，dist=无穷，visit=0）
起点入队
循环1：直到队列中没有元素
   从队伍中输出一个节点作为当前节点
   循环2：访问与当前节点连通但是【没有被访问过】的节点（visit=0的节点）
      将即将访问的节点记为正在访问的状态
      将即将访问的节点的状态更新（past=当前节点，dist=即将访问的节点到当前节点的距离，visit=1）
      即将访问的节点入队
   将当前节点的visit记为2（因为与它连接的所有节点都被访问过）   

为什么需要记录这些内容？我们逐一解释：首先，节点到起点的距离很好解释，这是问题的需求，但是在二叉树的层序遍历时，我们仅仅需要将节点输出，而不需要计算距离，此时不记录这个内容也没关系。如果题意不要求输出最短的路径，而是只要求我们记录最短的路径是多少，那不记录前驱节点问题也不大，它不影响最短路径的求解。记录该节点在当前路径下是否被访问的目的是，避免图中有环路而造成节点的重复访问和死循环，但是对于树形结构，当前节点不可能遍历以前访问过的节点，这个内容可以不记录。综上，在写广度优先算法的代码时，要依据需求变通，不应教条。

2. 深度优先搜索（DFS）

深度优先搜索依赖的是递归，你完全可以把深度优先搜索理解为动态规划的一种形式。它一样要记录：该节点到起点的距离dist，该节点的前驱节点past，该节点在当前路径下是否被访问过visit（0表示没有访问过，1表示当前路径下正在访问，2表示该节点周围的所有节点都已经被访问过）。记录这些值的目的与广度优先搜索也差不多。

编程逻辑大致如下：

初始化：
所有节点值初始化（past=NULL，dist=无穷，visit=0）
递归DFS（当前节点）
  当前路径正在访问当前节点（visit=1）
  对与当前节点连通的所有【没有被访问过】的节点
      改变即将访问的节点的状态（past为当前节点，dist为即将访问的节点到当前节点的距离）
      DFS（即将访问的节点）
      【如果有环路，这里还要加一步：如果当前节点的visit不是2，就把visit设为0，否则被访问过一次就再也访问不了了】
  将当前节点的visit记为2（因为与它连接的所有节点都被访问过）   

3. DijKstra算法

DijKstra算法是运筹学中求最短路径的常规算法，它的中心思想是：让每个节点记录它到起点的最短路径，其实也可以理解为动态规划的一种形式。与前面两种方法相同，DijKstra算法也需要记录：该节点到起点的距离dist，该节点的前驱节点past。

但是不同的是，不需要记录该节点是否被访问过，而是记录：该节点到起点的最短距离是否已经确定visit（0表示还没有确定了该节点到起点的最短距离，1表示已经确定该节点到起点的最短距离）。

编程逻辑大致如下：

初始化：
起点初始化（dist=0，past=NULL，visit=1）
其他节点初始化（dist=无穷，past=起点，visit=0）
循环：对于所有节点
  循环：对于所有【不确定到起点最短距离】的节点，找出距离起点最近的节点并记录距离
  更新找出的节点的状态（visit=1）
  循环：对于所有【不确定到起点最短距离】的节点
    计算它到刚才找出的节点的距离
    如果节点经过刚才找出的节点到起点的距离小于节点直接到达起点的距离
      更新节点的状态（dist=找出的节点的dist+找出的节点到该节点的距离，past=找出的节点）
  

二、优缺点剖析：

首先我们看如下无向图：假设所有边的权重都是正数

如果我想求从1到5的最短距离，上述描述的三种方法都可以。

我们再看如下情况：

假设所有边的权重都是相同的正数，求从1到3的最短路径。

我们利用DFS依照节点的id从小到大搜索，只能得到1-2-3这样的结果，那是因为1-3这条路径根本没有被访问到。

我们再看算法导论一书中给出的BFS和DFS示意图：

上图是BFS的示意图，从图中可以清楚地看出一次BFS的完整过程。我们可以发现：没有加粗的边是没有被访问过的。

上图是DFS的示意图，从图中可以清楚地看出一次DFS的完整过程，我们可以发现：虚线边是没有被访问过的。

到这里结论已经很清楚了：

DFS和BFS是以遍历所有节点为主要目的的算法，他们不一定能遍历所有的路径。即使在一些三种方法通用的情况下，DFS和BFS还有一些编程上的繁琐之处，主要表现在，我们需要额外定义变量存放最短路径，节点自身携带的最短路径和前驱节点是随着循环/迭代的进行不断更新的，它不能在节点中保留最优解。而对于DijKstra算法而言，节点自身保留的就是最优情况，不需要额外定义变量。

综上所述：我的建议是，针对树形结构求解类似最短路径或最小权重和的题目时，DFS和BFS是不错的选择，但是当遇到有环状结构的最短路径题时应该格外警惕，此时选择DijKstra算法比较稳妥。

应用分割线：

广度优先BFS的应用：

• 二叉树的层序遍历

深度优先DFS的应用：

• 树的深度求解

DijKstra：

• 最短路径