目录
一、初识图结构
1.什么是图
????????图是一种与树有些相似的数据结构，实际上，在数学的概念上，树是图的一种。
树可以用来模拟很多现实的数据结构，比如: 家谱、公司组织架构等等。同时，可以使用地铁地图来模拟图：
????????上面的结点(其实图中叫顶点Vertex)之间的关系，是不能使用树来表示(几叉树都不可以)，这个时候，就可以使用图来模拟它们。
2.图的特点
一组顶点：通常用 V (Vertex) 表示顶点的集合
一组边：通常用 E (Edge) 表示边的集合
边是顶点和顶点之间的连线
边可以是有向的，也可以是无向的。(比如A --- B，通常表示无向。 A --> B，通常表示有向)
? 3.图的术语
下图是一个抽象出来的图：
? ? ? ? (1).顶点
????????顶点表示图中的一个结点。
????????比如地铁站中某个站、多个村庄中的某个村庄、互联网中的某台主机、人际关系中的人。
? ? ? ? (2).边
????????边表示顶点和顶点之间的连线。
????????比如地铁站中两个站点之间的直接连线，就是一个边。
????????注意: 这里的边不要叫做路径，路径有其他的概念
????????在上面的图中: 0 - 1有一条边, 1 - 2有一条边, 0 - 2没有边.
? ? ? ? (3).相邻顶点
????????由一条边连接在一起的顶点称为相邻顶点。
????????比如0 - 1是相邻的, 0 - 3是相邻的. 0 - 2是不相邻的
? ? ? ? (4).度
????????一个顶点的度是相邻顶点的数量。
比如0顶点和其他两个顶点相连, 0顶点的度是2
比如1顶点和其他四个顶点相连, 1顶点的度是4
? ? ? ? (5).路径
????????路径是顶点v1, v2..., vn的一个连续序列，比如上图中0 1 5 9就是一条路径.
???1.简单路径: 简单路径要求不包含重复的顶点. 比如 0 1 5 9是一条简单路径.
? ?2.回路: 第一个顶点和最后一个顶点相同的路径称为回路. 比如 0 1 5 6 3 0
? ? ? ? (6).无向图
????????上面的图就是一张无向图，因为所有的边都没有方向。
比如 0 - 1之间有变, 那么说明这条边可以保证 0 -> 1, 也可以保证 1 -> 0.
? ? ? ? (7).有向图
????????有向图表示的图中的边是有方向的。
比如 0 -> 1, 不能保证一定可以 1 -> 0, 要根据方向来定.
? ? ? ? (8).无权图和带权图
? ? ? ? 1.无权图
????????上面的图就是一张无权图(边没有携带权重)
我们上面的图中的边是没有任何意义的, 不能收 0 - 1的边, 比4 - 9的边更远或者用的时间更长.
? ? ? ? 2.带权图
????????带权图表示边有一定的权重。
这里的权重可以是任意希望表示的数据，比如距离或者花费的时间或者票价.
下图是一张有向和带权的图：
二. 图的表示
????????一个图包含很多顶点，另外包含顶点和顶点之间的连线(边)，这两个都是非常重要的图信息。
? 1.顶点表示
????????顶点的表示相对简单，上面的顶点抽象成了1 2 3 4, 也可以抽象成A B C D。这些A B C D可以使用一个数组来存储起来(存储所有的顶点)。当然, A, B, C, D有可能还表示其他含义的数据(比如地铁站的名字)，这个时候，可以另外创建一个数组，用于存储对应的其他数据.
? 2.邻接矩阵
????????邻接矩阵让每个节点和一个整数相关联，该整数作为数组的下标值。用一个二维数组来表示顶点之间的连接
在二维数组中，0表示没有连线，1表示有连线。
通过二维数组，可以很快的找到一个顶点和哪些顶点有连线。(比如A顶点, 只需要遍历第一行即可)
另外, A - A, B - B(也就是顶点到自己的连线), 通常使用0表示.
邻接矩阵的问题:
????????如果是一个无向图, 邻接矩阵展示出来的二维数组, 其实是一个对称图。也就是A -> D是1的时候, 对称的位置 D -> 1一定也是1。
????????邻接矩阵还有一个比较严重的问题就是如果图是一个稀疏图，那么矩阵中将存在大量的0, 这意味着浪费了计算机存储空间来表示根本不存在的边，而且即使只有一个边, 也必须遍历一行来找出这个边, 也浪费很多时间.
? 3.邻接表
????????邻接表由图中每个顶点以及和顶点相邻的顶点列表组成，这个列表有很多中方式来存储: 数组/链表/字典(哈希表)等等
????????要表示和A顶点有关联的顶点(边), A和B/C/D有边, 那么可以通过A找到对应的数组/链表/字典, 再取出其中的内容就可以。
邻接表的问题:
????????邻接表计算"出度"是比较简单的(出度: 指向别人的数量, 入度: 指向自己的数量)。邻接表如果需要计算有向图的"入度"，是比较麻烦的。必须构造一个"“逆邻接表", 才能有效的计算"入度"。
三. 图结构的实现
? 1.封装图结构
//封装图结构
function Graph(){
//属性：顶点（数组）/边（字典）
this.vertexes = [] //顶点
this.edges = new Dictionay() //边
}
创建Graph的构造函数，定义两个属性:
vertexes: 用于存储所有的顶点, 我们说过使用一个数组来保存.
adjList: adj是adjoin的缩写, 邻接的意思. adjList用于存储所有的边, 这里采用邻接表的形式.
? 2.添加顶点的方法
? ? ? ? 向图中添加一些顶点
//1.添加顶点的方法
Graph.prototype.addVertex = function(v){
this.vertexes.push(v)
this.edges.set(v,[])
}将添加的顶点放入到数组中，另外，给该顶点创建一个数组[ ], 该数组用于存储顶点连接的所有的边
? 3.添加边的方法
//2.添加边的方法
Graph.prototype.addEdge = function(v1,v2){
this.edges.get(v1).push(v2)
this.edges.get(v2).push(v1)
}添加边需要传入两个顶点, 因为边是两个顶点之间的边, 边不可能单独存在.
根据顶点v取出对应的数组, 将w加入到它的数组中.
根据顶点w取出对应的数组, 将v加入到它的数组中.
这里实现的是无向图, 所以边是可以双向的.
测试代码：
//测试代码
//1.创建图结构
var g = new Graph()
//2.添加顶点
var myVertexes = ['A','B','C','D','E','F','G','H','I']
for(var i=0; i<myVertexes.length; i++){
g.addVertex(myVertexes[i])
}
//3.添加边
g.addEdge('A','B')
g.addEdge('A','C')
g.addEdge('A','D')
g.addEdge('C','D')
g.addEdge('C','G')
g.addEdge('D','G')
g.addEdge('D','H')
g.addEdge('B','E')
g.addEdge('B','F')
g.addEdge('E','I')
//测试
alert(g)
? 4.toString()方法
//实现toString方法
Graph.prototype.toString = function(){
//1.定义字符串，保存最终的结果
var resultString = ''
//2.遍历所有的节点，以及顶点对应的边
for(var i =0; i<this.vertexes.length; i++){
resultString += this.vertexes[i] + "->"
var vEdges = this.edges.get(this.vertexes[i])
for(var j=0; j<vEdges.length; j++){
resultString += vEdges[j] + ' '
}
resultString += '\n'
}
return resultString
}
四、图的遍历?
? 1.遍历的方式
? ? ? ? (1).图的遍历思想
????????图的遍历算法的思想在于必须访问每个第一次访问的节点, 并且追踪有哪些顶点还没有被访问到。有两种算法可以对图进行遍历：广度优先搜索(Breadth-First Search, 简称BFS)、深度优先搜索(Depth-First Search, 简称DFS)
????????两种遍历算法, 都需要明确指定第一个被访问的顶点。
? ? ? ? (2).遍历的注意点
????????对于每一条所连接的没有被访问过的顶点, 将其标注为被发现的, 并将其加进待访问顶点列表中。为了保证算法的效率: 每个顶点至多访问两次。
? ? ? ? (3).两种算法的思想
BFS: 基于队列, 入队列的顶点先被探索.
DFS: 基于栈, 通过将顶点存入栈中, 顶点是沿着路径被探索的, 存在新的相邻顶点就去访问.
为了记录顶点是否被访问过, 我们使用三种颜色来反应它们的状态:(或者两种颜色也可以)
白色: 表示该顶点还没有被访问
灰色: 表示该顶点被访问过, 但并未被探索过
黑色: 表示该顶点被访问过且被完全探索过
初始化颜色代码:
//初始化状态颜色
Graph.prototype.initializeColor = function(){
var colors = []
for(var i=0; i<this.vertexes.length; i++){
colors[this.vertexes[i]] = 'white'
}
return colors
}
? 2.广度优先搜索
? ? ? ? (1).广度优先搜索算法的思路
????????广度优先算法会从指定的第一个顶点开始遍历图, 先访问其所有的相邻点, 就像一次访问图的一层。换句话说, 就是先宽后深的访问顶点。
? ? ? ? (2).广度优先搜索的实现
//实现广度优先搜索
Graph.prototype.bfs = function (initV, handler) {
//1.初始化颜色
var colors = this.initializeColor()
//2.创建队列
var queue = new Queue()
//3.将顶点加入到队列中
queue.enqueue(initV)
//4.循环从队列中取出元素
while (!queue.isEmpty()) {
//4.1.从队列中取出一个顶点
var v = queue.dequeue()
//4.2.获取和顶点相连的另外顶点
var vList = this.edges.get(v)
//4.3.将v的颜色设置为灰色
colors[v] = 'gray'
//4.4遍历所有的顶点，并且加入到队列
for (var i = 0; i < vList.length; i++) {
var e = vList[i]
if (colors[e] == 'white') {
colors[e] = 'gray'
queue.enqueue(e)
}
}
//4.5访问顶点
handler(v)
//4.6.将顶点设置为黑色
colors[v] = 'black'
}
}
测试代码:
// 调用广度优先算法
var result = ""
graph.bfs(graph.vertexes[0], function (v) {
result += v + " "
})
alert(result) // A B C D E F G H I
? 3.深度优先搜索
????????(1).深度优先搜索的思路
????????深度优先搜索算法将会从第一个指定的顶点开始遍历图, 沿着路径知道这条路径最后被访问了.
接着原路回退并探索吓一条路径。
?
????????(2).深度优先搜索算法的实现
????????广度优先搜索算法使用的是队列，在这里可以使用栈完成，也可以使用递归。为了方便代码书写，使用递归完成(递归本质上就是函数栈的调用)
//深度优先搜索（DFS）
Graph.prototype.dfs = function(initV,handler){
//1.初始化颜色
var colors = this.initializeColor()
//2.从某个顶点开始依次递归访问
this.dfsVisit(initV,colors,handler)
}
Graph.prototype.dfsVisit = function(v,colors,handler){
//1.将颜色设置为灰色
colors[v] = 'gray'
//2.处理v节点
handler(v)
//3.访问v相连的顶点
var vlist = this.edges.get(v)
for(var i=0; i < vlist.length; i++){
var e = vlist[i]
if(colors[e] == 'white'){
this.dfsVisit(e,colors,handler)
}
}
//4.将v设置为黑色
colors[v]='black'
}测试代码：
//调用深度优先算法
result = ''
g.dfs(g.vertexes[0],function(v){
result += v + ' '
})
alert(result)递归过程：?
?