javascript 图(Graphs)算法与说明

图的介绍

图是网络结构的抽象模型。图是一组由边连接的节点（或顶点）。学习图是重要的，因为任何二元关系都可以用图来表示。

任何社交网络，例如Facebook、Twitter和Google plus，都可以用图来表示。

飞机路线图就是图的实例之一：

图的相关术语

通过下图来讲解说明：

相邻顶点：由一条边连接在一起的顶点。比如，A和B是相邻的，A和D是相邻的，A和C是相邻的，A和E不是相邻的。
度：一个顶点相邻顶点的数量。比如，A和其他三个顶点相连接。因此，A的度为3；Eh 饿其他连个顶点相连。因此，E的度为2。
路径：顶点v1连续序列。如ABEI和ACDG。简单路径要求不包含重复的顶点。比如，ADG就是一条简单路径。
环：简单路径ADCA。如果途中不存在环，则称该图是无环。如果途中每两个顶点间都存在路径，则该图是连通的。
无向图：图有方向的。如下图：

图的算法实例

var graph = new Graph();var myVertices = ['A','B','C','D','E','F','G','H','I'];for (var i=0; i<myVertices.length; i++){graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');
<!-- A -> B C D B -> E F C -> D G D -> G H E -> I F -> G -> H -> I -> 
-->function printNode(value){console.log('Visited vertex: ' + value);
}
graph.bfs(myVertices[0], printNode);
<!-- Visited vertex: AVisited vertex: BVisited vertex: CVisited vertex: DVisited vertex: EVisited vertex: FVisited vertex: GVisited vertex: HVisited vertex: I
-->graph.dfs();
<!-- Discovered ADiscovered BDiscovered EDiscovered Iexplored Iexplored EDiscovered Fexplored Fexplored BDiscovered CDiscovered DDiscovered Gexplored GDiscovered Hexplored Hexplored Dexplored Cexplored A
-->var shortestPathA = graph.BFS(myVertices[0]);var fromVertex = myVertices[0];for (i=1; i<myVertices.length; i++){var toVertex = myVertices[i],path = new Stack();for (var v=toVertex; v!== fromVertex; v=shortestPathA.predecessors[v]) {path.push(v);}path.push(fromVertex);var s = path.pop();while (!path.isEmpty()){s += ' - ' + path.pop();}console.log(s);
}
<!-- A - BA - CA - DA - B - EA - B - FA - C - GA - D - HA - B - E - I
-->var result = graph.DFS();var fTimes = result.finished;
s = '';
for (var count=0; count<myVertices.length; count++){var max = 0;var maxName = null;for (i=0; i<myVertices.length; i++){if (fTimes[myVertices[i]] > max){max = fTimes[myVertices[i]];maxName = myVertices[i];}}s += ' - ' + maxName;delete fTimes[maxName];
}
console.log(s);
// - B - A - D - C - F - E

ES6图完整实现代码：

let Graph = (function() {
    class Graph {
    constructor() {this.vertices = [];this.adjList = new Dictionary();this.time = 0;}addVertex(v) {
   //增加节点this.vertices.push(v);this.adjList.set(v, []); };addEdge(v, w) {
   //连接路径this.adjList.get(v).push(w);};toString() {
   //转为string返回var s = '';for(var i = 0; i < this.vertices.length; i++) {s += this.vertices[i] + ' -> ';var neighbors = this.adjList.get(this.vertices[i]);for(var j = 0; j < neighbors.length; j++) {s += neighbors[j] + ' ';}s += '\n';}return s;};initializeColor() {
   //var color = {};for(var i = 0; i < this.vertices.length; i++) {color[this.vertices[i]] = 'white';}return color;};bfs(v, callback) {var color = this.initializeColor(),queue = new Queue();queue.enqueue(v);while(!queue.isEmpty()) {var u = queue.dequeue(),neighbors = this.adjList.get(u);color[u] = 'grey';for(var i = 0; i < neighbors.length; i++) {var w = neighbors[i];if(color[w] === 'white') {color[w] = 'grey';queue.enqueue(w);}}color[u] = 'black';if(callback) {callback(u);}}};dfs(callback) {var color = this.initializeColor();for(var i = 0; i < this.vertices.length; i++) {if(color[this.vertices[i]] === 'white') {this.dfsVisit(this.vertices[i], color, callback);}}};dfsVisit(u, color, callback) {color[u] = 'grey';if(callback) {callback(u);}console.log('Discovered ' + u);var neighbors = this.adjList.get(u);for(var i = 0; i < neighbors.length; i++) {var w = neighbors[i];if(color[w] === 'white') {this.dfsVisit(w, color, callback);}}color[u] = 'black';console.log('explored ' + u);};BFS(v) {
   //广度优先搜索var color = this.initializeColor(),queue = new Queue(),d = {},pred = {};queue.enqueue(v);for(var i = 0; i < this.vertices.length; i++) {d[this.vertices[i]] = 0;pred[this.vertices[i]] = null;}while(!queue.isEmpty()) {var u = queue.dequeue(),neighbors = this.adjList.get(u);color[u] = 'grey';for(i = 0; i < neighbors.length; i++) {var w = neighbors[i];if(color[w] === 'white') {color[w] = 'grey';d[w] = d[u] + 1;pred[w] = u;queue.enqueue(w);}}color[u] = 'black';}return {distances: d,predecessors: pred};};DFS() {
   //深度优先搜索var color = this.initializeColor(),d = {},f = {},p = {};this.time = 0;for(var i = 0; i < this.vertices.length; i++) {f[this.vertices[i]] = 0;d[this.vertices[i]] = 0;p[this.vertices[i]] = null;}for(i = 0; i < this.vertices.length; i++) {if(color[this.vertices[i]] === 'white') {this.DFSVisit(this.vertices[i], color, d, f, p);}}return {discovery: d,finished: f,predecessors: p};};DFSVisit(u, color, d, f, p) {console.log('discovered ' + u);color[u] = 'grey';d[u] = ++this.time;var neighbors = this.adjList.get(u);for(var i = 0; i < neighbors.length; i++) {var w = neighbors[i];if(color[w] === 'white') {p[w] = u;this.DFSVisit(w, color, d, f, p);}}color[u] = 'black';f[u] = ++this.time;console.log('explored ' + u);};}return Graph;
})()