Fork me on GitHub

图和图算法

algorithm/graph/banner

本博文是提炼《数据结构与算法javascript描述》第十一章的内容。将讨论如何用图给网络建模,如何用javascript表示图,如何实现重要的图算法…

图的定义

图由边的集合及顶点的集合组成。边由顶点对(v1,v2)定义,v1和v2分别是图中的两个顶点。顶点也有权重,也称为成本。如果一个图的顶点对是有序的,则称为有序图/有向图。如果一个图的顶点对是无序的,则称为无序图/无向图。如下:

algorithm/graph/direction_graph

algorithm/graph/none_direction_graph

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

是至少有一条边的路径,且路径的第一个顶点和最后一个顶点相同。无论是有向图还是无向图,只要是没有重复边或者重复顶点的圈,就是一个简单圈。除了第一个和最后一个顶点以外,路径的其他顶点有重复的圈称为平凡圈【有点质疑,不应该是频繁圈嘛】。

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

用图对现实中的系统建模

可以用图对现实中的很多系统建模,比如对交通流量建模,顶点可以表示街道的十字路口,边可以表示街道。加权的边可以表示限速或者车道的数量。建模人员可以用这个系统来判断最佳路线及最可能堵车的街道。

图类

如果类似树/二叉树这种基于对象的方式去处理图的问题就会有问题,因为图可能增长到非常大。用对象来表示图很快就会变得效率低下,所以我们要考虑表示顶点和边的方案。

表示顶点

创建图类的第一步就是创建一个Vertex类来保存顶点和边。Vertex类有两个数据成员:一个用于标识顶点,另一个是表明这个顶点是否被访问过的布尔值。如下:

1
2
3
4
function Vertex(label , wasVisited){
this.label = label;
this.wasVisited = wasVisited;
}

这里将所有顶点保存在数组中,在图类里,可以通过他们在数组中的位置引用他们。

表示边

图的实际信息都保存在边上面,因为它们描述了图的结构。

我们将表示图的边的方法称为邻接表或者邻接表数组。这种方法将边存储为顶点的相邻顶点列表构成的数组,并以此顶点为索引。

构建图

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

1
2
3
4
5
6
7
8
9
10
11
function Graph(v) {
this.vertices = v;
this.edges = 0;
this.adj = [];
for(var i = 0 ; i < this.vertices; ++i){
this.adj[i] = [];
this.adj[i].push("");
}
this.addEdge = addEdge;
this.toString = toString;
}

这个类会记录一个图表示了多少条边,并使用一个长度与图的顶点数组来记录顶点的数量。通过for循环为数组中的每个元素添加一个子数组来存储所有的相邻顶点,并将所有元素初始化为空字符串。

addEdge添加边的函数如下:

1
2
3
4
5
function addEdge(v,w){
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}

当调用这个函数并传入顶点A和B时,函数会先查找顶点A的邻接表,将顶点B添加到列表中,然后再查找顶点B的邻接表,将顶点A加入列表。最后这个函数会将边加1。

showGraph函数会打印所有顶点及其相邻顶点列表的方式来显示图:

1
2
3
4
5
6
7
8
9
10
11
function showGraph() {
for(var i = 0; i < this.vertices; ++i){
console.log(i + "->");
for(var j = 0; j < this.vertices; ++j){
if(this.adj[i][j] != undefined){
console.log(this.adj[i][j]);
}
}
console.log('');
}
}

搜索图

确定从一个指定的顶点可以到达其他哪些顶点,这是经常对图执行的操作。图上的这些操作是用搜索算法执行的。在图上可以执行两种基础搜索:深度优先搜索和广度优先搜索

深度优先搜索

深度优先搜索包括从一条路径的起始顶点开始追溯,直到到达最后一个顶点,然后回溯,继续追溯下一条路径,直到到达最后的顶点,如此反复,直到没有路径为止。如下图:

algorithm/graph/deep_priority_search

深度优先搜索算法比较简单:访问一个没有访问过的顶点,将它标记为已访问,再递归地去访问在初始顶点的的邻接表中没有访问过的顶点

要让该算法运行,需要为Graph类添加一个数组,用来存储已访问过的顶点,将它所有元素的值都初始化为false。

1
2
3
4
this.marked = [];
for(var i = 0, i < this.vertices; i++){
this.marked[i] = false;
}

深度优先搜索的函数如下:

1
2
3
4
5
6
7
8
9
10
11
function dfs(v){
this.marked[v] = true;
if(this.adj[v] != undefined){
console.log('Visited vertex: '+v);
}
for each(var w in this.adj[v]){
if(!this.marked[w]){
this.dfs(w);
}
}
}

广度优先搜索

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

algorithm/graph/bright_priority_search

广度优先搜索算法是使用了抽象的队列而不是数组来对已访问过的顶点进行排序。其算法的工作原理如下:

  1. 查找和当前顶点相邻的未访问顶点,将其添加到已经访问顶点列表及队列中;
  2. 从图中取出下一个顶点v,添加到已访问的顶点列表中;
  3. 将所有与v相邻的未访问顶点添加到队列中。

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function bfs(s) {
var queue = [];
this.marked[s] = true;
queue.push(s); // 添加到队尾
while(queue.length >0){
var v = queue.shift(); // 从队首移除
if(v != undefined){
console.log('Visited vertex: '+ v);
}
for each(var w in this.adj[w]) {
if(!this.marked[w]) {
this.edgeTo[w] = v;
this.marked[w] = true;
queue.push(w);
}
}
}
}

查找最短路径

图是常见的操作之一就是寻找从一个顶点到另外一个顶点的最短路径。

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

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

确定路径

首先,我们需要一个数组保存从一个顶点到下一个顶点的所有边。我们将这个数组命名为edgeTo。因为从始至终使用的都是广度优先搜索函数,所以每次都会遇到一个没有标记的顶点,除了对它进行标记外,还会从邻接列表中我们正在探索的那个顶点添加一条边到这个顶点。这是新的bfs()函数,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 将这行添加到Graph类
this.edgeTo = [];

// bfs函数
function bfs(s){
var queue = [];
this.marked[s] = true;
queue.push(s); // 添加到队尾
while(queue.length > 0){
var v = queue.shift(); // 从队首中删除
if(v != undefined) {
console.log('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);
}
}
}
}

现在我们需要一个函数,用于展示图中连接到不同顶点的路径。函数pathTo()创建了一个栈,用来存储与指定顶点有共同边的所有顶点。以下是pathTo()函数的代码,以及一个简单的辅助函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function pathTo(v){
var source = 0;
if(!this.hasPathTo(v)) {
return undefined;
}
var path = [];
for(var i = v; i != source; i = this.edgeTo[i]){
path.push(i);
}
path.push(s);
return path;
}

function hasPathTo(v){
return this.marked[v];
}

拓扑排序

拓扑排序会对有向图的所有顶点进行排序,使有向边从前面的顶点指向后面的顶点。

拓扑排序算法

拓扑排序算法与深度优先搜索类似。不同的是,拓扑排序算法不会立即输出已访问的顶点,而是访问当前顶点邻接表中的所有相邻顶点,直到这个链表穷尽时,才将当前顶点压入栈中。

实现拓扑排序算法

拓扑算法被拆分为两个函数。第一个是topSort(),会设置进程并调用一个辅助函数topSortHelper(),然后现实排序好的顶点列表。主要工作是递归函数topSortHelper()中完成的。这个函数会将当前顶点标记为已访问,然后递归访问当前顶点邻接表中的每个相邻顶点,标记这些顶点为已访问。最后,将当前顶点压入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function topSort(){
var stack = [];
var visited = [];
for(var i = 0 ; i < this.vertices; i++){
visited[i] = false;
}
for(var i = 0; i < this.vertices; i++){
if(visited[i] == false){
this.topSortHelper(i, visited , stack);
}
}
for(var i = 0 ; i < stack.length; i++){
if(stack[i] != undefined && stack[i] != false){
console.log(this.vertexList[stack[i]]);
}
}
}

function topSortHelper(v , visited ,stack){
visited[v] = true;
for each (var w in this.adj[v]){
if(!visited[w]){
this.topSortHelper(visited[w] , visited , stack);
}
}
stack.push(v);
}

参考

数据结构与算法javascript描述》 Michael McMillan

<-- 本文已结束  感谢您阅读 -->
客官,且步,赏一个呗 (@ ~ @)