图

图的存储结构：

1. AM: Adjacent Matrix 邻接矩阵
2. AL: Adjacent List 邻接表
3. RAL: Reverse Adjacent List 逆邻接表
4. TL: Triple List 三元组顺序表(往往是行逻辑链接的，性能更好)
5. CL: Cross List 十字链表

图按存储结构分为：

1. AMGraph: Adjacent Matrix Graph
2. ALGraph: Adjacent List Graph
3. TLGraph: Triple List Graph
4. RALGraph: Reverse Adjacent List Graph
5. CLGraph: Cross/Orthogonal List Graph

图的遍历

BFS

时间复杂度取决于图的存储结构：

• 邻接矩阵：\(O(n^2)\)
• 邻接表：\(O(n+e)\)

DFS

时间复杂度取决于图的存储结构：

• 邻接矩阵：\(O(n^2)\)
• 邻接表：\(O(n+e)\)

有向图的拓扑排序

一个图可拓扑排序的充要条件是它无环，即它是有向无环图(DirectedAcyclic Graph，DAG)

算法实现

采用正邻接链作为 AOV 网的存储结构;

设立堆栈(或队列)，用来暂存入度为 0 的顶点;

while(堆栈/队列不为空){
    删除顶点以它为尾的弧：弧头顶点的入度减1，度数为0则入堆栈(或队列)
}

算法分析

设 AOV 网有 n 个顶点，e 条边，则算法的主要执行是:

• 统计各顶点的入度:时间复杂度是\(O(n+e)\);

• 入度为 0 的顶点入栈:时间复杂度是\(O(n)\);

• 排序过程:顶点入栈和出栈操作执行 n 次，入度减 1 的操作共执行 e 次，时间复杂度是\(O(n+e)\);

因此，整个算法的时间复杂度是\(O(n+e)\)

无向图的生成树

dfs 稍作修改即可得到生成树算法

保证每个节点只访问一次就可以避免环

无向图的生成森林

在生成树的基础上，加上并查集

有向图的强连通分量

1. 对有向图 G 进行 dfs 生成森林 T
2. 按中序遍历顺序编号
3. 从编号最大的节点开始再 dfs 遍历
4. 按(2)中标出的顶点编号，从编号最大的顶点开始对 G’进行深度优先搜索，得到一棵深度优先生成树。若一次完整的搜索过程没有遍历 G’的所有顶点，则从未访问的顶点中选择一个编号最大的顶点，由它开始再进行深度优先搜索，并得到另一棵深度优先生成树。在该步中，每一次深度优先搜索所得到的生成树中的顶点就是 G 的一个强连通分量的所有顶点。
5. 重复步骤(4)，直到 G’中的所有顶点都被访问。如下图是求一棵有向树的强连通分量过程。