# 图结构

TIP

图(Graph)是由顶点和连接顶点的边构成的离散结构。在计算机科学中,图是最灵活的数据结构之一,很多问题都可以使用图模型进行建模求解。例如:生态环境中不同物种的相互竞争、人与人之间的社交与关系网络、化学上用图区分结构不同但分子式相同的同分异构体、分析计算机网络的拓扑结构确定两台计算机是否可以通信、找到两个城市之间的最短路径等

# 特点

  • 一组顶点:通常用 V (Vertex)表示顶点的集合
  • 一组边:通常用 E (Edge)表示边的集合
    1. 边是顶点和顶点之间的连线
    2. 边可以是有向的,也可以是无向的。比如 A----B 表示无向,A ---> B 表示有向

# 常用术语

  • 顶点:表示图中的一个节点
  • 边:表示顶点和顶点给之间的连线
  • 相邻顶点:由一条边连接在一起的两个顶点
  • 度:一个顶点的度是相邻顶点的数量
  • 路径:
    1. 简单路径:简单路径要求不包含重复的顶点
    2. 回路:第一个顶点和最后一个顶点相同的路径称为回路
  • 无向图:图中的所有边都是没有方向的
  • 有向图:图中的所有边都是有方向的
  • 无权图:无权图中的边没有任何权重意义
  • 带权图:带权图中的边有一定的权重含义

# 表示方法

# 邻接矩阵

  • 一种表示图的常用方式
  • 可以使用二维数组来表示邻接矩阵
  • 邻接矩阵让每个节点和一个整数相关联,该整数作为数组的下标值
  • 使用一个二维数组来表示顶点之间的连接
  • 邻接矩阵的问题
    1. 如果图是一个稀疏图,那么邻接矩阵中将存在大量的 0,会造成存储空间的浪费
    2. 而且即使只有一个边, 我们也必须遍历一行来找出这个边, 也浪费很多时间

graph

上图说明

  • 二维数组中的 0 表示没有连线,1 表示有连线
  • 如:A[ 0 ][ 3 ] = 1,表示 A 和 C 之间有连接
  • 邻接矩阵的对角线上的值都为 0,表示 A - A ,B - B,等自回路都没有连接(自己与自己之间没有连接)
  • 若为无向图,则邻接矩阵应为对角线上元素全为 0 的对称矩阵
  • 上图很多 0 就会出现空间浪费

# 邻接表

  • 一种表示图的常用方式
  • 邻接表由图中每个顶点以及和顶点相邻的顶点列表组成
  • 这个列表可用多种方式存储,比如:数组/链表/字典(哈希表)等都可以
  • 邻接表的问题
    1. 邻接表计算出度是比较简单的(出度: 指向别人的数量, 入度: 指向自己的数量)
    2. 邻接表如果需要计算有向图的入度, 就必须构造一个“逆邻接表”

graph

上图说明

  • 图中可清楚看到 A 与 B、C、D 相邻
  • 假如要表示这些与 A 顶点相邻的顶点(边),可以通过将它们作为 A 的值(value)存入到对应的数组/链表/字典中
  • 之后,通过键(key)A 可以十分方便地取出对应的数据

# 代码封装

# 引入字典类和队列类

# 创建图类

// 封装图类
function Graph() {
	// 属性:顶点(数组)/边(字典)
	this.vertexes = [] // 存储顶点
	this.adjList = new Dictionay() // 存储边
}

# 添加顶点和边

思路图

  • 创建一个数组对象 vertexes 存储图的顶点
  • 创建一个字典对象 edges 存储图的边,其中 key 为顶点,value 为存储 key 顶点相邻顶点的数组

graph

代码实现

// 1. 添加顶点
Graph.prototype.addVertex = function (v) {
	this.vertexes.push(v)
	// 将边添加到字典中,新增的顶点作为键,对应的值为一个存储边的空数组
	this.edges.set(v, [])
}

// 2. 添加边:传入两个顶点为它们添加边
Graph.prototype.addEdge = function (v1, v2) {
	// 取出字典对象edges中存储边的数组,并添加关联顶点
	this.edges.get(v1).push(v2)
	// 表示的是无向表,故要添加互相指向的两条边
	this.edges.get(v2).push(v1)
}

# 转换为字符串输出

代码实现

// 3. 实现toString方法:转换为字符串输出
Graph.prototype.toString = function () {
	// 3.1 定义字符串,保存最终结果
	var resultString = ""

	// 3.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"
	}
	// 3.3 返回结果
	return resultString
}

测试

// 测试代码
var graph = new Graph()

// 1. 添加顶点
var myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
for (var i = 0; i < myVertexes.length; i++) {
	graph.addVertex(myVertexes[i])
}

// 2. 添加边
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")

// 3. 测试toString方法
console.log(graph.toString())

测试输出

A-->B  C  D
B-->A  E  F
C-->A  D  G
D-->A  C  G  H
E-->B  I
F-->B
G-->C  D
H-->D
I-->E

测试效果图

graph

# 遍历说明

图的遍历思想

算法思想在于 必须将图中所有顶点都访问一遍,并且不能有重复的访问和追踪有哪些顶点还没有被访问到

两种遍历算法

  • 广度优先搜索(Breadth - First Search,简称 BFS)
  • 深度优先搜索(Depth - First Search,简称 DFS)
  • 两种遍历算法都需要指定第一个被访问的顶点

两种算法的思想

  • BFS: 基于队列, 入队列的顶点先被探索
  • DFS: 基于栈, 通过将顶点存入栈中, 顶点是沿着路径被探索的, 存在新的相邻顶点就去访问

颜色状态

为了记录顶点是否被访问过,使用三种颜色来表示它们的状态

  • 白色:表示该顶点还没有被访问过
  • 灰色:表示该顶点被访问过,但并未完全被访问过
  • 黑色:表示该顶点被访问过,且都被访问过

颜色代码

// 4. 初始化状态颜色: 全部初始化为白色
Graph.prototype.initializeColor = function () {
	var colors = []
	for (var i = 0; i < this.vertexes.length; i++) {
		colors[this.vertexes[i]] = "white"
	}
	return colors
}

# 广度优先搜索

算法思路

  • 先宽后深的访问顶点:从指定的第一个顶点开始遍历图, 先访问其所有的相邻点, 然后一层一层遍历下去,直到遍历结束

算法图解

graph

实现思路

  • 基于队列实现广度优先搜索算法
  • 首先,创建一个队列 Q
  • 其次,将 v 标注为被发现的(灰色), 并将 v 将入队列 Q
  • 再次,如果 Q 非空, 执行下面的步骤:
    1. 将 v 从 Q 中取出队列
    2. 将 v 标注为被发现的灰色
    3. 将 v 所有的未被访问过的邻接点(白色), 加入到队列中
    4. 将 v 标志为黑色

实现代码

// 5. 实现广度优先搜索(BFS):传入指定的第一个顶点、处理结果的函数
Graph.prototype.bfs = function (initV, handler) {
	// 5.1 初始化颜色
	var colors = this.initializeColor()

	// 5.2 创建队列
	var queue = new Queue()

	// 5.3 将顶点放入队列中
	queue.enqueue(initV)

	// 5.4 循环从队列中取出元素
	while (!queue.isEmpty()) {
		// 5.4.1 从队列中取出一个顶点
		var v = queue.dequeue()

		// 5.4.2 获取和顶点相邻的另外顶点
		var vList = this.edges.get(v)

		// 5.4.3 将v的颜色设置为灰色
		colors[v] = "gray"

		// 5.4.4 遍历v所有相邻的顶点,并加入到队列中
		for (var i = 0; i < vList.length; i++) {
			var e = vList[i]
			// 判断相邻顶点是否被探测过,被探测过则不加入队列中;并且加入队列后变为灰色,表示被探测过
			if (colors[e] == "white") {
				colors[e] = "gray"
				queue.enqueue(e)
			}
		}

		// 5.4.4 访问顶点
		handler(v)

		// 5.4.5 将顶点v设置为黑色。此时黑色顶点v位于队列最前面,进入下一次while循环时会被取出
		colors[v] = "black"
	}
}

图解过程

  • 下为指定的第一个顶点为 A 时的遍历过程:
    1. 如 a 图所示,将在字典 edges 中取出的与 A 相邻的且未被访问过的白色顶点 B、C、D 放入队列 que 中并变为灰色,随后将 A 变为黑色并移出队列
    2. 如 b 图所示,将在字典 edges 中取出的与 B 相邻的且未被访问过的白色顶点 E、F 放入队列 que 中并变为灰色,随后将 B 变为黑色并移出队列
    3. 如 c 图所示,将在字典 edges 中取出的与 C 相邻的且未被访问过的白色顶点 G(A,D 也相邻不过已变为灰色,所以不加入队列)放入队列 que 中并变为灰色,随后将 C 变为黑色并移出队列
    4. 如 d 图所示,将在字典 edges 中取出的与 D 相邻的且未被访问过的白色顶点 H 放入队列 que 中并变为灰色,随后将 D 变为黑色并移出队列
  • 如此循环直到队列中元素为 0,即所有顶点都变黑并移出队列后才停止,此时图中顶点已被全部遍历

graph

测试代码

// 4. 测试bfs:调用广度优先算法
var result = ""
graph.bfs(graph.vertexes[0], function (v) {
	result += v + " -> "
})
console.log(result) // A -> B -> C -> D -> E -> F -> G -> H -> I ->

# 深度优先搜索

算法思路

  • 先深后宽的访问顶点:从指定的第一个顶点开始遍历图, 先沿着一条路径遍历直到该路径的最后一个顶点都被访问过为止,然后沿原来路径回退并探索下一条路径,直到遍历完全部节点

算法图解

graph

实现思路

  • 可以使用栈结构来实现深度优先搜索算法
  • 深度优先搜索算法的遍历顺序与二叉搜索树中的先序遍历较为相似,同样可以使用递归来实现(递归的本质就是函数栈的调用)
  • 基于递归实现深度优先搜索算法:定义 dfs 方法用于调用递归方法 dfsVisit,定义 dfsVisit 方法用于递归访问图中的各个顶点
  • 首先,在 dfs 方法中:
    1. 调用 initializeColor 方法将所有顶点初始化为白色
    2. 调用 dfsVisit 方法遍历图的顶点
  • 其次,在 dfsVisit 方法中:
    1. 将传入的指定节点 v 标注为灰色
    2. 处理顶点 V
    3. 访问 V 的相邻顶点
    4. 将顶点 v 标注为黑色

实现代码

// 6. 实现深度优先搜索(DFS):传入指定的第一个顶点、处理结果的函数
Graph.prototype.dfs = function (initV, handler) {
	// 6.1 初始化颜色
	var colors = this.initializeColor()

	// 6.2 从某个顶点开始依次递归访问
	this.dfsVisit(initV, colors, handler)
}
// 递归访问方法,传入三个参数分别表示:指定的第一个顶点、颜色、处理函数
Graph.prototype.dfsVisit = function (v, colors, handler) {
	// a. 将颜色设置为灰色
	colors[v] = "gray"

	// b. 处理v顶点
	handler(v)

	// c. 访问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)
		}
	}

	// d. 将v设置为黑色
	colors[v] = "black"
}

图解过程

  • 下为代码中的第 c 步操作:访问指定顶点的相邻顶点:
    1. 以指定顶点 A 为例,先从储存顶点及其对应相邻顶点的字典对象 edges 中取出由顶点 A 的相邻顶点组成的数组[B, C, D]
    2. 第一步:A 顶点变为灰色,随后进入第一个 for 循环,遍历 A 白色的相邻顶点:B、C、D;在该 for 循环的第 1 次循环中(执行 B),B 顶点满足:colors == "white",触发递归,重新调用该方法
    3. 第二步:B 顶点变为灰色,随后进入第二个 for 循环,遍历 B 白色的相邻顶点:E、F;在该 for 循环的第 1 次循环中(执行 E),E 顶点满足:colors == "white",触发递归,重新调用该方法
    4. 第三步:E 顶点变为灰色,随后进入第三个 for 循环,遍历 E 白色的相邻顶点:I;在该 for 循环的第 1 次循环中(执行 I),I 顶点满足:colors == "white",触发递归,重新调用该方法
    5. 第四步:I 顶点变为灰色,随后进入第四个 for 循环,由于顶点 I 的相邻顶点 E 不满足:colors == "white",停止递归调用
    6. 递归结束后一路向上返回,首先回到第三个 for 循环中继续执行其中的第 2、3...次循环,每次循环的执行过程与上面的同理,直到递归再次结束后,再返回到第二个 for 循环中继续执行其中的第 2、3...次循环....以此类推直到将图的所有顶点访问完为止

graph

完整遍历过程

  • 发现 表示访问了该顶点,状态变为灰色
  • 探索 表示既访问了该顶点,也访问了该顶点的全部相邻顶点,状态变为黑色
  • 由于在顶点变为灰色后就调用了处理函数 handler,所以 handler 方法的输出顺序为发现顶点的顺序即:A、B、E、I、F、C、D、G、H

graph

测试代码

// 5. 测试dfs:调用深度优先算法
result = ""
graph.dfs(graph.vertexes[0], function (v) {
	result += v + " -> "
})
console.log(result) // A -> B -> E -> I -> F -> C -> D -> G -> H ->

# 完整代码

// 封装图类
function Graph() {
	// 属性:顶点(数组)/边(字典)
	this.vertexes = [] // 存储顶点
	this.edges = new Dictionay() // 存储边

	/* 方法 */
	// 1. 添加顶点
	Graph.prototype.addVertex = function (v) {
		this.vertexes.push(v)
		// 将边添加到字典中,新增的顶点作为键,对应的值为一个存储边的空数组
		this.edges.set(v, [])
	}

	// 2. 添加边:传入两个顶点为它们添加边
	Graph.prototype.addEdge = function (v1, v2) {
		// 取出字典对象edges中存储边的数组,并添加关联顶点
		this.edges.get(v1).push(v2)
		// 表示的是无向表,故要添加互相指向的两条边
		this.edges.get(v2).push(v1)
	}

	// 3. 实现toString方法:转换为字符串输出
	Graph.prototype.toString = function () {
		// 3.1 定义字符串,保存最终结果
		var resultString = ""

		// 3.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"
		}
		// 3.3 返回结果
		return resultString
	}

	// 4. 初始化状态颜色: 全部初始化为白色
	Graph.prototype.initializeColor = function () {
		var colors = []
		for (var i = 0; i < this.vertexes.length; i++) {
			colors[this.vertexes[i]] = "white"
		}
		return colors
	}

	// 5. 实现广度优先搜索(BFS):传入指定的第一个顶点、处理结果的函数
	Graph.prototype.bfs = function (initV, handler) {
		// 5.1 初始化颜色
		var colors = this.initializeColor()

		// 5.2 创建队列
		var queue = new Queue()

		// 5.3 将顶点放入队列中
		queue.enqueue(initV)

		// 5.4 循环从队列中取出元素
		while (!queue.isEmpty()) {
			// 5.4.1 从队列中取出一个顶点
			var v = queue.dequeue()

			// 5.4.2 获取和顶点相邻的另外顶点
			var vList = this.edges.get(v)

			// 5.4.3 将v的颜色设置为灰色
			colors[v] = "gray"

			// 5.4.4 遍历v所有相邻的顶点,并加入到队列中
			for (var i = 0; i < vList.length; i++) {
				var e = vList[i]
				// 判断相邻顶点是否被探测过,被探测过则不加入队列中;并且加入队列后变为灰色,表示被探测过
				if (colors[e] == "white") {
					colors[e] = "gray"
					queue.enqueue(e)
				}
			}

			// 5.4.4 访问顶点
			handler(v)

			// 5.4.5 将顶点v设置为黑色。此时黑色顶点v位于队列最前面,进入下一次while循环时会被取出
			colors[v] = "black"
		}
	}

	// 6. 实现深度优先搜索(DFS):传入指定的第一个顶点、处理结果的函数
	Graph.prototype.dfs = function (initV, handler) {
		// 6.1 初始化颜色
		var colors = this.initializeColor()

		// 6.2 从某个顶点开始依次递归访问
		this.dfsVisit(initV, colors, handler)
	}
	// 递归访问方法,传入三个参数分别表示:指定的第一个顶点、颜色、处理函数
	Graph.prototype.dfsVisit = function (v, colors, handler) {
		// a. 将颜色设置为灰色
		colors[v] = "gray"

		// b. 处理v顶点
		handler(v)

		// c. 访问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)
			}
		}

		// d. 将v设置为黑色
		colors[v] = "black"
	}
}

// 测试代码
var graph = new Graph()

// 1. 添加顶点
var myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
for (var i = 0; i < myVertexes.length; i++) {
	graph.addVertex(myVertexes[i])
}

// 2. 添加边
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")

// 3. 测试toString方法
console.log(graph.toString())

// 4. 测试bfs:调用广度优先算法
var result = ""
graph.bfs(graph.vertexes[0], function (v) {
	result += v + " -> "
})
console.log(result) // A -> B -> C -> D -> E -> F -> G -> H -> I ->

// 5. 测试dfs:调用深度优先算法
result = ""
graph.dfs(graph.vertexes[0], function (v) {
	result += v + " -> "
})
console.log(result) // A -> B -> E -> I -> F -> C -> D -> G -> H ->