数据结构与算法（八）邻接表和邻接矩阵 & 图的深度优先广度优先遍历
[ 程序员阿沛 ](javascript:void(0);)
从本节开始，我们将介绍图这一数据结构和对应的算法，大概分3~4篇文章介绍完。目录大纲如下：
1.图的定义和表示——邻接表和邻接矩阵；
2.图的遍历——深度优先 & 广度优先；
3.图的最短路径——最短路径算法 & 多源最短路径算法；
4.图的连通性——最小生成树算法 & Union-Find并查集；
5.图节点的依赖性问题——拓扑排序；
0 1 图的定义和表示方式
图是多个顶点/节点通过多条边连接而成的网状结构，顶点之间呈多对多的关系（树节点之间则是呈一对多关系）。
树和图相比，树的节点之间是一对多的关系，并且存在父与子的层级关系；图的顶点之间是多对多的关系，并且所有顶点都是平等的。
在图中，最基本的单元是顶点（vertex），相当于树中的节点。顶点之间的关联关系，被称为边（edge）。图的种类繁多，包括无向图、有向图、带权图等。
图在的存储方式多种多样，最主要包括：邻接矩阵、邻接表、逆邻接表和十字链表。
邻接矩阵
邻接矩阵 是一个 nn二维矩阵arr，对于拥有n个顶点的图，包含的连接数量（边的数量）最多为 n(n-1)。
为什么连接数量为 n*(n-1)却需要nn大小的矩阵呢？因为 n(n-1)是每个顶点和其他顶点的关系，arr还描绘了每个顶点和自己的关系。
图中顶点0和顶点1之间有边关联，那么矩阵中的元素arr[0][1]与arr[1][0]的值就是1；顶点1和顶点2之间没有边关联，那么矩阵中的元素arr[1][2]与arr[2][1]的值就是0。
矩阵从左上到右下的一条对角线描述的就是顶点自己与自己的关联，其上的元素值必然是0，因为任何一个顶点与它自身是没有连接的。
对于一个无向图，如果 1 和 2有关联，则arr[1][2] 和 arr[2][1]都为1。对于一个有向图，如果 1 指向
2，但2不指向1，则arr[1][2]为1，arr[2][1]为0。
对于一个带权图，arr[i][j]的值就是权重，权重为0表示没有连接。
邻接矩阵的优点是快速查找两个节点的关系，时间复杂度O(1)；但占用大量空间，空间复杂度是O(n^2)。
邻接表
邻接表是一个二维数组arr，在逻辑上arr的下标代表本顶点，值存储着本顶点对应的相邻顶点。对于拥有n个顶点的图，arr的长度就为n，arr[i]存储着 i
这个节点的所有相邻节点。
邻接表默认存储有向图，如果要存储一个无向图，则需要消耗多一倍的空间。例如 1 ->
2，对于有向图而言，arr[1]内需要包含2，但arr[2]不用包含1；但对于无向图而言，邻接表将其理解为双向，因此arr[1]内需要包含2，arr[2]内也需要包含1。
邻接表的优点是节省空间，空间复杂度O(n)，缺点是查找两个顶点是否相连较慢，时间复杂度为O(n)。而且对于有向图而言，邻接表可以以O(n)复杂度找到某个顶点所指向的相邻顶点，但要找到所有指向本顶点的相邻顶点则需要遍历整个邻接表，复杂度为O(n^2)。
为了满足“找到所有指向本顶点的其他顶点”这个需求，描述一个图不仅需要维护邻接表，还需要维护逆邻接表。
逆邻接表
逆邻接表 rarr 的结构和邻接表一模一样，只是rarr[i]存储的是指向 i 自己这个顶点的所有顶点。
因此，一个图 = 邻接表 + 逆邻接表，如果没有“找到所有指向本顶点的其他顶点”这个需求，则只维护邻接表即可。
十字链表
十字链表相当于邻接表和邻接链表的结合，其物理上也是使用一个数组arr表示，但 arr[i]应该保存一个对象，该对象保存两个数组（或者两个链表）分别用来表示
i 这个顶点指向的相邻顶点，和 i 被哪些顶点指向。
下面是以邻接表实现的图（GO语言实现）
// 有向图节点type GNode struct{ Val int Neibors []*GNode // 某节点的相邻节点}
func (gnode *GNode) init(val int) GNode{ return GNode{Val: val, Neibors: make([]*GNode, 0)}}
// 以邻接表方式表示的图type Graph struct{ Pos map[*GNode]struct{} // 存储图的所有节点}
// 将n1连向n2节点（有向）func (graph *Graph) connect(n1, n2 *GNode) bool{ if _, ok := graph.Pos[n1]; !ok{ return false // n1不在graph中则返回false }
if _, ok := graph.Pos[n2]; !ok{ graph.Pos[n2] = struct{}{} // 将n2节点假如到 Graph 中 }
n1.Neibors = append(n1.Neibors, n2) return true}
02 图的遍历
图的遍历可以使用深度优先和广度优先遍历。
图的深度优先遍历主要思路是从图中一个未访问的顶点开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走，其关键在于“回溯”或者说“回退”，使用递归实现。
如下图所示：
图的广度优先遍历的主要思路在于将当前要遍历的节点A放入到一个队列，并且记录下A 节点所有的相邻的未遍历节点
到这个队列中，在这个队列中这些相邻节点被放在A节点的后面。
在遍历完A节点后，A节点就从队列中出队，然后再遍历队列中的下一个节点。在这个过程中，队列里的节点会增加或减少，直到队列中的节点为空且不再增加节点，就说明这个图的所有节点都被遍历完毕。
广度优先遍历的关键在于“重放”，目的是记录它们并找到他们的相邻节点，使用队列实现。
图的深度优先遍历和广度优先遍历 和
树的深度、广度优先遍历的实现基本一致，唯一不同的是图的多个顶点可能成环，因此需要一个hashmap或者数组记录已经访问过的顶点，避免重复访问。
直接上代码，以遍历下面这个无向图为例
深度优先遍历
// 深度优先算法遍历有向图, 以二维数组形式表示邻接表func DFSFromStart(arr [][]int, s int) []int{ visited := make(map[int]struct{}) res := make([]int, 0)
var backtrack func (start int) backtrack = func(start int) { if len(arr[start]) == 0{ // 如果某个顶点没有它所指向的相邻节点则结束本分支的遍历，转而遍历图的其他分支 return }
if _, ok := visited[start]; ok{ // 如果start节点已经遍历过，则不再遍历start和start的相邻节点 return } visited[start] = struct{}{} res = append(res, start) // 将start顶点添加到结果列表中 for _, neibor := range(arr[start]){ backtrack(neibor) // 遍历 neibor 节点做在的分支 } } backtrack(s) return res}
广度优先算法
// 广度优先算法遍历有向图, 以二维数组形式表示邻接表，数组下标就是图节点，len(arr) = 10 表示有10个图节点func BFSFromStart(arr [][]int, s int) []int{ // s表示出发节点，对于有向图而言，如果随便从某个节点出发，可能遍历不到整个图 queue := list.New() // 初始化一个队列 visited := make(map[int]struct{}) // 放入到队列之前，标记该节点为已访问，或者说标记为已放入队列 visited[s] = struct{}{} queue.PushBack(s) res := make([]int, 0)
for queue.Len() > 0{ first := queue.Front() queue.Remove(first) nodeVal := first.Value.(int) res = append(res,nodeVal)
for _, neibor := range(arr[nodeVal]){ if _, ok := visited[neibor]; ok{ // 标记为已放入队列的节点不再重复放入队列 continue } visited[neibor] = struct{}{} queue.PushBack(neibor) } } return res}
深度优先算法的应用：寻找两个顶点的所有路径
// 深度优先算法寻找两个节点的所有路径func DFSFindAllPath(arr [][]int, s, e int) [][]int{ allPath := make([][]int, 0) visited := make(map[int]struct{}) // 某条路径上已经遍历过的节点 curPath := make([]int, 0) // 当前遍历的某条路径
var backtrack func (start int) backtrack = func(start int) { // 从某个没有遍历过的节点start出发，计算到达e节点的路径的函数 curPath = append(curPath, start) visited[start] = struct{}{}
defer func(){ // 回溯 delete(visited, start) curPath = curPath[:len(curPath)-1] }()
if start == e{ // 到达终点 allPath = append(allPath, []int{}) lastPathIdx := len(allPath)-1 allPath[lastPathIdx] = append(allPath[lastPathIdx], curPath...)
// 回溯 //delete(visited, start) //curPath = curPath[:len(curPath)-1] return }
for _, neibor := range(arr[start]){ // 寻找start的所有相邻节点到终点e的路径 if _, ok := visited[neibor]; ok{ continue } backtrack(neibor) }
// 回溯 //delete(visited, start) //curPath = curPath[:len(curPath)-1] } backtrack(s) return allPath}
该算法复杂度为阶乘级别。当到达终点或者没有到达终点但是当前节点的所有节点都已经访问过则本层递归结束。
广度优先算法的应用：寻找两个顶点的最短路径
// 广度优先算法寻找两个节点的最短路径func BFSFindMinPath(arr [][]int, s, e int) []int{ queue := list.New() visited := make(map[int]int) // value为key的上一层相邻节点，当找到目标e时，要通过visited找到从s到e的路径 queue.PushBack(s) visited[s]= -1 var curVext int // 当前在遍历的顶点 found := false // 是否能找到目标节点e path := make([]int, 0)
for queue.Len() > 0{ found = false curLen := queue.Len() for i:=0; i<curLen; i++{ // 一次性将上一次的curVext的相邻顶点取出（可以看成是多叉树下 curVext的所有子节点） neiborNode := queue.Front() queue.Remove(neiborNode) curVext = neiborNode.Value.(int) if curVext == e{ found = true break }
// 将curVext的相邻节点（子节点）放入队列 for _, neibor := range(arr[curVext]){ if _, ok := visited[neibor]; ok{ continue } visited[neibor] = curVext queue.PushBack(neibor) } } if found{ break } }
if !found{ return path }
// 后序遍历visited链表获取最短路径 var iterMinPath func(start int) iterMinPath = func(start int){ if start == -1{ return } iterMinPath(visited[start]) path = append(path, start) } iterMinPath(e) return path}
该算法时间复杂度为 O(n)，空间复杂度为O(n)。
测试用例
func TestGraph(t *testing.T) { graph := [][]int{ // 邻接表表示的一个图 {1, 2, 3, 4}, {0, 4,7,9}, {0}, {0,5,6}, {0, 1,5}, {3, 4}, {3}, {1,8,10}, {7}, {1}, {7}, }
//广度优先遍历 fmt.Println(BFSFromStart(graph, 0)) //[0 1 2 3 4 7 9 5 6 8 10] // 深度优先遍历 fmt.Println(DFSFromStart(graph, 0)) //[0 1 4 5 3 6 7 8 10 9 2] // 寻找两个点间的所有路径 fmt.Println(DFSFindAllPath(graph, 1, 2)) // [[1 0 2] [1 4 0 2] [1 4 5 3 0 2]] // 寻找两个点见的最短路径 fmt.Println(BFSFindMinPath(graph, 6, 9)) // [6 3 0 1 9]}