第7讲 图的基本概念、存储、遍历、拓扑排序

1. 图的基本概念
   (1) 有向图、无向图
   (2) 度数（出度、入度）
   (3) 简单图：不存在顶点到其自身的边，且同一条边不重复出现
   (4) 路径、环、简单路径
   (5) 无向完全图：任意两个顶点之间都存在边，有n个顶点的无向完全图有 n × (n - 1) / 2条边
   (6) 有向完全图：任意两个顶点之间都存在方向护卫相反的两条弧，有n个顶点的无向完全图有 n × (n - 1) 条弧
   (7) 稀疏图&稠密图：有很少条边或弧的图称为稀疏图，反之称为稠密图，相对的概念。

图的存储及基本操作

• 邻接矩阵：适用于稠密图，可存有向图、无向图。常用。空间复杂度：O(n^2)。无法存重边。

• 邻接表：适用于稀疏图，可存有向图、无向图。常用。空间复杂度：O(n + m)。可存重边。

  （开一个单链表，存该点可以到附近一步到的点。）
  * 邻接多重表，适用于稀疏图，可存无向图。不常用。空间复杂度：O(n + m)。可存重边。

  （邻接表存储图的优化，这样就可以找一条边的反向边）

• 十字链表，适用于稀疏图，可存有向图、无向图。不常用。空间复杂度：O(n + m)。无法存重边

（对邻接矩阵做的优化）

• 三元组表，适用于稀疏图，可存有向图，无向图。常用于Bellman-Ford算法、Kruskal算法。空间复杂度：O(m)。可存重边。

  （例：写法（1,2,3）1和2是一条边连接的两个点，3是权值）

图的遍历

(1) 深度优先搜索。邻接表存储的时间复杂度：O(n + m)。邻接矩阵存储的时间复杂度：O(n^2)
(2) 广度优先搜索。邻接表存储的时间复杂度：O(n + m)。邻接矩阵存储的时间复杂度：O(n^2)

拓扑排序

• 不一定所有的图都有拓扑排序，有环的图就没有拓扑排序（无环就有）。遍历完之后，判断所有点是不是都被遍历过，若都被遍历过那就有拓扑排序，还有点没有被遍历过就没有拓扑序列。
• 用深搜的时候：在dfs之前输出就是dfs序列，但是在回溯之前输出的话那就是拓扑排序的逆序。

考题：2011-8、2012-5、2012-6、2013-7、2013-8、2014-7、2015-5、2016-6、2016-7、2017-3、2017-7、2018-7、2020-6

• 判断是不是广度搜索，可以列举各点到起点的最短距离，一次排列，如有小的值在序列后面说明不是。
• 小技巧：做选择题中判断的，从后面往前看
• 题目中拓扑排序的不明确指向深搜，一般都是宽搜的写法