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

基尔霍夫的猫 2019-06-21

深度优先搜索(DFS)

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

图1

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

与广度优先算法不同,深度优先算法不需要一个起始顶点,只要顶点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<vertices.length; i++){
                color[vertices[i]] = 'white';
            }
            return color;
        };
    }

接下来实现深度优先算法的核心代码:

this.dfs = function(callback){
        var color = initializeColor(); // 将所有顶点初始化为白色
        for (var i=0; i<vertices.length; i++){
            if (color[vertices[i]] === 'white'){ // 对每一个没有被访问过的顶点调用dfsVisit方法
                dfsVisit(vertices[i], color, callback); // {1}
            }
        }
        function dfsVisit(u, color, callback){
            color[u] = 'grey'; // 将顶点u置为灰,表明访问过但还没有完全探索
            callback && callback(u); // 执行回调函数
            var neighbors = adjList.get(u); // 获取顶点u的所有相邻顶点
            for (var i=0; i<neighbors.length; i++){ // 探索所有相邻顶点
                var w = neighbors[i];
                if (color[w] === 'white'){ // 如果相邻的顶点没有被访问过,则对其执行dfsVisit方法
                    dfsVisit(w, color, callback);
                }
            }
            color[u] = 'black'; // 将顶点u置为黑,表明已经完全访问。
        };
    };

对图1中的图执行上述搜索算法的过程如图2。

图2

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

由于我们是从起始点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<vertices.length; i++){
            if (color[vertices[i]] === 'white'){
                DFSVisit(vertices[i], color, d, f);
            }
        }

        return { // 返回探索数据
            discovery: d,
            finished: f
        };
        function DFSVisit(u, color, d, f){
            console.log('discovered ' + u);
            color[u] = 'grey';

            d[u] = ++time; // 发现顶点u后,时间+1

            var neighbors = adjList.get(u);
            for (var i=0; i<neighbors.length; i++){
                var w = neighbors[i];
                if (color[w] === 'white'){
                    DFSVisit(w,color, d, f);
                }
            }
            color[u] = 'black';
            
            f[u] = ++time; // 探索完顶点u后,时间+1
            
            console.log('explored ' + u);
        };
    };

对于深度优先算法,边是从最近发现的顶点u处被向外探索的。只有连接到未发现的顶点的边被探索了。当u所有的边都被探索了,该算法回退到u被发现的地方去探索其他的边。这个过程持续到我们发现了所有从原始顶点能够触及的顶点。如果还留有任何其他未被发现的顶点,我们对新源顶点重复这个过程。重复该算法,直到图中所有的顶点都被探索了。
观察上述代码可以发现,time的值只能在图的顶点数量的一到两倍之间,并且d[u]<f[u],即发现时间的值比完成时间的值小。

拓扑排序

给定图3,假定每个顶点都是一个我们需要去执行的任务。

图3

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

这是一个有向无环图(DAG),即任务的执行是有顺序的,例如,任务F不能在任务A之前执行,并且该图没有环。
当我们需要编排一些任务或步骤的执行顺序时,这称为拓扑排序。比如,当我们在开发一个项目时,首先我们得从客户那里得到需求,接着开发客户要求的东西,最后交付项目,但不能先交付项目再去收集需求。
拓扑排序只能应用于DAG。用深度优先搜索算法对图3中的任务图进行拓扑排序:

graph = new Graph();
myVertices = ['A','B','C','D','E','F'];
for (i=0; i<myVertices.length; i++){
    graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('B', 'D');
graph.addEdge('B', 'E');
graph.addEdge('C', 'F');
graph.addEdge('F', 'E');
var result = graph.DFS();

最终各顶点的发现和探索完成时间会保存在result中。图4直观地注明了各个顶点的发现时间/探索完成时间。

图4

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

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

相关推荐