Javascript —— 有向图广度优先搜索

用Javascript实现有向图的广度优先搜索

刚好遇到一个需求，对于一个有向图，指定一个节点 i 作为起点，输出从 i 出发，可以到达的所有节点，也就是图中以 i 作为起点的子连通片，思考了一下，可以用以前学的广度优先搜索解决。

一、有向图的存储

我们用一个邻接矩阵（二维数组）存储有向图的信息，对于一个矩阵graph，若graph[i][j] = true，则表示存在一条由节点 i 到 j 的边。

// 使用d3读取json文件

d3.json("test.json", function(error, graph) {

        // 构造邻接矩阵

        var graph_array = new Array();

        graph.links.forEach(function(d){

                if(!graph_array[d.source])

                {

                        graph_array[d.source]= new Array();

                }

                graph_array[d.source][d.target] = true;

        });

}

二、广度优先搜索（Breadth First Search）

步骤：

（0）创建一个队列存储经过的节点，把当前节点初始化为 i ，并将其入队（push）

（1）进行一次出队操作（pop），得到队首的节点 j（此时应把j记录下来，作为返回结果），遍历以 j 为起点的边，把这些边的终点节点依次入队

（2）判断队列是否为空，若是，则返回结果；若否，则跳回第一步继续执行。

算法的时间复杂度为O(n²)

具体代码如下：

function breadth_first_search(graph_array, root)

{

        var ret_nodes = {};　// 用于存储经过的节点

        var queue = [];

        queue.push(root);

        do

        {

                var current_node = queue.shift();

                ret_nodes[current_node] = true;

                for(var i = 0; graph_array[current_node] && i < graph_array[current_node].length; i++)

                {

                        if(graph_array[current_node][i])

                        {

                                queue.push(i);

                        }

                }

        }while(queue.length !== 0);

        return ret_nodes;

}