【数据结构十一】图

图论：是数学的一个分支，以图为研究对象，研究顶点和边组成的图形的数学理论和方法。研究的主要目的是事物之间的关系，顶点代表事物，边代表两个事物间的关系。

图的术语：

顶点：

顶点：图中的一个结点。例如：顶点 0。

相邻顶点：由一条边连接在一起的顶点。例如：顶点 0 和顶点 1 是相连的，顶点 0 和顶点 1 就是相邻顶点。

顶点的度：一个顶点的度是相邻顶点的数量。例如：顶点 0 和顶点 1、顶点 3 相连，因此顶点 0 的度是 2。

出度：指向别的顶点的边的数量。

入度：指向自己的边的数量。

边：

边：顶点与顶点之间的连线。例如：顶点 0 和顶点 1 之间就有一条边。

路径：

路径：是顶点 v1、v2…vn的一个连续序列。例如：0 1 5 9 就是一条路径。

简单路径：路径中不包含重复的顶点。例如：0 1 5 9 就是一条简单路径，0 1 5 2 4 5 9 就不是一条简单路径。

回路：第一个顶点和最后一个顶点相同的路径。例如：0 1 5 6 3 0。

图：

图：是由顶点的集合和边的集合组成的，通常用 V（Vertex）表示顶点的集合，用 E（Edge）表示边的集合。

有向图：边是有方向的图。

无向图：所有的边都没有方向的图。例如：上图就是无向图，顶点 0 和顶点 1之间的边是无向的，既能从顶点 0 到顶点 1，也能从顶点 1 到顶点 0。

带权图：边带有一定权重的图，权重可以是任何希望表示的数据，比如距离或者花费的时间等等。

无权图：边没有携带权重的图。例如：上图就是无权图，因为不能说顶点 0 和顶点 3 之间的边比顶点 0 和顶点 1 之间的边更长。

生活中的图：

1. 人与人之间的关系网：可以将一个个人看作顶点，人与人之间的关系看作边。
   
2. 地铁图：可以将一个个站点看作顶点，站点与站点之间的线路看作边。

   高德地图、百度地图导航时，就用到了图去规划时间最短、线路最短等的线路。
   

3. 村庄间的关系网：可以将一个个的村庄看作顶点，村庄与村庄之间的道路看作边。
   

图的表示方法：

常见的表示图的方式有：邻接矩阵和邻接表。

邻接矩阵：

它是一个二维数组，让每个顶点和一个整数关联，该整数作为数组的下标值，数组中的元素表示两个顶点之间是否有一条边，0 表示没有边，1 表示有边。例如：[0][2] 就表示顶点 A 到顶点 C 有一条边。

A - A、B - B 等是自回路，也就是顶点到自己的连线，通常用 0 表示。

邻接矩阵的缺点：如果图是一个稀疏图，那么邻接矩阵中将存在大量的 0，这意味着浪费了计算机存储空间来表示根本不存在的边。

邻接表：

邻接表由图中的每个顶点以及和顶点相邻的顶点列表组成，以顶点作为索引，以和顶点相邻的顶点列表作为值。

邻接表的缺点：邻接表计算出度比较简单，但是计算入度就非常麻烦了，此时必须构造一个逆邻接表，才能有效地计算入度。不过，在实际开发中，使用入度相对较少。

图的遍历：

图的遍历意味着需要将图中的每个顶点访问一遍，并且不能有重复的访问。

有两种算法可以对图进行遍历：广度优先搜索、深度优先搜索。两种遍历算法都需要明确指定第一个被访问的节点。

广度优先搜索（Breadth-First Search、BFS）: 深度优先搜索（Depth-First Search、DFS）: 图的实现：

使用邻接表实现无向图。

// 封装图
function Graph() {
	// 图中的元素：顶点的集合、边的集合
	this.vertexes = []
	this.edges = new Dictionay() // 此处用到了第六章封装的字典数据结构
}

// 图中的 *** 作
// 添加顶点
Graph.prototype.addVertex = function(v) {
	this.vertexes.push(v)
	this.edges.set(v, [])
}

// 添加边
Graph.prototype.addEdge = function(v1, v2) {
	this.edges.get(v1).push(v2)
	this.edges.get(v2).push(v1)
}

// 将图结构的内容以字符串形式返回
Graph.prototype.toString = function() {
	var resultStr = ''
	for (var i = 0; i < this.vertexes.length; i++) {
		var vertexe = this.vertexes[i]
		resultStr += vertexe + ' -> ' + this.edges.get(vertexe).join(',') + '\n'
	}
	return resultStr
}

// 调用图
var graph = new Graph()
graph.addVertex('A')
graph.addVertex('B')
graph.addVertex('C')
graph.addVertex('D')
graph.addVertex('E')
graph.addVertex('F')
graph.addVertex('G')
graph.addVertex('H')
graph.addVertex('I')
graph.addEdge('A', 'B')
graph.addEdge('A', 'C')
graph.addEdge('A', 'D')
graph.addEdge('B', 'E')
graph.addEdge('B', 'F')
graph.addEdge('C', 'D')
graph.addEdge('C', 'G')
graph.addEdge('D', 'G')
graph.addEdge('D', 'H')
graph.addEdge('E', 'I')
console.log(graph.toString())