1. 图的定义

图是由顶点的有穷非空集合和顶点之间边的集合组成。

1.1 有向图、无向图、完全图

  • 有向图：边有方向的图
  • 无向图：边没有方向的图
  • 完全图：任意两个顶点之间都有边相连的图

2. 图的存储结构

2.1 邻接矩阵表示法

用一个二维数组表示图中顶点之间的邻接关系。

2.2 邻接链表表示法

为每个顶点建立一个链表，存储与该顶点相邻接的顶点。

3. 图的遍历

3.1 深度优先搜索（DFS）

从图 G 任一结点 v 出发按深度优先搜索法进行遍历。

特点：尽可能先进行纵向搜索。

3.2 广度优先搜索（BFS）

特点：尽可能先进行横向搜索，即最先访问的顶点的邻接点也先被访问。

4. 拓扑排序

4.1 AOV 网

用顶点表示活动，用有向边表示活动之间的优先关系的有向图称为 AOV 网（Activity On Vertex Network）。

4.2 拓扑排序的方法

对 AOV 网进行拓扑排序的方法：

  1. 在 AOV 网中选择一个入度为 0 的顶点并输出
  2. 从网中删除该顶点及所有以它为尾的弧
  3. 重复上述两步，直到网中不存在入度为 0 的顶点为止

若输出的顶点数少于网中的顶点数，则说明网中存在环，拓扑排序无法进行。