算法和应用
DFS
深度优先搜索(Depth-First Search,简称 DFS)是一种用于图的遍历和搜索的算法,它从图中的一个起始顶点开始,尽可能深地访问顶点,直到无法继续前进,然后回溯到之前的顶点,继续深入其他分支。DFS 通常用递归或栈来实现,确保在深度方向上优先遍历。
以下是 DFS 算法的一般步骤:
- 从起始顶点开始,将其标记为已访问。
- 遍历与当前顶点相邻的未访问顶点,选择其中一个未访问顶点作为下一个深度遍历的目标,然后递归地进行 DFS。
- 如果无法继续深度遍历(即当前顶点没有未访问的邻居),则回溯到上一个顶点,继续遍历其他未访问的邻居。
- 重复步骤 2 和步骤 3,直到所有顶点都被访问。
图中 DFS 实现的框架与 树的遍历 类似,不同点在于需要使用 visit
数组记录已经访问过的节点,避免重复遍历:
function DFS(G, v, visited):
visited[v] ← true
for each neighbor u of v in G.adjacent[v]:
if not visited[u]:
DFS(G, u, visited)
图在邻接矩阵和邻接表中的 DFS 都遵循这个框架,两者的不同点在于获取 v 的邻居 u 的方式不同。
邻接矩阵
在邻接矩阵中,我们定义一个递归函数 dfs,函数从 start 顶点出发,输出当前结点,然后递归地去访问所有与其相邻的顶点。
注意递归前需要保证下一个顶点未被访问过,这样可以避免重复访问结点以及死循环。
// 全局变量,标记顶点是否被访问过
int visited[MAX_VERTICES];
// 递归函数,从 start 顶点出发
void dfs(int start) {
visited[start] = 1;
printf("%d ", start);
// 依次访问 start 的邻接顶点
for (int i = 0; i < MAX_VERTICES; i++) {
// 递归的两个条件:
// 1. 顶点 (start, i) 之间存在边
// 2. 顶点 i 未被访问过
if (adjMatrix[start][i] == 1 && !visited[i]) {
// 递归调用
dfs(i);
}
}
}
邻接表
邻接表的递归思路与邻接矩阵一致,唯一的区别就是访问邻接顶点方式的不同。
在邻接矩阵中,通过遍历矩阵中的一行来访问相邻顶点。在邻接表中,通过遍历链表来访问相邻顶点。
// 全局变量,标记顶点是否被访问过
int visited[MAX_VERTICES];
// 递归函数,从 start 顶点出发
void dfs(struct Graph* graph, int start) {
visited[start] = 1;
printf("%d ", start);
// 依次访问 start 的邻接顶点
struct Node* temp = graph->adjacencyList[start];
while (temp) {
int adjVertex = temp->data;
// 递归条件:顶点 i 未被访问过
if (!visited[adjVertex]) {
dfs(graph, adjVertex);
}
temp = temp->next;
}
}
BFS
广度优先搜索(Breadth-First Search,简称 BFS)是一种用于图的遍历和搜索的算法,它从图中的一个起始顶点开始,逐层地访问与该顶点相邻的顶点,然后再访问这些相邻顶点的邻居,以此类推。BFS 通常用队列来实现,确保按照广度优先的顺序访问顶点。
以下是 BFS 算法的一般步骤:
- 将起始顶点放入队列中,标记为已访问。
- 从队列中弹出一个顶点并访问它。
- 遍历该顶点的所有未被访问的邻居,将它们放入队列中,并标记为已访问。
- 重复步骤 2 和步骤 3,直到队列为空。
BFS 的伪代码实现如下所示,基于邻接矩阵或邻接表的 BFS 都遵循这个框架:
function BFS(G, start):
visited[start] ← true
enqueue(Q, start)
while Q is not empty:
v ← dequeue(Q)
process(v)
for each neighbor u of v in G.adjacent[v]:
if not visited[u]:
visited[u] ← true
enqueue(Q, u)
邻接矩阵
实现 bfs 时,首先添加起始顶点进入队列中,然后不断从队列中取出顶点,并添加该顶点的未访问相邻顶点进入队列。 重复直到队列为空。
在 dfs 中,visited 数组是各个递归函数都需要访问的数据结构,为了方便起见,可以定义为全局变量。 在 bfs 中,由于算法实现是基于迭代而非递归,所以 visited 和 队列 可以定义为局部变量。
// 从 start 开始遍历图
void bfs(int start, int vertices) {
// 队列 q
queue q;
// 标记顶点是否被访问过
int visited[MAX_VERTICES];
// 添加初始顶点
q.enqueue(start);
visited[start] = 1;
// 一直遍历到队列为空
while (q.size() > 0) {
// 从队列头部取出结点作为当前结点
int currentVertex = q.dequeue();
// 输出当前结点
printf("%d ", currentVertex);
// 将当前结点的所有 相邻的未访问顶点 添加到队列中
for (int i = 0; i < vertices; i++) {
if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {
q.enqueue(i);
visited[i] = 1;
}
}
}
}
邻接表
实现思路与邻接矩阵方式一致,不同点在与访问相邻顶点的方式不同。
void bfs(struct Graph* graph, int start) {
// 队列 q
queue q;
// 标记顶点是否被访问过
int visited[MAX_VERTICES];
// 添加初始顶点
q.enqueue(start);
visited[start] = 1;
// 一直遍历到队列为空
while (front != rear) {
// 从队列头部取出结点作为当前结点
int currentVertex = q.dequeue();
// 输出当前结点
printf("%d ", currentVertex);
// 将当前结点的所有 相邻的未访问顶点 添加到队列中
struct Node* temp = graph->adjacencyList[currentVertex];
while (temp) {
int adjVertex = temp->data;
if (!visited[adjVertex]) {
q.enqueue(adjVertex);
visited[adjVertex] = 1;
}
temp = temp->next;
}
}
}
最小生成树
最小生成树(Minimum Spanning Tree,MST)是在一个连接所有顶点的无向图中,通过选择一部分边而形成的树,使得树的总权重(或成本)最小。
准确的最小生成树定义如下:在无向图 $G = (V, E)$ 中,$(u, v)$ 代表连接顶点 $u$ 和顶点 $v$ 的边,而 $w(u, v)$ 代表此边的权重,若存在 $T$ 为 $E$ 的子集且 $(V, E)$ 为树,使得 $w(T) = \sum_{(u, v) \in T} w(u, v)$ 最小,则此 $T$ 为 $G$ 的最小生成树。
最小生成树满足以下特点:
- 包含图中的所有顶点。
- 通过选择一些边而形成一个树结构,没有环路。
- 边的总权重最小。
prim 算法
Prim 算法的主要思想是从一个初始顶点开始,逐步扩展生成树,每次选择与当前生成树相邻且权重最小的边所连接的顶点,并将该顶点加入生成树。算法的运行过程可以概括为以下步骤:
- 选择一个起始顶点作为生成树的根节点。
- 初始化一个空的生成树,包含初始顶点。
- 将与生成树中的顶点相邻且权重最小的边的另一端顶点加入生成树,即选择一条最小权重边。
- 重复步骤 3,直到生成树包含了所有的顶点。
- 最终生成树即为原图的最小生成树。
kruskal 算法
Kruskal 算法是一种用于求解最小生成树(Minimum Spanning Tree,MST)的贪心算法。Kruskal 算法的基本思想是从边的权重最小的边开始,逐步构建生成树,确保不会形成环路。
以下是 Kruskal 算法的一般流程:
- 初始化一个空的生成树,开始时生成树中没有边。
- 将图中的所有边按照权重从小到大进行排序。
- 依次从排序后的边列表中选取边,加入生成树,但要确保添加该边不会形成环路。可以使用并查集来检查是否形成环路。
- 重复步骤 3,直到生成树包含了所有的顶点,即生成树中的边数等于顶点数减 1。
- 返回生成树作为最小生成树。
最短路径
dijkstra 算法
Dijkstra 算法是一种用于计算 单源最短路径 的经典算法,适用于 带非负权重的有向或无向图。
Dijkstra 算法是一种贪心算法。它从起点开始,维护一组已知的最短路径,每次从所有未处理的顶点中选择一个当前距离起点最短的顶点,将其加入“最短路径已确定”的集合,并通过它尝试更新其邻居的最短路径。该过程重复,直到所有顶点的最短路径都被确定。
🛠️ 算法需要定义以下数据结构:
dist[]
: 一个数组,dist[v]
表示起点到节点v
的当前最短路径长度,初始化为 ∞,起点为 0。visited[]
: 一个布尔数组,记录哪些节点的最短路径已被确定。
✨ 算法具体流程如下:
- 初始化
dist[source] ← 0
- 其他
dist[v] ← ∞
- 所有
visited[v] ← false
- 主循环(直到所有顶点都被访问)
- 找出未访问的、
dist[]
值最小的节点u
- 标记
visited[u] ← true
- 对于
u
的每个邻居v
:- 如果
v
未访问,且dist[u] + w(u,v) < dist[v]
,则更新dist[v] ← dist[u] + w(u,v)
- 如果
- 找出未访问的、
- 结束
- 所有最短路径保存在
dist[]
中
- 所有最短路径保存在
Dijkstra 的考察侧重于手工模拟其过程,代码实现一般不会考察,这里给出算法的简单伪代码实现,帮助各位理清其中的处理细节。
function Dijkstra_Simple(Graph, source):
对于图中每个顶点 v:
dist[v] ← ∞ // 起点到 v 的距离初始化为无穷大
visited[v] ← false // 所有顶点初始都未被访问
dist[source] ← 0 // 起点到自身距离为 0
重复 |图中顶点数| 次:
u ← 所有未访问的顶点中 dist[u] 最小的顶点
visited[u] ← true // 标记 u 已被访问
对于 u 的每个相邻顶点 v:
边权重 weight ← 图中边(u, v) 的权重
如果 v 未访问 且 dist[v] > dist[u] + weight:
dist[v] ← dist[u] + weight // 通过 u 到 v 更短,更新最短路径
return dist[] // 表示起点到所有顶点的最短路径
假设顶点的个数为 $V$,边的个数为 $E$,那么最佳实现(使用了优先队列)的 dijkstra 算法时间复杂度为 $O(V+E)$。
floyd 算法
Floyd Warshall 是一种基于动态规划的方法,用于求解任意两个顶点之间的最短路径,它适用于带权有向图。
该算法的核心思想是尝试使用每一个顶点作为中转点,逐步更新所有顶点对之间的最短路径。对任意两点 $i → j$,判断是否可以通过一个中间点 $k$ 得到更短路径:
$$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])$$
这个过程会遍历所有可能的中转点 $k$,不断优化路径。
✨ 算法具体流程如下:
- 初始化距离矩阵
dist
:dist[i][j] = 0
(若i=j
)dist[i][j] = 边权
(若i→j
有边)dist[i][j] = ∞
(其余情况)
- 三重循环更新最短路径
for k in 所有顶点: for i in 所有顶点: for j in 所有顶点: if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] ← dist[i][k] + dist[k][j]
- 输出 dist 矩阵 :表示所有顶点对之间的最短路径长度。
若顶点数为 $n$,则 Floyd Warshall 算法的时间复杂度为 $O(n^3)$,该算法适合在算法题中兜底使用,因为实现比较简单,建议大家熟练掌握代码实现。
拓扑排序
拓扑排序这样一种对图中顶点的排序方式:
将图中的所有顶点排序,使得对于每一条有向边
u
→v
,顶点u
都排在v
之前。
拓扑排序主要应用于 DAG(有向无环图)或 AOV 网,这种图没有环路,因此可以对其进行拓扑排序。
首先需要区分 AOV 和 AOE 这两个概念,注意拓扑排序适用于 AOV,关键路径适用于 AOE。
AOV 网
AOV(Activity on Vertex Network)网是一种以顶点表示活动或任务的网络模型。每个顶点代表一个任务或活动,而边表示任务之间的依赖关系。在 AOV 网中,任务或活动通常表示为顶点,而依赖关系(任务的先后顺序)表示为有向边。
AOE 网
AOE(Activity on Edge Network)网是一种以边表示活动或任务的网络模型。每条边代表一个任务或活动,而顶点通常表示事件,表示任务的开始或完成时间。在 AOE 网中,任务的持续时间通常不包含在边上,而是与边相连的事件顶点之间的时间差。
算法步骤
计算拓扑排序的算法有两种,一种是 Kahn 算法(基于入度),另一种是 DFS+栈 的实现。
Kahn算法Kahn 算法的核心思想是 依次选取入度为 0 的顶点进行输出,其具体步骤如下:
- 选择一个没有前驱顶点(入度为 0)的顶点作为起始顶点,将其加入拓扑排序的结果序列中。
- 从图中移除该顶点以及与之相关的边(即将与之相邻的顶点的入度减 1)。
- 重复步骤 1 和步骤 2,直到所有的顶点都被加入到拓扑排序的结果序列中,或者发现图中存在环路。
- 如果所有的顶点都被成功加入结果序列,那么这个序列就是拓扑排序的结果。
下图展示了一个采用 Kahn 算法输出 AOE 网中的拓扑序列的实例:
此外,可以通过 DFS+栈 得到拓扑序列,其步骤如下:
- 对图进行深度优先遍历。
- 每个节点 DFS 结束后将其压入栈中。
- 最后将栈中元素逆序输出,就是拓扑排序结果。
DFS 过程中,每个节点在其所有后继节点访问完成后才被加入栈中,因此栈中元素的逆序正好满足拓扑排序所需的“前驱先于后继”的约束。
拓扑排序的时间复杂度通常为 $O(V + E)$ ,其中 $V$ 是顶点的数量, $E$ 是边的数量。这个算法非常适合于解决任务调度和依赖关系问题,因为它可以确定任务的执行顺序或依赖关系的合理性。
关于拓扑排序,还需要关注以下几点:
拓扑排序的结果可能不唯一,因为在构建过程中往往会出现多个入度为 0 的顶点,不同的选择顺序会产生不同的合法排序结果。
如果图中 存在环路,那么无法进行拓扑排序,因为无法找到入度为 0 的顶点作为起始顶点。
关键路径
关键路径是从源点到汇点的最长路径,由于这条路径是 AOE 网 中最长的路径,所以这条路径直接决定了最短工期,所以该路径被称为 关键 路径。
为了理解关键路径,首先需要明确以下概念:
- 源点:在 $AOE$ 网中仅有一个入度为 $0$ 的顶点,称为开始顶点,表示整个工程的开始。
- 汇点:在 $AOE$ 网中仅有一个出度为 $0$ 的顶点,称为结束结点,表示整个工程的结束。
- 关键路径的长度:完成整个工程的最短时间,也是 $AOE$ 网中从源点到汇点的最长路径。
- 关键活动:关键路径上的活动。
- $ve(k)$:事件 $v_k$ 的最早可以发生时间。
- $vl(k)$:事件 $v_k$ 的最晚可以发生时间。
算法步骤
求解关键路径的 核心思路 在于找到所有最早发生时间和最晚发生时间相同的结点,连接这些结点即可得到关键路径。
所以在求关键路径的算法中,我们需要依次计算每个顶点的最早发生时间(ve)和最晚发生时间(vk),然后判断哪些顶点的 ve 和 vk 相等。
具体步骤:
- 从源点出发,令 $ve(start) = 0$ ,按照拓扑排序求其他顶点的最早发生时间 $ve$ 。
- 对于源点:$ve(start) = 0$。
- 对于后续结点:$ve(k) = \text{Max} \{ ve(j) + weight(v_j, v_k) \}$,$v_k$ 为 $v_j$ 的任意后继,$weight(v_j, v_k)$ 表示 $<v_j, v_k>$ 的权值。
- 从汇点出发,令 $vl(end) = ve(end)$,按逆拓扑有序求其余顶点的最迟发生时间 $vl$。
- 对于汇点:$vl(end) = 0$。
- 对于前继结点:$vl(k) = \text{Min} \{ vl(j) - weight(v_k, v_j) \}$,$v_k$ 为 $v_j$ 的任意前驱。
- 连接所有 $ve(i) = vl(i)$ 的结点 $i$,得到关键路径。下图中例子中所有 $ve$ 和 $vl$ 相同的结点为$v_1, v_3, v_4, v_6$,其对应的关键路径为 $v_1 \rightarrow v_3 \rightarrow v_4 \rightarrow v_6$ 即 $a_2, a_5, a_7$。
关键路径的特点:
- 关键路径上的所有活动都是关键活动,它是决定整个工程的关键因素,因此可通过加快关键活动来缩短整个工程的工期。
- AOE 网中的关键路径并不唯一,对于有几条关键路径的网,只加快一条关键路径,需要同时加快多个关键路径。
用图表达树
当表达式中存在共享的子表达式时,二叉树可能不是存储这些表达式的最有效方式,因为它会重复存储共享的子表达式。在这种情况下,可以使用有向无环图(Directed Acyclic Graph, DAG)来表示表达式,这样可以避免重复,并且更有效地表示表达式。
比如对于表达式 (x + y) * ((x + y) / x)
,用二叉树和 DAG 的表示如下图: