算法和应用

DFS

深度优先搜索（Depth-First Search，简称 DFS）是一种用于图的遍历和搜索的算法，它从图中的一个起始顶点开始，尽可能深地访问顶点，直到无法继续前进，然后回溯到之前的顶点，继续深入其他分支。DFS 通常用递归或栈来实现，确保在深度方向上优先遍历。

以下是 DFS 算法的一般步骤：

1. 从起始顶点开始，将其标记为已访问。
2. 遍历与当前顶点相邻的未访问顶点，选择其中一个未访问顶点作为下一个深度遍历的目标，然后递归地进行 DFS。
3. 如果无法继续深度遍历（即当前顶点没有未访问的邻居），则回溯到上一个顶点，继续遍历其他未访问的邻居。
4. 重复步骤 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 算法的一般步骤：

1. 将起始顶点放入队列中，标记为已访问。
2. 从队列中弹出一个顶点并访问它。
3. 遍历该顶点的所有未被访问的邻居，将它们放入队列中，并标记为已访问。
4. 重复步骤 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）是在一个连接所有顶点的无向图中，通过选择一部分边而形成的树，使得树的总权重（或成本）最小。

准确的 MST 定义如下：在无向图 $G = (V, E)$ 中，$(u, v)$ 代表连接顶点 $u$ 和顶点 $v$ 的边，而 $w(u, v)$ 代表此边的权重，若存在 $T$ 为 $E$ 的子集且 $(V, T)$ 为树，使得 $w(T) = \sum_{(u, v) \in T} w(u, v)$ 最小，则此 $T$ 为 $G$ 的 最小生成树。

MST 满足以下特点：

• 包含图中的所有顶点。
• 通过选择一些边而形成一个树结构，没有环路。
• 边的总权重最小。

prim 算法

Prim 算法通过 逐步扩展顶点集合 来构建最小生成树：从一个初始顶点出发，每次都选择一条 连接生成树与外部顶点的最小权重边，并将该顶点并入生成树，直到所有顶点都被包含。

prim 算法步骤 如下：

1. 选定一个起始顶点作为生成树的根。
2. 初始化生成树，只含有该顶点。
3. 在所有 连接生成树与未加入顶点的边 中，选取权重最小的一条，并将对应顶点加入生成树。
4. 重复步骤 3，直到所有顶点均被纳入生成树。
5. 得到的生成树即为原图的 最小生成树。

参考 prim 算法的流程图如下：

举个实际例子，对于以下的无向图，假设我们从顶点 a 出发使用 prim 算法寻找最小生成树，会逐步选择出 ab、bc、ci、cf、fg、gh、cd 以得到最小生成树：

kruskal 算法

Kruskal 算法是一种用于求解 最小生成树（MST）的贪心算法。Kruskal 算法的基本思想是从边的权重最小的边开始，逐步构建生成树，确保不会形成环路。

以下是 Kruskal 算法的一般流程：

1. 初始化一个空的生成树，开始时生成树中没有边。
2. 将图中的所有边按照权重 从小到大进行排序。
3. 依次 从排序后的边列表中选取边，加入生成树，但要确保 添加该边不会形成环路。
4. 重复步骤 3，直到生成树包含了所有的顶点，即生成树中的边数等于顶点数减 1。
5. 返回生成树作为 最小生成树。

参考 kruskal 算法的流程图如下：

继续使用上文中 prim 中的无向图作为例子，使用 kruskal 算法，会依次选择 hg、ic、gf、ab、cf、cd、ah 以得到最小生成树：

最短路径

dijkstra 算法

Dijkstra 算法是一种用于计算 单源最短路径 的经典算法，适用于 带非负权重 的有向或无向图。

Dijkstra 算法是一种 贪心算法。它的 核心思想 是：从起点出发，不断“扩展”到距离起点最近的节点，并利用这些节点去尝试更新其他节点的最短路径，直到所有节点的最短路径都被确定。

换句话说，算法始终保持一个 “已确定最短路径的集合”，并且在每一步中把离起点最近的“候选节点”加入其中：

🛠️ dijkstra 算法需要定义以下 数据结构：

• dist[]：数组，dist[v] 表示起点到节点 v 的 当前已知最短路径长度。
  • 初始化时：dist[source] = 0，其余节点均为 ∞。
• visited[]：布尔数组，表示某个节点的最短路径是否已经被最终确定。
  • 初始时：所有节点均为 false。

✨ dijkstra 算法流程   如下：

1. 初始化
   • 设起点为 source。
   • dist[source] ← 0
   • 对于其他顶点 v，dist[v] ← ∞
   • visited[v] ← false
2. 主循环（重复 |V| 次，即所有顶点都被处理完）
   • 从所有 未访问 的顶点中，找到一个 dist[] 值最小的顶点 u。 （这意味着：当前已知路径中，u 是离起点最近的尚未确定的节点。）
   • 将该顶点标记为已访问：visited[u] ← true。
   • 对于 u 的每个邻居 v：
     • 如果 v 未被访问，并且通过 u 到达 v 的路径更短（即 dist[u] + w(u,v) < dist[v]）， 则更新：

       dist[v] ← dist[u] + w(u,v)
       

       （这一步就是“松弛操作”，表示尝试通过 u 改进到 v 的最短路径。）
3. 结束
   • 当所有顶点都被访问后，dist[v] 就保存了起点到各个顶点的最短路径长度。

Dijkstra 算法流程可以通过以下流程图理解：

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$，不断优化路径。

✨ 算法具体流程如下：

1. 初始化距离矩阵 dist：

   • dist[i][j] = 0（若 i=j）
   • dist[i][j] = 边权（若 i→j 有边）
   • dist[i][j] = ∞（其余情况）

2. 三重循环更新最短路径

   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]
   

3. 输出 dist 矩阵 ：表示所有顶点对之间的最短路径长度。

若顶点数为 $n$，则 Floyd Warshall 算法的时间复杂度为 $O(n^3)$，该算法适合在算法题中兜底使用，因为实现比较简单，建议大家熟练掌握代码实现。

拓扑排序

拓扑排序 这样一种对图中顶点的排序方式：

将图中的所有顶点排序，使得对于每一条有向边 u → v，顶点 u 都排在 v 之前。

拓扑排序 主要应用于 DAG（有向无环图）或 AOV 网，这种图没有环路，因此可以对其进行拓扑排序。

首先需要区分 AOV 和 AOE 这两个概念，注意 拓扑排序 适用于 AOV，关键路径 适用于 AOE。

AOV 网

AOV（Activity on Vertex Network）网是一种以顶点表示活动或任务的网络模型。每个 顶点 代表一个 任务或活动，而 边 表示任务之间的 依赖关系。在AOV网中，任务或活动通常表示为顶点，而依赖关系（任务的先后顺序）表示为有向边。