2018-09-25前端面试必备——图
图
图是由边和点组成。一条边连接的两个点称为相邻顶点。
图可以是无向的也可以是有向的。本文探讨的都是无向图。
图一般有以下两种实现方法：
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结构）。
functionGraph(){varvertices=[];//顶点集合varadjList={};//边this.addVertex=function(v){...};//添加顶点方法this.addEdge=function(v,w){...};//添加边方法this.toString=function(){...};//显示方法this.dfs=function(){...}this.bfs=function(v){...}}
1
2
3
4
5
6
7
8
9
添加结点方法：顶点集合中添加节点，并生成节点的邻接表。
this.addVertex=function(v){vertices.push(v); adjList[v]=[];};
1
2
3
4
添加边方法：在对应点的邻接表中添加对方，表示双方之间有边。
this.addEdge=function(v,w){adjList[v].push(w); adjList[w].push(v);};
1
2
3
4
显示方法：输出形式为节点 -> 相邻的节点
this.toString=function(){vars ='';for(vari=0; i
1
2
3
4
5
6
7
8
9
10
11
12
13
使用方法：
vargraph =newGraph();varmyVertices = [0,1,2,3,4,5];for(vari=0; i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
遍历图的方法有：
1. 深度优先遍历
2. 广度优先遍历
深度优先搜索算法将会从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶
点被访问了，接着原路回退并探索下一条路径。
步骤：
1. 访问顶点v
2. 标记v为false
3. 对于v的所有未访问的邻点w：
1. 访问顶点w
2.w的flag不为true，则访问其邻点
this.dfs=function(){var flag=[];for(vari=0;i
if(!flag[vertices[i]]){
dfsVisit(vertices[i])
}}functiondfsVisit(u){flag[u]=true;console.log(u); var neighbors=adjList[u];for(vari=0;i
var w=neighbors[i];
if(!flag[w]){
dfsVisit(w)
}} }}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
使用方法：
graph.dfs();/*
0
1
4
3
2
5
*/
1
2
3
4
5
6
7
8
9
从指定的第一个顶点开始遍历图，先访问其所有的相邻点。
步骤：
1. 创建一个队列
2. 将指定顶点放入队列中，将其flag设为true
3. 如果队列非空，则执行以下步骤：
1. 取出队列中第一个元素
2. 判断其元素的相邻的节点flag，如果不是true，放入队列中，并更改其flag
this.bfs=function(v){varqueue=[],//队列flag=[];//标记是否访问过flag[v]=true; queue.push(v);while(queue.length!==0){varn=queue.shift(),neighbors=adjList[n];for(vari=0;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
使用方法：
graph.bfs(myVertices[0])/*
0
1
4
5
3
2
*/
