• 图的基本概念、存储表示（邻接矩阵、邻接表、十字链表）
  • 图的遍历（DFS、BFS）及其遍历树
  • 强联通分量、Kosaraju
  • 生成树、最小生成树、Kruskal、Prim、并查集
  • 最短路、Dijkstra、Floyd
  • 有向无环图、拓扑排序、关键路径

易混概念

  • 连通图的生成树是含有该连通图全部顶点的 极小连通子图。
  • 自由树：没有简单回路的无向图，连通且有 $n - 1$ 条边。
  • 网络：带权连通图
  • 有向图的生成森林：由若干有向树组成，树的并集包括所有顶点，有向树的边不相交。

图的存储

  • 邻接矩阵：A[i][j].
  • 邻接表：
    • 顶点 {data, *first_edg}
    • 边 {adjvex, *next_edg, data}
    • 分为邻接表（同一起点）和逆邻接表（同一终点）
  • 邻接多重表（对于无向图）：
    • 顶点 {data, *first_edg}
    • 边 {data, vex1, vex2, *next_vex1_path, *next_vex2_path}
  • 十字链表（对于有向图）：
    • 顶点 {data, *first_in_edg, *first_out_edg}
    • 边 {data, from, to, *next_from_path, *next_to_path}

有向图强连通分量（Kosaraju 算法）

对于有向图 $G$，Kosaraju 算法的流程：

  1. 在原图 $G$ 上做一次 DFS，得到 DFS 森林。
  2. 对于 DFS 森林，将每个顶点按照 DFS 完成顺序编号（单棵树内是 DFS 后序遍历，后遍历到的树的编号顺序大一些）
  3. 对原图 $G$ 每条边反向，得到反图 $G’$.
  4. 每次对未访问且编号的最大的点开始，对 $G’$ 做 DFS，每次 DFS 到的顶点集合构成强连通分量。

算法正确性证明：

  • 首先，如果我们将 $G$ 中的强连通分量缩点，得到的图 $G^{SCC}$ 是一个有向无环图。 证明：反证法，若存在环，则这些强连通分量应合并为一个更大的强连通分量，矛盾。
  • 然后，对于未访问且最大的点，它所在的强连通分量 $C$ 在 $G^{SCC}$ 必然是入度为零的分量。 证明：反证法，假设有另一强连通分量 $C’ \rightarrow C$，那么 $C’$ 的结点在原图的后序遍历应该比 $C$ 中的结点靠后，而这里我们选取未访问且编号最大的点，矛盾。
  • 假设前 $k$ 次 DFS 已经正确找出了正确的强连通分量并已经移除（相当于在对 $G^{SCC}$ 的拓扑排序中，已访问前 $k$ 个可行点），现在我们考虑未访问且最大的点。
  • 在反图中，这个点所在的强连通分量必然是没有出边，该证明和刚才是类似的。所以，我们在反图上从该点开始进行遍历，由于同一强连通分量在反图中仍保持强连通性，因此 DFS 能遍历该分量内的全部结点。于是我们就可以找到强连通分量的所有结点。

关键路径

最早发生时间： $$ve_i = \begin{cases}0, & i 是源点 \\ \displaystyle \max_{j \to i}\{ve_j + w_{ji}\},\ & i 不是源点\end{cases}$$ 最晚发生时间： $$vl_i = \begin{cases}ve_{i}, & i 是汇点 \\ \displaystyle \min_{i \to j}\{vl_j - w_{ji}\},\ & i 不是汇点\end{cases}$$