JavaScript数据结构和算法之图和图算法(2)

广度优先搜索（BFS）属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

广度优先搜索从第一个顶点开始，尝试访问尽可能靠近它的顶点，如下图所示：

其工作原理为：

1. 首先查找与当前顶点相邻的未访问的顶点，将其添加到已访问顶点列表及队列中；
 2. 然后从图中取出下一个顶点v，添加到已访问的顶点列表
 3. 最后将所有与v相邻的未访问顶点添加到队列中
下面是广度优先搜索函数的定义：

复制代码 代码如下:

function bfs(s){
    var queue = [];
    this.marked = true;
    queue.push(s);//添加到队尾
    while(queue.length>0){
        var v = queue.shift();//从队首移除
        if(v == undefined){
            print("Visited vertex: " + v);
        }
        for each(var w in this.adj[v]){
            if(!this.marked[w]){
                this.edgeTo[w] = v;
                this.marked[w] = true;
                queue.push(w);
            }
        }
    }
}

最短路径

在执行广度优先搜索时，会自动查找从一个顶点到另一个相连顶点的最短路径

确定路径

要查找最短路径，需要修改广度优先搜索算法来记录从一个顶点到另一个顶点的路径，我们需要一个数组来保存从一个顶点操下一个顶点的所有边，我们将这个数组命名为edgeTo

复制代码 代码如下:

this.edgeTo = [];//将这行添加到Graph类中

//bfs函数
function bfs(s){
    var queue = [];
    this.marked = true;
    queue.push(s);//添加到队尾
    while(queue.length>0){
        var v = queue.shift();//从队首移除
        if(v == undefined){
            print("Visited vertex: " + v);
        }
        for each(var w in this.adj[v]){
            if(!this.marked[w]){
                this.edgeTo[w] = v;
                this.marked[w] = true;
                queue.push(w);
            }
        }
    }
}

拓扑排序算法

拓扑排序会对有向图的所有顶点进行排序，使有向边从前面的顶点指向后面的顶点。
拓扑排序算法与BFS类似，不同的是，拓扑排序算法不会立即输出已访问的顶点，而是访问当前顶点邻接表中的所有相邻顶点，直到这个列表穷尽时，才会将当前顶点压入栈中。

拓扑排序算法被拆分为两个函数，第一个函数是topSort()，用来设置排序进程并调用一个辅助函数topSortHelper()，然后显示排序好的顶点列表

拓扑排序算法主要工作是在递归函数topSortHelper()中完成的，这个函数会将当前顶点标记为已访问，然后递归访问当前顶点邻接表中的每个顶点，标记这些顶点为已访问。最后，将当前顶点压入栈中。

复制代码 代码如下: