学习JavaScript数据结构与算法 — 深度优先搜索算法

李增田发布于2019-08-22 11:09 / 571人阅读

摘要：深度优先搜索上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。用深度优先搜索算法对图中的任务图进行拓扑排序最终各顶点的发现和探索完成时间会保存在中。

深度优先搜索（DFS）

上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。其中深度优先搜索算法会从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶点，接着原路回退并探索下一条路径。换句话说，它是先深度后广度地访问顶点，如下图1。

图1

与广度优先算法不同，深度优先算法不需要一个起始顶点，只要顶点v没有被访问，就访问该顶点。
我们用三种状态来反映顶点的状态：

白色：表示该顶点还没有被访问。

灰色：表示该顶点被访问过，但并未被探索过。

黑色：表示该顶点被访问过且被完全探索过。

访问某一顶点v的步骤如下：

标注v为被发现的（灰色）

对于v的所有未访问的邻点w：访问顶点w

标注v为已被探索的（黑色）

因此深度优先搜索的步骤是递归的，这意味着深度优先搜索算法使用栈来存储函数调用（由递归调用所创建的栈）。
与广度优先算法类似，在算法开始之前，我们需要将所有顶点置为白色（本文的所有代码都是在图中实现的Graph类中添加的）。

    function Graph() {
        var vertices = [];
        var adjList = new Dictionary();
        // 图类的其他代码省略...
        var initializeColor = function(){
            var color = [];
            for (var i=0; i
接下来实现深度优先算法的核心代码：
    this.dfs = function(callback){
        var color = initializeColor(); // 将所有顶点初始化为白色
        for (var i=0; i
对图1中的图执行上述搜索算法的过程如图2。
图2

由于我们是从起始点A开始搜索的，{1}处的代码只会执行一次，因为所有其他顶点都有一条路径到达A点。如果从B点开始搜索，{1}处的代码便会执行两次。
搜索时间
给定一个图G，要得到任意顶点u的发现时间（d[u]）以及完成对该顶点的搜索时间（f[u]），可以在上述代码的基础上做一定修改（修改的位置用空行隔开）：
    this.DFS = function(){
        var color = initializeColor(), //{2}
            len = vertices.length,

            d = new Array(len).fill([]), // 用于保存任意顶点u的发现时间
            f = new Array(len).fill([]), // 用于保存任意顶点u探索完成的时
            time = 0; // 用于记录探索时间

        for (var i=0; i
对于深度优先算法，边是从最近发现的顶点u处被向外探索的。只有连接到未发现的顶点的边被探索了。当u所有的边都被探索了，该算法回退到u被发现的地方去探索其他的边。这个过程持续到我们发现了所有从原始顶点能够触及的顶点。如果还留有任何其他未被发现的顶点，我们对新源顶点重复这个过程。重复该算法，直到图中所有的顶点都被探索了。
观察上述代码可以发现，time的值只能在图的顶点数量的一到两倍之间，并且d[u]
拓扑排序
给定图3，假定每个顶点都是一个我们需要去执行的任务。
图3

这是一个有向无环图（DAG），即任务的执行是有顺序的，例如，任务F不能在任务A之前执行，并且该图没有环。
当我们需要编排一些任务或步骤的执行顺序时，这称为拓扑排序。比如，当我们在开发一个项目时，首先我们得从客户那里得到需求，接着开发客户要求的东西，最后交付项目，但不能先交付项目再去收集需求。
拓扑排序只能应用于DAG。用深度优先搜索算法对图3中的任务图进行拓扑排序：
graph = new Graph();
myVertices = ["A","B","C","D","E","F"];
for (i=0; i
最终各顶点的发现和探索完成时间会保存在result中。图4直观地注明了各个顶点的发现时间/探索完成时间。
图4

那么按照探索完成时间的倒序来排序得到的拓扑排序为：
B - A - D - C - F - E
需要注意的是，算法不同，得到的拓扑排序可能不同，比如下面的拓扑排序也是可能的：
A - B - C - D - F - E

GPU云服务器云服务器最佳优先搜索算法广度优先搜索算法代码深度学习算法是什么深度优先搜索

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/91881.html

学习JavaScript数据结构与算法 — 图

摘要：图关联矩阵在关联矩阵表示的图中，矩阵的行表示顶点，列表示边。如图，顶点数是，边的数量是，用邻接矩阵表示图需要的空间是，而使用关联矩阵表示图需要的空间是。广度优先搜索算法数据结构是队列。深度优先搜索算法数据结构是栈。定义图和散列表、二叉树一样，是一种非线性数据结构。如图1所示，图由一系列顶点以及连接顶点的边构成。由一条边连接在一起的顶点成为相邻顶点，比如A和B、A和D是相邻的，而A和...

yiliang 2019-08-22 11:09 评论0 收藏0
学习JavaScript数据结构与算法 — 广度优先搜索算法

摘要：广度优先搜索上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。其中广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。其它最短路径算法对于加权图的最短路径，广度优先算法可能并不合适。广度优先搜索（BFS）上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。其中广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的...

eternalshallow 2019-08-22 11:09 评论0 收藏0
算法系列——JavaScript中广度优先搜索思想实现

摘要：散列表上面的地图向我们展示了如何用广度优先搜索的思想找到北京到广州的最短路线。在广度优先搜索中，我们需要用到队列的这种思想来实现查找。建立了下面这个模型武汉广州西藏上海上海武汉广州代码完整实现，利用递归和广度优先搜索的思想实现。什么是广度优先搜索？如果只是是背概念，幼儿园的小朋友都能背下来念给你听。假设看这篇文章的都和我一样是个前端工程师，我们要从广度优先搜索（BFS）中学到什么...

everfly 2019-08-21 17:36 评论0 收藏0
听说你想来做人工智能了

摘要：达观数据招人啦面向北京上海深圳成都四个地区提供人工智能算法产品销售等多类岗位毕业多年，你的状态还好吗是否忧虑被甩在时代的边缘是否担心被机器取代是否不安现状跃跃欲试来吧，选择对的行业，与优秀的人一起共事，与我们一起走在时代的风口上，从事当下最 showImg(https://segmentfault.com/img/bVbeHrX?w=720&h=400);达观数据招人啦！面向北京、上...

zzir 2019-06-26 18:30 评论0 收藏0