# 图的存储结构：

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’中的所有顶点都被访问。如下图是求一棵有向树的强连通分量过程。