基本概念

图的定义

图 G 由顶点的有限非空​集 V 和边集 E 组成 → G = (V, E)。

线性表可以是空表，树可以是空树，但图不可以是空图（边集可空，顶点集一定非空⚠）。

|V| 表示 G 中顶点 vertex 的个数，|E| 表示 G 中边 edge 的条数。

有向图

每条边都有方向。

无向图

每条边都没有方向。

边/无向边

无向图中的边，是顶点的无序对，记为 ($v_i$, $v_j$)，等价于有向图中 <$v_i$, $v_j$> 和 <$v_j$, $v_i$> 两条边。

可以说 $v_i$ 和 $v_j$ 互为邻接点。

边 ($v_i$, $v_j$) 依附于 $v_i$ 和 $v_j$，或称边 ($v_i$, $v_j$) 和 $v_i$、$v_j$ 相关联。

弧/有向边

有向图中的边，是顶点的有序对，记为 <$v_i$, $v_j$>，$v_j$ 为弧头，$v_i$ 为弧尾。

<$v_i$, $v_j$> 称从 $v_i$ 到 $v_j$ 的弧，也称 $v_i$ 邻接到 $v_j$。

度

度 TD($v$)：依附于顶点 $v$ 的边/弧的条数。

入度 ID($v$)：有向图中指向顶点 $v$ 的边的条数。

出度 OD($v$)：有向图中由顶点 $v$ 发出的边的条数。

有向图中顶点 $v$ 的度等于其入度和出度之和，即 TD($v$) = ID($v$) + OD($v$)。

无向图的全部顶点的度的和等于边数的 2 倍（因为每条边与两个顶点相关联）。

有向图的全部顶点的入度之和 = 出度之和 = 边数。

简单图

不存在重复边（平行边）+ 不存在顶点到自身的边（自循环）。

多重图

存在平行边或自循环。

数据结构中仅讨论简单图。

完全图/有向完全图

无向完全图：具有 $\frac{n(n-1)}{2}$ 条边的无向图（任意两顶点间都存在边）。

有向完全图：具有 $n(n-1)$ 条边的有向图（任意两顶点间都存在方向相反的两条弧）。

子图

子图的点集和边集是父图点集和边集的子集（必要条件）。

但并非父图点集和边集的任何子集都能构成子图，因为这样的子集可能不是图。

生成子图

子图的点集和父图的点集相同，这样的子图称为父图的生成子图。

连通

连通：两顶点间有路径存在，则称这两顶点连通。

强连通：两顶点间双向连通，则称这两顶点强连通。

🐒一般在无向图中讨论连通性，在有向图中讨论强连通性。

也可认为，一个连通的有向图分为强连通的和非强连通的。

连通图：任意两顶点连通，则称为连通图，否则称为非连通图。

强连通图：任意两顶点强连通，则称为强连通图，否则称为非强连通图。

连通分量：即极大连通子图（连通 + 点和边尽可能多）。

强连通分量：即极大强连通子图（强连通 + 点和弧尽可能多）。

非连通图边最多的情况：由 $n-1$ 个顶点构成无向完全图，另一个顶点孤立。

强连通图边最少的情况：$n$ 条弧构成一个环路。

单个顶点也可单独构成一个连通/强连通分量（前提是其余顶点都和它不连通/强连通）。

生成树

包含图中全部顶点的一个极小连通子图（全部顶点 + 连通 + 边尽可能少）。

一般生成树是针对无向连通图。任何无向连通图都有一棵或多棵生成树。

若图中顶点数为 $n$，则它的生成树含有 $n-1$ 条边。

对生成树而言，若砍去一条边，则会变成非连通图；若加上一条边，则会形成一个回路。

若具有 $n$ 个顶点的图是一个环，则它有 $n$ 棵生成树。

生成森林

非连通图的各连通分量的生成树构成了该非连通图的生成树林。

有向树

一个顶点的入度为 0、其余顶点的入度均为 1 的有向图。

权

每条边都可以标上具有某种意义的数值，该数值称为该边的权值。

网

即带权图。

路径

顶点 $v_p$ 到顶点 $v_q$ 之间的一条路径是指顶点序列 $v_p$，$v_{i1}$，…，$v_{i2}$，$v_{im}$，$v_q$。

关联的边也可理解为路径的构成要素，此时路径定义为由顶点和相邻顶点序偶构成的边所形成的序列。

路径长度：路径上边的数目。

距离

顶点 $u$ 到顶点 $v$ 的距离是 $u$ 到 $v$ 的最短路径（若存在）的长度。

若 $u$ 到 $v$ 不存在路径，则记该距离为 ∞。

回路/环

第一个顶点和最后一个顶点相同的路径。

简单路径

顶点不重复出现（顶点只经过一次）。

简单回路

除首尾顶点外其余顶点不重复出现。

稠密图、稀疏图

依据边数的多少。

一般 |E|＜|V|log|V| 时可视为稀疏图。

存储结构

邻接矩阵

用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系）。存储顶点之间邻接关系的二维数组称为邻接矩阵。顶点数为 $n$ 的图的邻接矩阵是 $n$​​ 阶方阵。

在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点信息等均可省略）。

无权图的邻接矩阵

$A[i][j]=1$ 表示 ($v_i$, $v_j$) 或 <$v_i$, $v_j$> 在图中存在；$A[i][j]=0$ 表示 ($v_i$, $v_j$) 或 <$v_i$, $v_j$> 在图中不存在。

带权图的邻接矩阵

$A[i][j]=w_{ij}$ 表示 ($v_i$, $v_j$) 或 <$v_i$, $v_j$> 在图中存在且权值为 $w_{ij}$；$A[i][j]=0$ 或 $\infin$ 表示 ($v_i$, $v_j$) 或 <$v_i$, $v_j$> 在图中不存在。

无向图的邻接矩阵

对称且唯一（对规模特大的邻接矩阵可采用压缩存储。试题若无特别说明，默认上下三角都存储）。

第 $i$ 行或第 $i$ 列的非零或非 $\infin$ 元素的个数为顶点 $i$ 的度（非零或非 $\infin$ 元素的个数为总边数的两倍）。

有向图的邻接矩阵

非零或非 $\infin$ 元素的个数为总边数。

第 $i$ 行非零或非 $\infin$ 元素的个数为顶点 $i$ 的出度，第 $i$ 列非零或非 $\infin$ 元素的个数为顶点 $i$ 的入度。

邻接矩阵的优缺点及适用场景

  • 优点：容易确定图中任意两点之间是否有边相连。

  • 缺点：要确定图中有多少条边则必须按行、按列对每个元素进行检测，耗时久；稀疏图显然要浪费大量的存储空间，空间复杂度为 $O(|V|^2)$。

  • 适用：稠密图。

邻接矩阵的数学特性

设图 $G$ 的邻接矩阵为 $A$，$A^n$ 的元素 $A^n[i][j]$ 等于由顶点 $i$ 到顶点 $j$ 的长度为 $n$ 的路径的数目（离散数学）。

邻接表

顶点表(顺) + 边表(链)：

对于有向图，边表即为出边表。

特点

  • 给定一顶点，很容易找到它的所有邻边。
  • 若要确定给定两个顶点间是否存在边，在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。
  • 表示不唯一：每个顶点对应的单链表中各边结点链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。
  • 无向图邻接表求给定顶点的度以及有向图邻接表求给定顶点的出度和出边容易，但有向图求该顶点的入度和入边需要遍历全部的邻接表，统计邻接点 adjvex 域为该顶点的边表结点个数（也可采用逆邻接表，就反过来）。

空间复杂度

无向图：$O(|V|+2|E|)$（边会存两次）。

有向图：$O(|V|+|E|)$。

适用

稀疏图（极大地节省存储空间）。

十字链表（有向图）

顶点表(顺) + 弧表(链)：

弧结点

tailvex 域指示弧尾顶点编号，headvex 域指示弧头顶点编号，hlink 域指向弧头相同的下一条弧，tlink 域指向弧尾相同的下一条弧，info 域存放该弧的相关信息（可省）。

顶点结点

data 域存放数据信息，firstin 域指向以该顶点为弧头的第一个弧结点，firstout 域指向以该顶点为弧尾的第一个弧结点。

仍是顺序存储。

十字链表的特点

  • 出边、入边容易找，出度、入度容易求。

  • 表示不唯一，但一个十字链表表示唯一确定一个图。

邻接多重表（无向图）

顶点表(顺) + 边表(链)：

边结点
ivex 域和 jvex 域指示该边依附的两个顶点的编号，ilink 域指向下一条依附于顶点 ivex 的边，jlink 域指向下一条依附于顶点 jvex 的边，info 域存放该边的相关信息（可省）。

顶点结点

data 存储该顶点的相关信息，firstedge 指向第一条依附于该顶点的边。

邻接多重表的特点

无向图的邻接多重表表示和邻接表表示的差别仅在于，同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。

遍历

从某一顶点出发，按照某种搜索方法沿着图中的边，对所有顶点访问一次且仅访问一次。

BFS

图的广度优先搜索遍历算法 BFS (Breadth-First-Search) 是二叉树的层次遍历算法的扩展。

空间复杂度

$O(|V|)$

邻接表和邻接矩阵都需借助一个辅助队列，每个顶点均需入队一次。

时间复杂度

邻接表：$O(|V|+|E|)$

邻接矩阵：$O(|V^2|)$

BFS 算法求解单源最短路径问题

因为 BFS 总是按照距离由近到远来遍历图中每个顶点。

只适合求非带权图或边权值相等的图的单源最短路径。

广度优先生成树

同一个图的邻接矩阵存储表示是唯一的，所以其广度优先生成树也是唯一的；但因为邻接表存储表示不唯一，所以其广度优先生成树也是不唯一的。

连通图遍历产生树，非连通图遍历产生森林。

对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。

DFS

类似树的先序遍历。当不能再继续向下访问时，依次退回到最近被访问的顶点。

空间复杂度

$O(|V|)$

DFS 算法是一个递归算法，需要借助一个递归工作栈。

时间复杂度

邻接表：$O(|V|+|E|)$

邻接矩阵：$O(|V^2|)$

深度优先生成树

与 BFS 类似，基于邻接表存储的深度优先生成树是不唯一的。

图的遍历与图的连通性

图的遍历算法可以用来判断图的连通性。

对于无向图来说：

  • 若无向图是连通的，则从任意一个顶点从出发，仅需一次遍历就能够访问图中的所有顶点。
  • 若无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点。
  • BFSTraverse() 或 DFSTraverse() 调用 BFS() 或 DFS() 的次数等于该图的连通分量数。
  • 连通图遍历产生树，非连通图遍历产生森林。

对于有向图来说：

  • 若从初始顶点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。

  • 调用 BFS() 或 DFS() 的次数并不等于连通分量数或强连通分量数。

    连通但非强连通的有向图一次调用 BFS() 或 DFS() 也可能无法访问到所有顶点。

    能确定的是，需要多次调用 BFS() 或 DFS() 才能访问到所有顶点的有向图一定是非强连通的。

应用

最小生成树 MST

带权连通无向图的生成树中，边的权值之和最小的那棵生成树称为该图的最小生成（代价）树 MST (Minimum-Spanning-Tree)。

MST 的性质

  1. MST（树形）可能不唯一。

    当图中各边权值互不相等时，其 MST 是唯一的。

    若无向连通图本身是一棵树时（边数 = 顶点数 - 1），则该图的 MST 就是它本身。

  2. MST 的边的权值之和唯一且是最小的。

  3. MST 的边数为顶点数减 1。

Prim 算法和 Kruskal 算法都是基于贪心算法策略的构造 MST 的算法。

Prim 算法

  • 思路：从某一顶点开始扩展，每次选择离当前生成树距离最近的顶点并入。
  • 时间复杂度：$O(|V^2|)$
  • 适用：边稠密图

Kruskal 算法

  • 思路：按权值递增次序选择 “合适” 的边来构造，直至所有顶点都在一个连通分量上。

    “合适” 指该边依附的两个顶点分别落在不同的连通分量上。

  • 时间复杂度

    使用堆存放边，每次选择最小权值的边需要 $O(\log_{2}|E|)$ 的时间。

    每次使用并查集来快速判断两个顶点是否属于一个集合所需的时间为 $O|\alpha(V)|$，可视为常数。

    最坏情况下需要对 |E| 条边各扫描一次。

    综上，算法的时间复杂度为 $O(|E|log_{2}|E|)$。

  • 适用：边稀疏而顶点较多的图。

TODO 看不懂：由于生成树 T 中的所有边可视为一个等价类，因此每次添加新的边的过程类似于求解等价类的过程，由此可以采用并查集的结构来描述 T，从而构造 T 的时间复杂度为 $O(|E|log_{2}|E|)$。

最短路径

使用 BFS 求解单源最短路径只是对无权图或权值相等的带权图而言。

求解带权图最短路径的算法通常依赖一种性质：两点间的最短路径也包含了路径上其他顶点间的最短路径。

求最短路径允许图有环（Floyd 算法不允许有带负边的环），并且有向图和无向图都适用。

Dijkstra 算法

求单源最短路径（某一顶点到其他各顶点的最短路径）。

  • 思路

    设两个顶点集合 S、T，S 存放已找到最短路径的顶点，T 存放剩余顶点（初始 S 中只包括源点）。

    不断从 T 选取与源点路径最近的顶点并入 S，每并入一个都要更新源点到剩余顶点最短路径长度值（以并入的新顶点与源点最短路径为基础计算） 。

  • 时间复杂度

    邻接矩阵、邻接表：$O(|V^2|)$

  • 不适用：带有负权值边的图（因为已并入 S 的点的最短路径无法更新）。

  • 在构造的过程中设置了三个辅助数组：

    ① final[]：标记各顶点是否已找到最短路径，即是否已并入集合 S。

    ② dist[]：记录从源点到其他各顶点当前的最短路径长度。

    ③ path[]：path[i] 表示从源点到顶点 i 之间最短路径的前驱结点。在算法结束时，可根据其值追溯得到完整的最短路径。

    考题只要求求最短路径长度时就不用记录中间顶点。

  • 也可以求任意两个顶点间的最短路径。

    寻找从源点到某个特定顶点的最短路径，和求解源点到其他所有顶点的最短路径一样复杂，时间复杂度也为 $O(|V^2|)$。

Floyd 算法

求所有顶点间的最短路径。

  • 思路

    设有 $n$ 个顶点 $v_0$、$v_1$、…、$v_{n-1}$，以 $n$ 阶方阵 $A$ 记录两顶点间的最短路径长度。

    共有 $n+1$ 个方阵序列 $A^{-1}$、$A^{0}$、…、$A^{n-1}$，其中 $A^{-1}$ 记录初始状态各顶点间的最短路径长度，此后依次尝试在原路径加入 $v_0$、$v_1$ … 作为中间顶点，若能减少路径长度，则以此作为当前最短路径，并在方阵中更新最短路径长度。加入 $v_i$ 更新最短路径后得到方阵 $A^{i}$，经过 $n$ 次迭代后所得到的 $A^{(n-1)}$ 便保存了任意一对顶点间的最短路径长度。

    $A^{k}[i][j]=min(A^{k-1}[i][j], A^{k-1}[i][k]+A^{k-1}[k][j])$

    显然，主对角线始终为 0。另外计算 $A^{i}$ 即加入 $v_i$ 时，第 $i$ 行和第 $i$ 列也不用动。

  • 时间复杂度：$O(|V^3|)$。

    不过由于其代码很紧凑，且不包含其他复杂的数据结构，因此隐含的常数系数是很小的，即使对于中等规模的输入来说，它仍然是有效的。

  • 不适用：允许图中带有负权值的边，但不允许有包含负权值边的环。

  • 也可用单源最短路径算法来解决每对顶点之间的最短路径问题：

    轮流将每个顶点最为源点，并且在所有边权值均非负时，运行一次 Dijkstra 算法。

    其算法复杂度为 $|V|·O(|V^2|)=O(|V^3|)$。

有向无环图

有向无环图 DAG (Directed Acyclic Graph)，简称 DAG 图。

利用有向无环图 DAG 描述表达式，可实现对相同子式的共享，从而节省存储空间。

在表达式的 DAG 图表示中，不可能出现重复的操作数顶点。

例如表达式 $((a+b)(b(c+d))+(c+d)e)((c+d)e)$，公共子式为 $(c+d)$ 和 $(c+d)e$。

拓扑排序

AOV 网

以顶点表示活动、以弧表示活动的先后次序的无权 DAG，称之为 顶点表示活动的网络 (Activity On Vertex NetWork)，简称 AOV 网。

拓扑排序

由一个 DAG 的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

  1. 每个顶点出现且只出现一次。
  2. 若顶点 A 在序列中排在顶点 B 的前面，则在图中不存在从顶点 B 到顶点 A 的路径。

或定义为：拓扑排序是对 DAG 的顶点的一种排序，它使得若存在一条从顶点 A 到顶点 B 的路径，则在排序中顶点 B 出现在顶点 A 的后面。

对 AOV 网进行拓扑排序的常用算法思路

  1. 从 AOV 网中选择一个没有前驱的顶点并输出。

  2. 从网中删除该顶点和所有以它为起点的有向边。

  3. 重复前两步，直到当前 AOV 网为空或当前网中不存在无前驱的顶点为止。

    后一种情况说明有向图中必然存在环。

入度为 0 的顶点，说明没有前驱活动或前驱活动都已完成，则工程可以从这个顶点所代表的活动开始或继续。

拓扑排序的算法时间复杂度

因为输出每个顶点的同时还要删除以它为起点的边，所以：

邻接表 $O(|V|+|E|)$，邻接矩阵 $O(|V|^2)$。

拓扑序列的存在性

不存在拓扑排序$\iff$图中存在顶点数大于 1 的回路/环（存在拓扑序列$\iff$无环）

邻接矩阵为三角矩阵（且对角元全为零）$\rightarrow$ 无环

每个 AOV 网都有一个或多个拓扑排序序列：若存在有多个直接后继的顶点，则拓扑排序的结果通常不唯一；若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果唯一。

拓扑序列的唯一性

充要条件：每次输出顶点时，检测入度为 0 的顶点始终唯一。

充分非必要条件：AOV 网的各顶点为线性序列。

利用 DFS 实现拓扑排序

用 DFS 算法遍历一个有向无环图，并在 DFS 算法退栈返回时输出相应的顶点，则输出的顶点序列是逆拓扑有序。在此基础上，可以在遍历结束后将序列反转得到拓扑有序序列；也可以设置一个计时器，在退栈返回时不选择输出，而是对各顶点计时（记录结束时间）。遍历结束后按结束时间从大到小排序，即可得到拓扑序列。

逆拓扑排序

  1. 从 AOV 网中选择一个无后继（出度为 0）的顶点并输出。

  2. 从网中删除该顶点和所有所有以它为终点的有向边。

  3. 重复前两步，直到当前 AOV 网为空。

利用 BFS 实现拓扑排序

没错，BFS 也可用来实现拓扑排序。有同学就有疑问了，拓扑排序可以检测环，BFS 可以实现拓扑排序，那 BFS 岂不是也可以检测环了？答案是否定的，因为用 BFS 实现拓扑排序的前提是，使用的图是 DAG。

TODO：实现思路。

关键路径

AOE 网

以顶点表示事件，以有向边表示活动，以边的权值代表完成该活动开销的带权 DAG，称之为 边表示活动的网络 (Activity On Edge Network)，简称 AOE 网。

AOE 网的性质

  • 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
  • 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

源点与汇点

在 AOE 网中仅有一个入度为 0 的顶点，称为开始顶点（源点），代表整个工程的开始。

网中也仅存一个出度为 0 的顶点，称为结束顶点（汇点），表示整个工程的结束。

在 AOE 网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才算结束。

关键路径与关键活动

关键路径：从源点到汇点的所有路径中，具有最大路径长度的路径。

关键活动：关键路径上的所有活动。

完成整个工程的最短时间 = 关键路径的长度。

通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能变成非关键活动。

关键路径不一定唯一，且对于有几条关键路径的网，只加快部分关键路径并不能缩短整个工期，只有加快所有关键路径才能达到缩短工期的目的。

事件 $v_k$ 的最早发生时间 $v_e(k)$

从源点到 $v_k$ 的最长路径长度。

决定了所有从 $v_k$ 开始的活动能够开工的最早时间。

可按 $v_e(源点)=0$、$v_e(k)=max(v_e(j)+weight(v_j, v_k))$ 从前往后进行递推计算。其中 $v_j$ 为 $v_k$ 的任意前驱，$weight(v_j, v_k)$ 为 <$v_j$, $v_k$> 的权值。

可在求拓扑排序的过程基础上求解。

事件 $v_k$ 的最迟发生时间 $v_l(k)$

在不推迟整个工程完成的前提下，即保证它的后继事件 $v_j$ 在其最迟发生时间 $v_l(j)$ 能够发生时，该事件最迟必须发生的时间。

可按 $v_l(汇点)=v_e(汇点)$、$v_l(k)=min(v_l(j)-weight(v_k, v_j)$ 从后往前进行递推计算。其中 $v_j$ 为 $v_k$ 的任意后继。

可在求逆拓扑排序的过程基础上求解。

活动 $a_i$ 的最早发生时间 $e(i)$

该活动弧的起点事件的最早发生时间。

活动 $a_i$ 的最迟发生时间 $l(i)$

该活动弧的终点事件的最迟发生时间与该活动所需时间之差。

活动 $a_i$ 完成的时间余量 $d(i)$

在不增加完成整个工程所需总时间的情况下，活动 $a_i$ 可以拖延的时间

$d(i)=l(i)-e(i)$

若一个活动的时间余量为 0，说明该活动必须如期完成，否则就会拖延整个工程的进度。

$l(i)-e(i)=0$ 即 $l(i)=e(i)$ 的活动就是关键活动。

求关键路径的一般步骤

  1. 从源点出发，令 $v_e(源点)=0$，按拓扑排序求其余顶点的 $v_e()$

  2. 从汇点出发，令 $v_l(汇点)=v_e(汇点)$，按逆拓扑排序求其余顶点的 $v_l()$

  3. 根据各顶点事件的 $v_e()$ 求所有弧活动的 $e()$，根据各顶点事件的 $v_l()$ 求所有弧活动的 $l()$。

  4. 求 AOE 网中所有活动的 $d()$，找出所有 $d()=0$ 的活动构成关键路径。

    这里求关键路径要满足：路径上的所有活动都是关键活动，即 $d()=0$ 的活动，并且路径长度等于最大路径长，即 $v_l(汇点)$ 或 $v_e(汇点)$。

    ⚠特别注意：路径上所有活动都是关键活动 ≠ 此路径是关键路径。

实际上求出各顶点事件 $ve()$ 后就能得到关键路径（可能有多条）。

求关键路径还是得多练习，有些地方说不清楚，需要一定熟练度。下题用来练手：

刷题笔记

  • 单个顶点也可单独构成一个连通/强连通分量（前提是其余顶点都和它不连通/强连通）。

  • 若一个具有 $n$ 个顶点、$e$ 条边的无向图是一个森林，则该森林中必有 $n - e$ 棵树。

  • 只有邻接矩阵的表示唯一。

  • BFS/DFS 序列、广度/深度优先生成树的唯一性

    邻接矩阵：唯一（因为同一个图的邻接矩阵存储表示唯一）

    邻接表：不唯一（因为同一个图的邻接表存储表示不唯一）

  • 如何对无环有向图中的顶点重新编号，使得该图的邻接矩阵中所有 1 都集中到对角线以上？

    方式一：

    1）按各顶点的出度进行排序。出度最大的顶点编号为 1，出度最小的顶点编号为 $n$（设共 $n$ 个顶点）。

    2）只要存在弧 <$i$, $j$>，就把顶点 $i$ 编号在顶点 $j$ 之前。

    方式二：采用拓扑排序并依次编号。

  • 建立无向图邻接表的时间复杂度为 O($n+e$)。

  • 练一下只根据邻接表（即不画图）写出的 BFS 和 DFS 序列（P232 选择08）

    不画图即按算法思路走，可以节省画图时间；画图比较直观，不容易错，但也要结合邻接表的边表结点顺序

  • 根据邻接表画出深度优先生成树和广度优先生成树（P211 综合01）。

    画不画图跟上一条一样。建议第一遍做不画图，第二遍检查时画图（有时间的话哈哈哈）。

  • DFS 可实现拓扑排序，可判断图中是否存在回路。

    若将输出顶点信息的语句移到退出递归前，则输出的顶点序列是逆拓扑排序。

  • MST 一定唯一的两种情况：① 图中各边的权值互不相等；② 图本身是一棵树

    图中存在权值相同的边，其 MST 可能不唯一。

  • 讨论拓扑排序和关键路径的前提是：DAG（有向 + 无环）。

    只讨论拓扑排序时使用的是 AOV 网，无权。

    讨论关键路径使用的是 AOE 网，有权，且应连通。

  • 可以判断是否有环/回路

    1. DFS

      无向图：在深度优先遍历过程中遇到了回边，则必定存在环。

      有向图：在深度优先遍历过程中遇到了回边，不一定存在环，这条回边可能是指向深度优先生成森林中另一棵生成树。但若从某个顶点 u 出发，在 DFS(u) 结束之前发现一条从顶点 v 到 u 的边，由于 v 在生成树上是 u 的子孙，则图中必定存在包含 u 和 v 的环。

    2. 拓扑排序

      存在无法找到下一个可以加入拓扑序列的顶点，则说明此图存在回路（顶点数目大于 1 的强连通分量）。

    3. 求关键路径

      求关键路径的算法本身无法判断是否有环。

      判断是否有环是求关键路径的第一步——拓扑排序。

  • 求两个顶点的最短路径上经过的顶点序列

    选择题可以直接把选项的路径长度都求出来，选最短的就行。

    不然就跟着迪杰斯特拉或者弗洛伊德算法走一遍。

  • 图的邻接矩阵为三角矩阵且对角元全为零 $\rightarrow$ 无环 ↔ 拓扑排序存在

    图的邻接矩阵为三角矩阵且对角元全为零，并且对角线以上/以下全为 1（不为 0）$\rightarrow$ 拓扑序列存在且唯一

    具有有序的拓扑排序序列 $\rightarrow$ 图的邻接矩阵为三角矩阵且对角元全为零

    对有向图中的顶点进行适当的编号，使其邻接矩阵为三角矩阵且主对角元全为零的充分必要条件是，该有向图可以进行拓扑排序。

  • 拓扑序列唯一，不能唯一确定该图

    拓扑序列唯一，也不能说明图中每个顶点的入度和出度最多为 1

    比如下面三个 DAG，它们的拓扑排序唯一且都是 ABCD

  • 若有向图的拓扑有序序列唯一，则图中入度为 0 和出度为 0 的顶点都仅有 1 个。

    若入度为 0 的顶点不唯一，则这些顶点均可作为拓扑序列的起点；若出度为 0 的顶点不唯一，则这些顶点均可作为拓扑序列的终点。

  • 破圈法求解最小生成树

    任取一圈，去掉圈上权值最大的边。反复执行这一步骤，直到没有圈为止

  • 求有向图的强连通分量的数目

    1. 每个顶点自身都是一个强连通分量

      所以含有 $n$ 个顶点的有向图至少有 $n$ 个强连通分量

    2. 当某个顶点只有出弧而没有入弧时，其他顶点无法到达这个顶点，不可能与其他顶点和边构成强连通分量

      所以直接删除该顶点及所有与之为尾的弧（即该顶点的所有出弧）

  • 关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。

    缩短所有关键路径上共有的任意一个关键活动的持续时间可缩短关键路径长度。

  • 所有顶点事件都是关键事件并不能说明关键路径唯一。

    如下图，所有事件都是关键事件，且除了 a 之外都是关键活动。

  • 关键路径不一定包含所有关键活动。

    只包含关键活动的路径且保证长度最大就是关键路径。