《数据结构》学习系列——图（中）

系列文章目录

目录

---

图的遍历

• 从给定连通图的某一顶点出发，沿着一些边访问遍图中所有的顶点，且使每个顶点仅被访问一次，称为图的遍历（Graph Traversal）
• 存在的问题：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到曾经访问过的顶点。
  • 避免重复访问：设置一个标志顶点是否被访问过的辅助数组 visited[]，它的初始状态为 0。在图的遍历过程中，一旦某一个顶点 $i$ 被访问，就立即让 visited[i] 置为 1，防止它被多次访问

深度优先遍历

• 深度优先遍历又被称为深度优先搜索 DFS (Depth First Search)，其类似于树的先根遍历
• 基本思想：
  • DFS在访问图中某一起始顶点 $v$ 后，由 $v$ 出发，访问它的任一邻接顶点 $w_1$；再从 $w_1$ 出发，访问与 $w_1$ 邻接但还没有访问过的顶点 $w_2$；然后再从 $w_2$ 出发，进行类似的访问。如此往下去，直至到达所有的邻接顶点都被访问过的顶点 $u$ 为止。接着，退回一步，退到前一次访问过的顶点，看看还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止
    

递归算法

伪代码

// 图的深度优先遍历的递归算法
DepthFirstSearch(v, visited)
{visited[v] = 1;p = adjacent(Head[v]);while (p != NULL){if (visited[VerAdj(p) != 1]){DepthFirstSearch(VerAdj(p), visited)p = link(p);	}}
}// 算法主体
DFS_Main()
{// 为辅助数组申请空间visited = new int[graphsize];// 数组初始化for (int k = 0; k < graphsize; k++){visited[k] = 0;// 从序号为0的顶点出发，深度优先遍历图DepthFirstSearch(0, visited)delete[] visited;}
}

非连通图需要多次调用深度优先遍历算法

for i = 0 to n-1
{for j = 0 to n-1{if visited[j] = 0{DepthFirstSearch(v[j], visited)}}	
}

算法分析

• 图中有 $n$ 个顶点，$e$ 条边
• 如果用邻接表存储，沿顶点的adjacent可以找到某个顶点 $v$ 的所有邻接顶点 $w$。由于总共有 $2e$（无向图）或 $e$（有向图）个边结点，所以扫描边的时间为 $O(e)$。而且对所有顶点递归访问 1 次，所以遍历图的时间复杂性为 $O(n+e)$
• 如果用邻接矩阵存储，则查找每一个顶点的所有的边，所需时间为 $O(n)$，则遍历图中所有的顶点所需的时间为 $O(n^2)$

堆栈算法

• 可以利用堆栈实现深度优先遍历的非递归算法
• 堆栈中存放已访问结点的还没有被访问的邻接顶点。每次弹出栈顶元素时，如其未被访问则访问该顶点，检查当前顶点的边链表，将还没有被访问的邻接顶点入栈，循环进行

基本思想
首先将所有顶点的visited[]值置为 0，初始顶点压入堆栈

• ① 检测堆栈是否为空。若堆栈为空，则迭代结束；否则，从栈顶弹出一个顶点 $v$
• ② 如果 $v$ 未被访问过，则访问 $v$，将visited[v]值更新为 1，然后根据 $v$ 的邻接顶点表，将 $v$ 的未被访问的邻接顶点压入栈，执行步骤 ①

// 非递归实现深度优先遍历算法
void DFS(Graph &graph, int v) {stack<int> S;         // 创建栈Svector<bool> visited(graph.size(), false); // 初始化访问标记数组S.push(v);            // 将起始顶点压入栈while (!S.empty()) {  // 当栈不为空时int v = S.top();  // 弹出栈顶元素S.pop();if (!visited[v]) {cout << v << " ";  // 访问顶点visited[v] = true; // 标记为已访问// 获取顶点v的所有邻接顶点，并压入栈中for (auto p = graph.adjacent(v); p != nullptr; p = p->link) {if (!visited[p->VerAdj]) {S.push(p->VerAdj);}}}}
}

算法分析

• 如果使用邻接表表示图，则循环的总时间代价为 $d_0+d_1+\cdots +d_{n-1}=O(e)$，其中 $d_i$ 是顶点 $i$ 的度（无向图）或出度（有向图）。总的时间复杂度为 $O(n+e)$
• 如果使用邻接矩阵，则对于每一个被访问的顶点，循环要检测矩阵中的 $n$ 个元素，总的时间代价为 $O(n^2)$

---

广度优先搜索

• 为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问
• 与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组visited[]，为被访问过的顶点加标记

// BFS1 [初始化]
CREATEQ(Q);         // 创建队列 Q
for (int i = 1; i <= n; i++) visited[i] = 0; // 初始化所有顶点为未访问
PRINT(v);           // 打印起始顶点
visited[v] = 1;     // 标记起始顶点为已访问
Q.enqueue(v);       // 起始顶点入队列// BFS2 [广度优先遍历]
while (!Q.isEmpty()) {       // 当队列不为空时v = Q.dequeue();         // 队头元素出队p = adjacent(Head[v]);   // 获取当前顶点的邻接链表while (p != NULL) {      // 遍历邻接链表if (visited[p->VerAdj] == 0) { // 如果邻接顶点未被访问Q.enqueue(p->VerAdj);      // 将邻接顶点入队PRINT(p->VerAdj);          // 打印邻接顶点visited[p->VerAdj] = 1;    // 标记邻接顶点为已访问}p = p->link;        // 继续访问下一个邻接顶点}
}

算法分析

• 如果使用邻接表表示图，则循环的总时间代价为 $d_0+d_1+\cdots +d_{n-1}=O(e)$，其中 $d_i$ 是顶点 $i$ 的度。总的时间复杂度为 $O(n+e)$
• 如果使用邻接矩阵，则对于每一个被访问的顶点，循环要检测矩阵中的 $n$ 个元素，总的时间代价为 $O(n^2)$

---

拓扑排序

• AOV 网：在有向图中，用顶点表示活动，用有向边表示活动之间的先后关系，称这样的有向图为AOV网 (Activity On Vertex Network)}
  • 计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了所有这些活动，这个工程就可以完成了
  • 例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样，在有些课程之间有先后关系，有些课程可以并行地学习

定义定理

• 在 AOV 网络中，如果活动 $V_i$ 必须在活动 $V_j$ 之前进行，则存在有向边 $⟨V_i,V_j⟩$
• AOV 网络中不能出现有向回路，即有向环。在 AOV 网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的 AOV 网络，必须先判断它是否存在有向环
• 拓扑序列：AOV 网中所有顶点排成的线性序列，要求每个活动的所有前驱活动都排在该活动前面
• 拓扑排序：构造 AOV 网的拓扑序列的过程被称为拓扑排序
• 如果通过拓扑排序能将 AOV 网络的所有顶点都排入一个拓扑有序的序列中，则该 AOV 网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明 AOV 网络中存在有向环，此 AOV 网络所代表的工程是不可行的
• 设图 $G=(V,E)$ 是非循环图，$V(G)\ne \varnothing$，则 $G$ 中一定存在入度为零的顶点。
• 设 $G=(V,E)$ 是非循环图， V ( G ) = { 1 , 2 , … , n } V(G) = \{1, 2, \dots, n\} V(G)={1,2,…,n}，$e=|E(G)|$。则算法是正确的，且算法的时间复杂性为 $O(n+e)$

算法思想

• 拓扑排序算法的基本步骤
  • 从网中选择一个入度为 0 的顶点并将其输出
  • 从网中删除该顶点及其所有出边
  • 执行步骤 ① 和 ②，直至所有顶点都已输出，或网中剩余顶点入度均不为 0（说明网中存在回路，无法继续拓扑排序）
    注意：对于任何无回路的 AOV 网，其顶点均可排成拓扑序列，但其拓扑序列未必唯一

伪代码

• 假定 AOV 网用邻接表的形式存储。为实现拓扑排序算法，事先需做好两项准备工作：
• 建立一个数组count[]，count[i]的元素值为顶点 $i$ 的入度；
• 建立一个堆栈，栈中存放入度为 0 的顶点，每当一个顶点的入度为 0，就将其压入栈

// TOrder1 [初始化]
// 计算 count 数组（每个顶点的入度）
for (int i = 1; i <= n; i++) count[i] = 0; // 初始化所有顶点的入度为 0// 遍历邻接表，计算每个顶点的入度
for (int i = 1; i <= n; i++) {p = adjacent(Head[i]); // 获取顶点 i 的邻接表头指针while (p != NULL) {    // 遍历邻接表count[VerAdj(p)]++; // 更新邻接顶点的入度p = p->link;        // 移动到下一个邻接点}
}// 拓扑排序
top = 0; // 栈顶指针初始化为 0// 将入度为 0 的顶点压入栈
for (int i = 1; i <= n; i++) {if (count[i] == 0) {stack[top] = i; // 顶点 i 入栈top++;          // 栈顶指针加 1}
}for (int i = 1; i <= n; i++) {// 如果循环体执行了 n 次但栈为空，则说明图中存在回路if (top == 0) {PRINT("There is a cycle in the network!");RETURN;} else {// 栈顶元素出栈j = stack[top - 1];top--; // 栈顶指针减 1PRINT(j); // 输出顶点 j（拓扑序中的一个顶点）// 遍历顶点 j 的邻接表，更新邻接顶点的入度p = adjacent(Head[j]);while (p != NULL) {k = VerAdj(p);    // 获取邻接顶点count[k]--;       // 邻接顶点的入度减 1if (count[k] == 0) { // 如果邻接顶点入度变为 0，则压入栈stack[top] = k;top++;}p = p->link; // 继续遍历下一个邻接点}}
}

---

关键路径

基本概念

• 如果在有向无环的带权图中

  • 用有向边表示一个工程中的各项活动 (Activity)
  • 用边上的权值表示活动的持续时间 (Duration)
  • 用顶点表示事件 (Event)

• 则这样的有向图叫做用边表示活动的网络，简称AOE (Activity On Edges) 网络

  • 源点：表示整个工程的开始（入度为零）
  • 汇点：表示整个工程的结束（出度为零）

• 在 AOE 网络中，有些活动必须顺序进行，有些活动可以并行进行

• 从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成

• 完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径被称为关键路径 (Critical Path)

• 关键路径：从源点到汇点具有最大长度的路径称为关键路径

• 路径长度：指路径上的各边权值之和

• 关键活动：关键路径上的活动

关键活动有关量

• 事件 $v_j$ 的最早发生时间ve(j)：

  • 从源点 $v_0$ 到 $v_j$ 的最长路径长度。

• 事件 $v_j$ 的最迟发生时间vl(j)：

  • 保证汇点的最早发生时间不推迟（即不推迟整个工程完成时间）的前提下，事件 $v_j$ 允许的最迟发生时间，等于ve(n-1)减去从 $v_j$ 到 $v_{n-1}$ 的最长路径长度

• 活动 $a_i$ 的最早开始时间e(i)：

  • 设活动 $a_i$ 在有向边 $⟨v_j,v_k⟩$ 上，e(i)是从源点 $v_0$ 到 $v_j$ 的最长路径长度。因此e(i) = ve(j)

• 活动 $a_i$ 的最迟开始时间l(i)：

  • l(i)是在不会引起时间延误的前提下，该活动允许的最迟开始时间。设活动 $a_i$ 在有向边 $⟨v_j,v_k⟩$ 上，则$l(i)=\text{vl(k)}-\text{weight}(⟨j,k⟩)$

数学公式

• 求所有事件的最早发生时间}：
  递推公式： // 拓扑排序正序
  ve(k) = { 0 , k = 0 max ⁡ { ve(j) + weight ( ⟨ j , k ⟩ ) } , ⟨ v j , v k ⟩ ∈ E ( G ) , k = 1 , 2 , … , n − 1 \texttt{ve(k)} = \begin{cases} 0, & k = 0 \\ \max\{\texttt{ve(j)} + \texttt{weight}(\langle j, k \rangle)\}, & \langle v_j, v_k \rangle \in E(G), \; k = 1, 2, \dots, n-1 \end{cases} ve(k)={0,max{ve(j)+weight(⟨j,k⟩)},​k=0⟨vj​,vk​⟩∈E(G),k=1,2,…,n−1​

• 求所有事件的最迟发生时间}：
  递推公式：拓扑排序逆序
  vl(j) = { ve(n-1) , j = n − 1 min ⁡ { vl(k) − weight ( ⟨ j , k ⟩ ) } , ⟨ v j , v k ⟩ ∈ E ( G ) , j = n − 2 , n − 3 , … , 0 \texttt{vl(j)} = \begin{cases} \texttt{ve(n-1)}, & j = n-1 \\ \min\{\texttt{vl(k)} - \texttt{weight}(\langle j, k \rangle)\}, & \langle v_j, v_k \rangle \in E(G), \; j = n-2, n-3, \dots, 0 \end{cases} vl(j)={ve(n-1),min{vl(k)−weight(⟨j,k⟩)},​j=n−1⟨vj​,vk​⟩∈E(G),j=n−2,n−3,…,0​

伪代码

思路
求关键活动的基本步骤：

• 对 AOE 网进行拓扑排序，若网中有回路，则终止算法；按拓扑次序求出各顶点事件的最早发生时间 ve
• 按拓扑序列的逆序求出各顶点事件的最迟发生时间 vl
• 根据ve和vl的值，求出各活动的最早开始时间 e(i)与最迟开始时间l(i)，若e(i) = l(i)，则 $i$ 是关键活动

// CPath1 - 计算事件的最早发生时间
// 初始化事件的最早发生时间
for (int i = 1; i <= n; i++) ve[i] = 0; // 最早发生时间初始化为 0// 按拓扑序计算事件的最早发生时间
for (int i = 1; i <= n; i++) {p = adjacent(Head[i]); // 获取顶点 i 的邻接表while (p != NULL) {k = VerAdj(p); // 获取邻接顶点if (ve[i] + cost(p) > ve[k]) // 更新最早发生时间ve[k] = ve[i] + cost(p);p = p->link; // 继续访问下一个邻接点}
}// CPath2 - 计算事件的最迟发生时间
// 初始化事件的最迟发生时间
for (int i = 1; i <= n; i++) vl[i] = ve[n]; // 最迟发生时间初始化为最后事件的最早时间// 按拓扑逆序计算事件的最迟发生时间
for (int i = n; i >= 1; i--) {p = adjacent(Head[i]); // 获取顶点 i 的邻接表while (p != NULL) {k = VerAdj(p); // 获取邻接顶点if (vl[k] - cost(p) < vl[i]) // 更新最迟发生时间vl[i] = vl[k] - cost(p);p = p->link; // 继续访问下一个邻接点}
}// CPath3 - 关键活动的最早开始时间和最迟开始时间
// 遍历所有活动，计算关键活动
for (int i = 1; i <= n; i++) {p = adjacent(Head[i]); // 获取顶点 i 的邻接表while (p != NULL) {k = VerAdj(p); // 获取邻接顶点e = ve[i]; // 最早开始时间l = vl[k] - cost(p); // 最迟开始时间if (e == l) // 如果最早时间等于最迟时间，则为关键活动PRINT("<", i, ",", k, "> is Critical Activity!");p = p->link; // 继续访问下一个邻接点}
}

时间复杂性

• 时间复杂性：对顶点进行拓扑排序的时间复杂性为 $O(n+e)$，以拓扑次序求ve[i]和按拓扑逆序求vl[i]}时，所需时间均为 $O(e)$。求各个活动的e[k]和l[k]的时间复杂度为 $O(e)$，整个算法的时间复杂性是 $O(n+e)$
• 定理 6.3：任意的非空 AOE 网至少存在一条关键路径
• 推论 6.1：假设边 $⟨T_i,T_j⟩$ 属于 AOE 网，则有
  $$\text{vl[j]}-\text{ve[i]}\ge \text{Weight}(⟨T_i,T_j⟩)$$
• 且如果 $⟨T_i,T_j⟩$ 属于某一条关键路径，则有
  $$\text{vl[j]}-\text{ve[i]}=\text{Weight}(⟨T_i,T_j⟩).$$