图

图是由边和点组成。一条边连接的两个点称为相邻顶点。

图可以是无向的也可以是有向的。本文探讨的都是无向图。

图的表示

图一般有以下两种实现方法： 1. 邻接矩阵：使用二维数组来表示点与点之间是否有边，如arr[i][j]=1则表示节点i与节点j之间有边，如果arr[i][j]=0则表示节点i与节点j之间没有边。 2. 邻接表：使用数组或字典结构来表示与节点i之间有边的节点集合：如arr[i]=[j,k,l,,m]，表示为节点i与其中的这些点都有边

本文采用邻接表方式来实现图结构，邻接表则采用字典方式来表示，而字典可以通过map结构来表示，但是map结构属于ES6，所以本文采用对象方式来表示字典。

创建图类

下面声明图类，其中顶点结合采用数组结构表示，边集合采用对象结构表示（也可以使用ES6的map结构）。

function Graph(){ var vertices=[];//顶点集合 var adjList={};//边 this.addVertex=function(v){...};//添加顶点方法 this.addEdge=function(v,w){...};//添加边方法 this.toString=function(){...};//显示方法 this.dfs=function(){...} this.bfs=function(v){...} }

添加结点方法：顶点集合中添加节点，并生成节点的邻接表。

this.addVertex=function(v){ vertices.push(v); adjList[v]=[]; };

添加边方法：在对应点的邻接表中添加对方，表示双方之间有边。

this.addEdge=function(v,w){ adjList[v].push(w); adjList[w].push(v); };

显示方法：输出形式为节点 -> 相邻的节点

this.toString=function(){ var s = ''; for (var i=0; i<vertices.length; i++){ s += vertices[i] + ' -> '; var neighbors = adjList[vertices[i]]; for (var j=0; j<neighbors.length; j++){ s += neighbors[j] + ' '; } s += '\n'; } return s; };

使用方法：

var graph = new Graph(); var myVertices = [0,1,2,3,4,5]; for (var i=0; i<myVertices.length; i++){ graph.addVertex(myVertices[i]); } graph.addEdge(0, 1); //增加边 graph.addEdge(0, 4); graph.addEdge(0, 5); graph.addEdge(1, 4); graph.addEdge(1, 3); graph.addEdge(2, 3); graph.addEdge(2, 5); console.log(graph.toString()) /* 0 -> 1 4 5 1 -> 0 4 3 2 -> 3 5 3 -> 1 2 4 -> 0 1 5 -> 0 2 */

图的遍历

遍历图的方法有： 1. 深度优先遍历 2. 广度优先遍历

深度优先遍历

深度优先搜索算法将会从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶 点被访问了，接着原路回退并探索下一条路径。

步骤： 1. 访问顶点v 2. 标记v为false 3. 对于v的所有未访问的邻点w： 1. 访问顶点w 2.w的flag不为true，则访问其邻点

this.dfs=function(){ var flag=[]; for(var i=0;i<vertices.length;i++){ if(!flag[vertices[i]]){ dfsVisit(vertices[i]) } } function dfsVisit(u){ flag[u]=true; console.log(u); var neighbors=adjList[u]; for(var i=0;i<neighbors.length;i++){ var w=neighbors[i]; if(!flag[w]){ dfsVisit(w) } } } }

使用方法：

graph.dfs(); /* 0 1 4 3 2 5 */

广度优先遍历

从指定的第一个顶点开始遍历图，先访问其所有的相邻点。 步骤： 1. 创建一个队列 2. 将指定顶点放入队列中，将其flag设为true 3. 如果队列非空，则执行以下步骤： 1. 取出队列中第一个元素 2. 判断其元素的相邻的节点flag，如果不是true，放入队列中，并更改其flag

this.bfs=function(v){ var queue=[],//队列 flag=[];//标记是否访问过 flag[v]=true; queue.push(v); while(queue.length!==0){ var n=queue.shift(),neighbors=adjList[n]; for(var i=0;i<neighbors.length;i++){ var w = neighbors[i]; if(!flag[w]){ flag[w]=true; queue.push(w) } } console.log(n); } }

使用方法：

graph.bfs(myVertices[0]) /* 0 1 4 5 3 2 */