代码随想录算法训练营Day64|拓扑排序（卡码网117）、dijkstra朴素版

拓扑排序

117. 软件构建 (kamacoder.com)

拓扑排序简单的说是将一个有向图转为线性的排序。

它将图中的所有结点排序成一个线性序列，使得对于任何的边uv，结点u在序列中都出现在结点v之前，这样的序列满足图中所有的前驱-后继关系。

拓扑排序通常用于任务调度、项目计划、编译依赖分析等场景，其中活动或任务之间存在依赖关系，需要确定一个合理的执行顺序。

拓扑排序的算法步骤如下：

1. 选择一个没有前驱的结点（即入度为0的结点），将其加入到拓扑排序的序列中，并从图中删除该节点及其所有出边。
2. 重复步骤1，直到所有的结点都被加入拓扑排序序列中或者途中不再存在无前驱的结点。
3. 如果所有的结点都被加入序列中，则完成了拓扑排序；若图中还存在结点，则说明图中存在环，无法进行拓扑排序。

        由于拓扑排序的结果可能不唯一，当图中存在多个入度为0的结点，可以任意选择一个结点进行删除。

在实际应用中，拓扑排序通常和深度优先搜索或广度优先搜素结合使用。例如，使用广度优先搜索（拓扑排序的广度优先搜索实现通常被称为Kahn算法）进行拓扑排序的算法流程如下：

1. 计算所有节点的入度：遍历图中的所有节点，计算每个节点的入度（即有多少边指向该节点）。

2. 初始化队列：创建一个空队列，将所有入度为0的节点加入队列。这些节点是没有前置依赖的节点，可以开始执行。

3. 处理队列：只要队列不为空，就重复以下步骤：

   • 从队列中取出一个节点（称为当前节点），并将其添加到拓扑排序的结果序列中。
   • 减少当前节点的所有出边指向的节点的入度（因为这些节点的依赖减少了）。
   • 如果某个节点的入度在减少后变为0，则将其加入队列，因为它现在没有前置依赖了。

4. 检查是否有未处理的节点：当队列为空时，如果所有的节点都已经添加到拓扑排序的结果序列中，则拓扑排序成功完成。如果还有节点未添加到结果序列中，则说明图中存在环，因此无法进行拓扑排序。

伪代码

拓扑排序(图 G):
    初始化入度为0的队列 Q
    初始化拓扑排序的结果序列 L

    // 计算所有节点的入度
    对于每个节点 v in G:
        v.入度 = G 中指向 v 的边的数量
        如果 v.入度 == 0:
            Q.enqueue(v)

    // 处理队列
    当 Q 不为空时:
        当前节点 u = Q.dequeue()
        L.add(u)  // 将 u 添加到拓扑排序的结果序列中

        // 减少所有出边的目标节点的入度
        对于每个节点 v，其中存在边 u -> v:
            v.入度 = v.入度 - 1
            如果 v.入度 == 0:
                Q.enqueue(v)

    // 检查是否所有节点都已处理
    如果 L 中的节点数量不等于 G 中的节点数量:
        返回 "图 G 包含环，无法进行拓扑排序"
    否则:
        返回 L 作为拓扑排序的结果序列

C++代码参考代码随想录代码随想录 (programmercarl.com)

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

int main() {
    int N, M; // N个文件存在M条依赖关系
    cin >> N >> M;
    vector<int> inDegree(N, 0); // 记录每个点的入度
    unordered_map<int, vector<int>> umap;

    // 读取M条依赖关系
    for (int i = 0; i < M; i++) {
        int s, t;
        cin >> s >> t;
        // t依赖于s，因此t的入度加1
        inDegree[t]++;
        umap[s].push_back(t);
    }

    queue<int> Queue;
    // 将所有入度为0的节点加入队列
    for (int i = 0; i < N; i++) {
        if (inDegree[i] == 0)
            Queue.push(i);
    }

    vector<int> path; // 存储拓扑排序结果
    while (!Queue.empty()) {
        int cur = Queue.front();
        Queue.pop();
        path.push_back(cur);

        // 遍历当前节点的所有后继节点
        for (int next : umap[cur]) {
            inDegree[next]--;
            if (inDegree[next] == 0)
                Queue.push(next);
        }
    }

    // 检查是否所有的节点都被处理了
    if (path.size() == N) {
        for (int i = 0; i < N - 1; i++) {
            cout << path[i] << " ";
        }
        cout << path[N - 1];
    } else {
        // 如果不是所有的节点都被处理，说明存在环
        cout << -1 << endl;
    }

    return 0;
}

在时间复杂度上，初始化入度数组O(N)，读取依赖关系并构建邻接表O(M)(M条依赖关系)，将入度为0结点加入队列，O(N)，BFS的时间复杂度为O(N+M)(每个结点最多访问一次，每个结点被加入队列后移除，每条边会被访问一次来减少相邻结点的入度)时间复杂度为O(N+M）

空间复杂度 入度数组O(N)，邻接表最差情况下O(N^2)，队列和路径数组都为O(N)，最差情况下空间复杂度为O(N^2)，但实际应用中，若图比较稀疏，则空间复杂度为O(M+N)。

dijkstra

47. 参加科学大会（第六期模拟笔试） (kamacoder.com)

        Dijkatra算法是一种著名的图搜索算法，它用于在加权图中找到从一源节点到其余所有结点的最短路径。

算法步骤：

1. 初始化：需要一个最短路径估计的容器（优先队列，通常是最小堆）存储所有结点及其当前的最短路径估计值，除源节点设置为0外，将所有结点的最短路径估计值设置为无穷大。
2. 访问源结点：将源结点加入优先队列。
3. 循环处理队列：当优先队列非空时，重复以下步骤：

   从优先队列中取出具有最小估计值的节点，称为当前节点。

   对于当前节点的每个邻接节点，执行以下操作：

   1. 计算通过当前节点到达邻接节点的路径长度。
   2. 如果这个路径长度比已知的最短路径估计值更短，则更新邻接节点的最短路径估计值，并更新它的前驱节点为当前节点。
   3. 将邻接节点及其新的最短路径估计值加入优先队列。 

4. 标记完成：当一个结点从优先队列取出时，意味着它的最短路径已经确定，可以将其标记为完成。
5. 构建最短路径树：当算法结束时，可以从源结点开始，通过每个结点的前驱结点信息，构造出从源结点到所有其他结点的最短路径树。

需要注意的几个点：

• Dijkstra算法不能处理带有负权边的图，因为在有负权边的图中，可能存在一条路径，其总权重随着经过的边数增加而减少，导致无法正确找到最短路径。
• Dijkstra算法的时间复杂度为O(V^2)，V为图中结点的数量，使用优先队列可以优化到O(E+VlogV),E为边的数量、
• Dijkstra可以用于有向图和无向图。

代码随想录 (programmercarl.com)

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int N, M; // N个文件存在M条依赖关系
    cin >> N >> M;
    vector<vector<int>> grid(N+1, vector<int>(N+1, INT_MAX)); // 创建一个N+1xN+1的二维数组，用于存储节点之间的权重，初始化为INT_MAX
    int v1, v2, val;
    for (int i = 0; i < M; i++) { // 读取M条依赖关系
        cin >> v1 >> v2 >> val; // 读取两个节点v1和v2以及它们之间的权重val
        grid[v1][v2] = val; // 更新权重矩阵，表示v1到v2有边，权重为val
    }
    int start = 1; // 定义起始节点为1
    int end = N; // 定义目标节点为N
    vector<int> minDist(N+1, INT_MAX); // 创建一个长度为N+1的数组，用于存储从起始节点到其他节点的最短路径估计值，初始化为INT_MAX
    vector<int> visited(N+1, 0); // 创建一个长度为N+1的数组，用于标记节点是否被访问过，0表示未访问，1表示已访问
    minDist[start] = 0; // 起始节点到自身的最短路径为0

    for (int i = 0; i <= N; i++) { // 循环，找到未访问的最短路径节点
        int minVal = INT_MAX; // 初始化最小值为INT_MAX
        int cur = 1; // 初始化当前节点为1
        for (int v = 1; v <= N; v++) { // 遍历所有节点，找到未访问且最短路径估计值最小的节点
            if (!visited[v] && minDist[v] < minVal) { // 如果节点v未访问且最短路径估计值小于minVal
                minVal = minDist[v]; // 更新最小值
                cur = v; // 更新当前节点为v
            }
        }
        visited[cur] = 1; // 标记当前节点为已访问
        for (int v = 1; v <= N; v++) { // 遍历所有节点，更新从当前节点出发到其他节点的最短路径估计值
            if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {
                // 如果节点v未访问，且当前节点到节点v有边，且通过当前节点到达v的路径更短
                minDist[v] = minDist[cur] + grid[cur][v]; // 更新节点v的最短路径估计值
            }
        }
    }

    if (minDist[end] == INT_MAX) // 如果目标节点的最短路径估计值仍然是INT_MAX，表示没有路径到达目标节点
        cout << -1 << endl; // 输出-1
    else
        cout << minDist[end] << endl; // 否则输出从起始节点到目标节点的最短路径长度
    return 0;
}

算法的时间复杂度为O(N^2)，空间复杂度这里也是O(N^2)（没有用上最小堆等优先队列）