JavaScript 图

[Checkson]

背景

我们可以将复杂的网络看做一张图，数据在网络中以 点对点 形式传输。图通常用来表示和存储具有“多对多”关系的数据结构，是数据结构中非常重要的一种结构。图是众多数据中比较复杂的一种，本章，我们将介绍，如何用 JavaScript 表示图，如何实现重要的图算法。

定义

图由 边 的集合和 顶点 的集合组成。我们在中国地图上看到各个省道、国道、高速、铁路等连接两个地方的道路，在图里面都可以看做 边，各个交通枢纽，例如北京、上海、深圳、广州等城市，在图中可以看做是 顶点。

边由顶点 对 (v1,v2) 定义，v1 和 v2 分别是图中的两个顶点。顶点也有权重，也称为成本。如果一个 图的顶点对是有序的，则可以称之为有向图。在对有向图中的顶点对排序后，便可以在两个顶点之间绘制一个箭头。有向图表明了顶点的流向。计算机程序中用来表明计算方向的 流程图就是一个有向图的例子。下面展示了一个有向图。

如果图是无序的，则称之为无序图，或无向图。下面展示了一个无序图。

图中的一系列顶点构成路径，路径中所有的顶点都由边连接。路径的长度用路径中第一个顶点到最后一个顶点之间边的数量表示。由指向自身的顶点组成的路径称为环，环的长度为 0。

圈是至少有一条边的路径，且路径的第一个顶点和最后一个顶点相同。无论是有向图还是无向图，只要是没有重复边或重复顶点的圈，就是一个简单圈。除了第一个和最后一个顶点以外，路径的其他顶点有重复的圈称为平凡圈。

如果两个顶点之间有路径，那么这两个顶点就是强连通的，反之亦然。如果有向图的所有的顶点都是强连通的，那么这个有向图也是强连通的。

顶点（Vertex）类实现

创建图类的第一步就是要创建一个 Vertex 类来保存顶点和边。这个类的作用与链表和二叉搜索树的 Node 类一样。Vertex 类有两个数据成员:一个用于标识顶点，另一个是表明这个顶点是否被访问过的布尔值。它们分别被命名为 label 和 hadVisited。这个类只需要一个函数，那就是为顶点的数据成员设定值的构造函数。Vertex 类的代码如下所示:

// 顶点构造函数
function Vertex (label) {
    this.label = label;
    this.hadVisited = false;
}

边表示

图的实际信息都保存在边上面，因为它们描述了图的结构。我们很容易像之前提到的那样用二叉树的方式去表示图，这是不对的。二叉树的表现形式相当固定，一个父节点只能有两个子节点，而图的结构却要灵活得多，一个顶点既可以有一条边，也可以有多条边与它相连。

我们将表示图的边的方法称为邻接表。这种方法将边存储为由顶点的相邻顶点列表构成的数组，并以此顶点作为索引。使用这种方案，当我们在程序中引用一个顶 点时，可以高效地访问与这个顶点相连的所有顶点的列表。比如，如果顶点 2 与顶点 1、 3相连，并且它存储在数组中索引为 2 的位置，那么，访问这个元素，我们可以访 问到索引为 2 的位置处由顶点 1、3组成的数组。请参考下图：

图（Vertex）类实现

确定了如何在代码中表示图之后，构建一个表示图的类就很容易了。下面是第一个 Graph类的定义:

[完整代码地址]

// 图构造函数
function Graph (v) {
    this.vertices = v;
    this.edges = 0;
    this.adj = [];
    this.init();
}

// 数据初始化
Graph.prototype.init  = function () {
    for (var i = 0; i < this.vertices; i++) {
        this.adj[i] = [];
    }
}

// 添加边
Graph.prototype.addEdge = function (v1, v2) {
    this.adj[v1].push(v2);
    this.adj[v2].push(v1);
    this.edges++;
}

// 输出图信息
Graph.prototype.showGraph = function () {
    for (var i = 0; i < this.vertices; ++i) {
        var logMsg = i + ' -->';
        for (var j = 0; j < this.vertices; j++) {
            if (this.adj[i][j]) { 
                logMsg += ' ' + this.adj[i][j]
            }
        }
        console.log(logMsg);
    }
}

图（Graph）类测试

var graph = new Graph(6);

graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(1, 4);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.addEdge(3, 5);

graph.showGraph();

运行结果

0 --> 4
1 --> 2 4
2 --> 1 3
3 --> 2 4 5
4 --> 0 1 3
5 --> 3

图的遍历

深度优先搜索

深度优先搜索包括从一条路径的起始顶点开始追溯，直到到达最后一个顶点，然后回溯， 继续追溯下一条路径，直到到达最后的顶点，如此往复，直到没有路径为止。这不是在搜索特定的路径，而是通过搜索来查看在图中有哪些路径可以选择。

// 深度优先搜索
Graph.prototype.dfs = function (v) {
    var st = [], top = -1;
    var visited = [];
    st[++top] = v;
    visited[v] = true;
    while (top !== -1) {
        var vertex = st[top--];
        console.log('Visited --> ' + vertex);
        for (var i = this.adj[vertex].length - 1; i >= 0; i--) {
            if (!visited[this.adj[vertex][i]]) {
                st[++top] = this.adj[vertex][i];
                visited[this.adj[vertex][i]] = true;
            }
        }
    }
}

广度优先搜索

广度优先搜索从第一个顶点开始，尝试访问尽可能靠近它的顶点。本质上，这种搜索在图上是逐层移动的，首先检查最靠近第一个顶点的层，再逐渐向下移动到离起始顶点最远的层.

Graph.prototype.bfs = function (v) {
    var rear = -1, front = -1;
    var queue = [], visited = [];
    queue[++rear] = v;
    visited[v] = true;
    while (rear != front) {
        var vertex = queue[++front];
        console.log('Visited --> ' + vertex);
        for (var i = 0; i < this.adj[vertex].length; i++) {
            var tempVertex = this.adj[vertex][i];
            if (!visited[tempVertex]) {
                queue[++rear] = tempVertex;
                visited[tempVertex] = true;
            }
        }
    }
}

测试代码

var graph = new Graph(6);

graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(1, 4);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.addEdge(3, 5);

console.log('=============== dfs ===============');
graph.dfs(0);
console.log('=============== bfs ===============');
graph.bfs(0);

运行结果

=============== dfs ===============
Visited --> 0
Visited --> 4
Visited --> 1
Visited --> 2
Visited --> 3
Visited --> 5
=============== bfs ===============
Visited --> 0
Visited --> 4
Visited --> 1
Visited --> 3
Visited --> 2
Visited --> 5

查找最短路径

图最常见的操作之一就是寻找从一个顶点到另一个顶点的最短路径。考虑下面的例子：在国庆假期中，你将在两个星期的时间里游历 10 个大旅游城市，去参观各种名胜古迹。你希望通过最短路径算法，找出开车游历这 10 个城市行驶的最小里程数。另一个最短路径问题涉及创建一个计算机网络时的开销，其中包括两台电脑之间传递数据的时间，或者两台电脑建立和维护连接的成本。最短路径算法可以帮助确定构建此网络的最有效方法。

广度优先搜索对应的最短路径

在执行广度优先搜索时，会自动查找从一个顶点到另一个相连顶点的最短路径。例如，要查找从顶点 A 到顶点 D 的最短路径，我们首先会查找从 A 到 D 是否有任何一条单边路径， 接着查找两条边的路径，以此类推。这正是广度优先搜索的搜索过程，因此我们可以轻松地修改广度优先搜索算法，找出最短路径。

参考链接

最短路径—Dijkstra算法和Floyd算法
图的四种最短路径算法
拓扑排序