day25

图

a 图

a1 概述：邻接，相关

之前学习到vector，tree都是图的特例；

a2 有向/无向图

可以通过有向图表示无向图或混合图，技巧是将无向边转化为彼此对称的一对有向边。

a3 路径 环路

所有的环路中比较有意思的两种：如图（i）经过所有的边一次且恰好一次，（ii）经过每个顶点一次且恰好一次
有向无环图（DAG）不包含有向环的有向图就是有向无环图

b

b1-1 邻接矩阵-接口

b1-2 邻接矩阵与关联矩阵

关联矩阵行为顶点，列为边，每一列只有两个位置是1，其余位置都是0

b1-3 实例

b1-4 顶点和边

b1-5 邻接矩阵

顶点集，边集（即邻接矩阵）

b1-6 顶点静态操作

b1-7 边操作

b1-8 顶点动态操作

上述代码有误，需要在第4、8行加上代码e–(边数减一)

b1-9 综合评价

对邻接矩阵表示法的综合评价
具体证明方法参考教材练习中的6-3题

c搜索

c1 BFS化繁为简

c2 策略

树的层次遍历是图的广度优先搜索的特例

c3 实现

分别处理见下一节

c4 可能情况

c5 实例

最后去掉cross edge，可以得到一棵树（右下图）

c6 多连通

如何实现对多个连通域的统一遍历，每一个连通域启动且只启动一次广度优先搜索

c7 复杂度

对前面BFS代码的复杂度分析

c8 最短路径

对于无权图的BFS遍历，如上图右，每个节点与S节点的那一条通路，恰好对应于原图中这两个节点间的最短通路。证明见习题6-7

d 深度优先搜索

d1 DFS算法

d2 DFS框架

d3 细节

d4 无向图

见视频

d5 有向图

详见视频

d6 多可达域

d7 嵌套引理

完成代码，开始第七章