算法-图和图算法
图的定义
用图对现实中的系统建模
可以用图对现实中的很多系统建模. 比如对交通流量建模, 顶点可以表示街道的十字路口, 边可以表示街道. 加权的边可以表示限速或者车道的数量. 建模人员可以用这个系统来判断最佳路线及最有可能堵车的街道.
任何运输系统都可以用图来建模. 比如, 航空公司可以用图来为其飞行系统建模. 将每个机场看成顶点, 将经过两个顶点的每条航线看作一条边. 加权的边可以表示从一个机场到另一个机场的航班成本, 或两个机场间的距离, 这取决于建模的对象是什么.
包含局域网和广域网(如互联网)在内的计算机网络, 同样经常用图来建模. 另一个可以用图来建模的现实系统是消费市场, 顶点可以用来表示供应商和消费者.
图类
乍一看, 图和数或者二叉树很像, 你可能会尝试用树的方式去创建一个图类, 用节点来表示每一个顶点. 但这种情况下, 如果基于对象的方式去处理就会有问题, 因为图可能增长到非常大. 用对象来表示图很快就会变得效率低下, 所以我们要考虑表示顶点和边的其它方案.
表示顶点
创建图类的第一步就是要创建一个Vertex类来保存顶点和边. 这个类的作用于链表和二叉查找树的Node类一样. Vertex类有两个数据成员:
label: 表示顶点.wasVisited: 表明这个顶点是否被访问过的布尔值.
我们将所有顶点保存到数组中, 在图类里, 可以通过它们在数组中的位置引用它们.
class Vertex {
constructor(label, wasVisited) {
this.label = label;
this.wasVisited = wasVisited;
}
};表示边
图的实际信息都保存在边上面, 因为它们描述了图的结构. 我们很容易像之前提到的那样用二叉树的方式去表示图, 这是不对的. 二叉树的表现形式相当固定, 一个父节点只能有两个子节点, 而图的结构却要灵活得多, 一个顶点既可以有一条边, 也可以有多条边与它相连.
我们将表示图的边的方法称为: 邻接表 或者 _邻接表数组_. 这种方法将边存储为顶点的相邻顶点列表构成的数组, 并以此顶点作为索引. 使用这种方案, 当我们在程序中引用一个顶点时, 可以高效地访问与整个顶点相连的所有顶点的列表. 比如, 如果顶点2与顶点0、1、3、4相连, 并且它存储在数组中索引为2的位置, 那么, 访问这个元素, 我们可以访问到索引为2的位置处由顶点0、1、3、4组成的数组. 本章将选用这种表示方法.
0 --> [2] 1 --> [2] 2 --> [0, 1, 3, 4] 3 --> [2] 4 --> [2]
另一种表示图边的方法被称为: _邻接矩阵_. 它是一个二维数组, 其中的元素表示两个顶点之间是否有一条边.
构建图
确定了如何在代码中表示图之后, 构建一个图的类就容易多了.
class Graph {
constructor(v) {
this.vertices = v;
this.edges = 0;
this.adj = [];
for(let i = 0; i < this.vertices; i++) {
this.adj[i] = [''];
};
}
addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
showGraph() {
let str = '';
for(let i = 0; i < this.vertices; i++) {
str += i + '-->';
for(let j = 0; j < this.vertices; j++) {
if(this.adj[i][j] != undefined) {
str += this.adj[i][j] + ' ';
};
};
str += '\n';
};
log(str)
};
};这个类会记录一个图表示了多少条边, 并使用一个长度与图的定点数相同的数组来记录定点的数量. 通过for循环为数组中的每一个元素添加一个字数组来存储所有的相邻顶点, 并将所有元素初始化为空字符串.
添加边addEdge()这个方法会传入顶点A和B, 会先查找顶点A的领接表, 将顶点B添加到列表中, 然后再查找顶点B的领接表, 将顶点A加入列表. 最后将边数edges加1.
showGraph()这个方法会通过打印所有顶点及其相邻定点列表的方式来显示图.
const g = new Graph(5); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(2, 4); g.showGraph(); //输出 /** 0--> 1 2 1--> 0 3 2--> 0 4 3--> 1 4--> 2 **/
以上输出显示, 下面的用数字0, 1等来代替顶点0, 顶点1.
0有到1和2的边.
1有到0和3的边.
2有到0和4的边.
3有到1的边.
4有到2的边.
当然, 这种显示存在冗余, 例如, 0和1之间的边和1到0之间的边相同. 如果只是为了显示, 这样是不错的, 但是在开始探索图的路径之前, 需要调整一下输出.
搜索图
确定从一个指定的顶点可以到达其他哪些顶点, 这是经常对图执行的操作. 我们可能想通过地图了解到从一个城镇到另一个城镇的路有哪些, 或者从一个机场到其它机场的航班有哪些等.
图上的这些操作使用搜索算法执行的. 在图上可以执行两种基础搜索:
- 深度优先搜索.
- 广度优先搜索.
深度优先
深度优先包括从一条路径的其实顶点开始追溯, 直到到达最后一个顶点, 然后回溯, 继续追溯下一条路径, 直到到达最后的顶点, 如此往复, 直到没有路径为止. 这不是在搜索特定的路径, 而是通过搜索来查看在图中有哪些路径可以选择.
这里盗个图.
深度优先: 访问一个没有访问过的顶点, 将它标记为已访问, 再递归去访问在初始顶点的领接表中其它没有访问过的顶点.
要让该算法运行, 需要向Graph类添加一个数组, 用来存储已访问过的顶点(marked), 将它所有元素的值全部初始化为false. Graph类的代码片段显示了这个新数组及其初始化的过程.
window.log = console.log.bind(console)
class Vertex {
constructor(label, wasVisited) {
this.label = label;
this.wasVisited = wasVisited;
}
};
class Graph {
constructor(v) {
this.vertices = v;
this.edges = 0;
this.adj = [];
this.marked = [];
for(let i = 0; i < this.vertices; i++) {
this.adj[i] = [''];
this.marked[i] = false;
};
}
addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
showGraph() {
let str = '';
for(let i = 0; i < this.vertices; i++) {
str += i + '-->';
for(let j = 0; j < this.vertices; j++) {
if(this.adj[i][j] != undefined) {
str += this.adj[i][j] + ' ';
};
};
str += '\n';
};
log(str)
};
// 深度优先算法
dfs(v) {
this.marked[v] = true;
if (this.adj[v] != undefined) {
log('哪些点可以到达: ' + v);
};
(this.adj[v] || []).forEach(i => {
if(!this.marked[i]) {
this.dfs(i)
}
})
}
};
const g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.showGraph();
g.dfs(0);广度优先
广度优先从第一个顶点开始, 尝试访问尽可能靠近它的顶点. 本质上, 这种搜索在图上是逐层移动的, 首先检查最靠近第一个顶点的层, 再逐渐向下移动到离起始顶点最远层.
这里盗个图.
广度优先算法使用了抽象的队列而不是数组来对已访问过的顶点进行排序. 算法原理:
- 查找与当前顶点相邻的未访问顶点, 将其添加到已访问顶点列表及队列中.
- 从图中去除下一个顶点
v, 添加到已访问的顶点列表. - 将所有与
v相邻的未访问顶点添加到队列.
// 广度优先算法
bfs(s) {
const queue = [];
this.marked[s] = true;
queue.push(s); // 添加至队尾
while (queue.length) {
const v = queue.shift(); // 从队首删除
if (this.adj[v] != undefined) {
log('哪些点可以到达: ' + v);
};
(this.adj[v] || []).forEach(i => {
if(!this.marked[i]) {
this.marked[i] = true;
queue.push(i);
}
})
}
}查找最短路径
图最常见的操作之一就是寻找从一个顶点到另一个顶点的最短路径. 考虑下例: 假期中, 你将在两个星期时间里游历10大联盟城市, 去观看棒球比赛. 你希望通过最短路径算法, 找出开车游历这10个大联盟城市, 去观看棒球比赛. 你希望通过最短路径算法, 找出开车游历这10个城市行驶的最小里程数. 另一个最短路径问题涉及创建一个计算机网络时的开销, 其中包括两台电脑之间传递数据的时间, 或两台电脑建立和维护连接的成本. 最短路径算法可以帮助确定构建此网络的最有效方法.
广度优先对应的最短路径
在执行广度优先时, 会自动查找从一个顶点到另一个顶点的最短路径. 例如, 要查找从顶点A到顶点D的最短路径, 我们首先会查找从A到D是否有任何一条单边路径, 接着查找两条边的路径, 以此类推. 这是广度优先算法的过程, 因此我们可以轻松地修改广度优先算法, 找出最短路径.
确定路径
要查找最短路径, 需要修改广度优先算法来记录从一个顶点到另一个顶点的路径. 需要对Graph类做一些修改.
首先, 需要一个数组来保存从一个顶点到下一个顶点的所有的边. 我们将这个数组命名为edgeTo. 因为从始至终都是使用广度优先算法函数, 所以每次都会遇到一个没有标记的顶点, 除了对它进行标记外, 还会从邻接列表中我们正在探索的那个顶点添加一条边到这个顶点.
修改了bfs()方法以及在constructor()中定义edgeTo属性.
我们还需要一个函数pathTp()用于展示图中连接到不同顶点的路径. pathTo()创建一个栈, 用来存储于指定顶点有共同边的所有顶点. 以及一个简单的辅助方法: hasPathTo().
window.log = console.log.bind(console)
class Vertex {
constructor(label, wasVisited) {
this.label = label;
this.wasVisited = wasVisited;
}
};
class Graph {
constructor(v) {
this.vertices = v;
this.edges = 0;
this.edgeTo = []; // 保存从一个顶点到下一个顶点的所有边
this.adj = [];
this.marked = [];
for(let i = 0; i < this.vertices; i++) {
this.adj[i] = [''];
this.marked[i] = false;
};
}
addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
showGraph() {
let str = '';
for(let i = 0; i < this.vertices; i++) {
str += i + '-->';
for(let j = 0; j < this.vertices; j++) {
if(this.adj[i][j] != undefined) {
str += this.adj[i][j] + ' ';
};
};
str += '\n';
};
log(str)
}
// 深度优先算法
dfs(v) {
this.marked[v] = true;
if (this.adj[v] != undefined) {
log('哪些点可以到达: ' + v);
};
(this.adj[v] || []).forEach(i => {
if(!this.marked[i]) {
this.dfs(i)
}
})
}
// 广度优先算法
bfs(s) {
const queue = [];
this.marked[s] = true;
queue.push(s); // 添加至队尾
while (queue.length) {
const v = queue.shift(); // 从队首删除
if (this.adj[v] != undefined) {
log('哪些点可以到达: ' + v);
};
(this.adj[v] || []).forEach(i => {
if(!this.marked[i]) {
this.edgeTo[i] = v;
this.marked[i] = true;
queue.push(i);
}
})
}
}
// 创建一个栈 存储于指定顶点有共同边的所有顶点
pathTo(v) {
const source = 0;
if (!this.hasPathTo(v)) {
return undefined;
};
const path = [];
for (let i = v; i != source; i = this.edgeTo[i]) {
path.push(i);
};
path.push(source);
return path;
}
hasPathTo(v) {
return this.marked[v];
}
};
const g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.bfs(0);
const vertex = 4;
const paths = g.pathTo(vertex);
let res = '';
while (paths.length > 0) {
if (paths.length > 1) {
res += paths.pop() + '-';
} else {
res += paths.pop();
}
};
log(res);输出:
0-2-4
也就是从顶点0到顶点4的最短路径.
拓扑排序
拓扑排序 会对有向图的所有顶点进行排序, 使有向边从前面的顶点指向后面的顶点. eg:
-CS1
|-CS2
|-汇编语言
|-数据结构
|-操作系统
|-算法这个例子的拓扑排序将会是一下序列:
- CS1
- CS2
- 汇编语言
- 数据结构
- 操作系统
- 算法
课程3和课程4可以同时上, 课程5和课程6也可以.
这类问题被称为 优先级约束调度 , 每个大学生对此都很熟悉. 就好像只有先上过大学英语1的课程才能上大学英语2的课程一样.
拓扑排序算法
拓扑排序算法与深度优先算法类似. 不同的是, 拓扑排序算法不会立即输出已访问的顶点, 而是访问当前顶点邻接表中的所有相邻顶点, 直到这个列表穷尽时, 才将当前顶点压入栈中.
实现拓扑排序算法
拓扑排序算法被拆分为两个方法. 第一个topSort(), 会设置排序进程并调用一个辅助方法topSortHelper(), 然后显示排序号的顶点列表.
主要工作实在递归方法topSortHelper()中完成的. 这个方法会将当前顶点标记为已访问, 然后递归访问当前顶点领接表中的每个相邻顶点, 标记这些顶点为已访问. 最后 将当前顶点压入栈.
Graph类也将被修改, 这样不仅可以用于数字顶点, 还可以用于符号顶点. 在代码中, 每个顶点都只标注了数字, 但是我们添加了一个vertexList数组, 将各个顶点关联到一个符号(上面的课程名称).
下面将展示整个部分的完整定义, 包括用于拓扑排序的方法, 以确保Graph类的新的定义更清晰. showGraph()方法也将被修改, 这样可以显示符号名称而不只是显示顶点数字.
window.log = console.log.bind(console)
class Vertex {
constructor(label) {
this.label = label;
}
};
class Graph {
constructor(v) {
this.vertices = v;
this.vertexList = [];
this.edges = 0;
this.edgeTo = []; // 保存从一个顶点到下一个顶点的所有边
this.adj = [];
this.marked = [];
for(let i = 0; i < this.vertices; i++) {
this.adj[i] = [];
this.marked[i] = false;
};
}
topSort() {
const stack = [];
const visited = [];
for (let i = 0; i < this.vertices; i++) {
visited[i] = false;
};
for (let i = 0; i < this.vertices; i++) {
if (visited[i] == false) {
this.topSortHelper(i, visited, stack);
}
};
for (let i = stack.length - 1; i >= 0; i--) {
log(this.vertexList[stack[i]])
};
}
topSortHelper(v, visited, stack) {
visited[v] = true;
(this.adj[v] || []).forEach(w => {
if (!visited[w]) {
this.topSortHelper(w, visited, stack)
}
});
stack.push(v)
}
addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
showGraph() {
var visited = [];
for (let i = 0; i < this.vertices; i++) {
let str = this.vertexList[i] + '-->';
visited.push(this.vertexList[i]);
for (let j = 0; j < this.vertices; j++) {
if (this.adj[i][j] != undefined) {
if (visited.indexOf(this.vertexList[j]) < 0) {
str += this.vertexList[j] + ' ';
}
}
};
visited.pop();
log(str)
};
log(' ');
}
// 深度优先算法
dfs(v) {
this.marked[v] = true;
if (this.adj[v] != undefined) {
log('哪些点可以到达: ' + v);
};
(this.adj[v] || []).forEach(i => {
if(!this.marked[i]) {
this.dfs(i)
}
})
}
// 广度优先算法
bfs(s) {
const queue = [];
this.marked[s] = true;
queue.push(s); // 添加至队尾
while (queue.length) {
const v = queue.shift(); // 从队首删除
if (this.adj[v] != undefined) {
log('哪些点可以到达: ' + v);
};
(this.adj[v] || []).forEach(i => {
if(!this.marked[i]) {
this.edgeTo[i] = v;
this.marked[i] = true;
queue.push(i);
}
})
}
}
// 创建一个栈 存储于指定顶点有共同边的所有顶点
pathTo(v) {
const source = 0;
if (!this.hasPathTo(v)) {
return undefined;
};
const path = [];
for (let i = v; i != source; i = this.edgeTo[i]) {
path.push(i);
};
path.push(source);
return path;
}
hasPathTo(v) {
return this.marked[v];
}
};
const g = new Graph(6);
g.addEdge(1, 2);
g.addEdge(2, 5);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(0, 1);
g.vertexList = [ 'CS1', 'CS2', '数据结构', '汇编语言', '操作系统', '算法' ];
g.showGraph();
g.topSort();输出结果:
CS1--> CS2-->CS1 数据结构 汇编语言 数据结构-->CS1 CS2 汇编语言-->CS1 操作系统-->CS1 算法-->CS1 CS1 CS2 操作系统 汇编语言 数据结构 算法