该文章为清华大学数据结构与算法设计MOOC课程读书笔记.
1. 一些基本术语
1.1 邻接与关联
邻接(adjacency)：通过边相连接的两个节点之间的关系
关联(incidence)：节点与其所属的边之间的关系
1.2 有向与无向图
边是否有方向
1.3 路径(path)环路(cycle)
- 有向无环图(Directed Acyclic Graph)
- 欧拉路径(Eulerian Path)：一笔画问题，能够经过所有边一次且仅一次的环路。
- 汉密尔顿环路(Hamiltonian Tour)：能够经过所有节点一次且仅一次的环路。
2. 计算机中图的表示：邻接矩阵(adjacency matrix)
adjacency matrix
在无向图中，存在冗余，因为每条边被表示了两次
优点
缺点
3. BFS
3.1 对于图的遍历
通过某种策略对图进行遍历，可以将图转化为树结构，因此完成完全非线性结构对半线性结构的转换，简化了带求解的问题。
完全非线性->半线性->线性
3.2 策略
BFS策略
图的BFS实际上就是树的level-order遍历的推广，树的level-order遍历就是图的BFS的特例。
3.3 实现
利用Queue，节点出队列后进行访问，并且搜索邻接点。
BFS实现1
搜索到的邻接点可能是之前搜索过的或者访问过的，不需要再次访问。
BFS实现2
如果图中包含多个连通域(connected component)，需要遍历所有点，查看状态，对没有发现过的节点启动一次BFS
BFS实现-多连通域
3.4 复杂度
O(n + e) , 因为需要访问每个节点，每条边1次
3.5 BFS特性：最短路径
不用解释了吧
4. DFS
类似于树遍历中的pre-order遍历
4.1 实现
从起点开始，对所有邻接点深度优先遍历
DFS实现1
未发现的邻接节点才进行访问；已发现的邻接节点进行回溯；对于已访问的邻接节点，有直接亲子关系的为forward边，否则为cross边。
DFS实现2
4.2 性质
DFS遍历生成BFS树(森林)，可包含全图信息
DFS森林
DFS中对各节点生成的时间标签，可以在O(1)时间内提供很有用的信息，比如说是否存在直系亲子关系。
Parenthesis Lemma
5. 图遍历算法的应用
图遍历算法的应用
5.1 拓扑排序
(1) 定义
拓扑排序的结构是一个序列，该序列中的点不会通过图中的边指回序列中的前驱点。
拓扑排序
(2) 零入度算法
顺序算法：逐层(利用stack，queue都行)遍历入度为0的节点，将遍历的节点放入queue中，遍历节点的序列则为拓扑序列。
基于"BFS"
逆序算法：利用DFS得到DFS树，通过节点被visited的顺序，将其压到栈中，最后出栈节点的顺序即为拓扑序列。
原因：DFS中visited的节点顺序必然是DFS树由下而上的，这在拓扑要求中属于依赖关系靠后的节点，因此也是在序列中靠后的节点。
基于DFS
网友评论