代码随想录算法训练营 Day58 图论Ⅷ 拓扑排序 Dijkstra

图论

题目

117. 软件构建
拓扑排序：给出一个有向图，把这个有向图转成线性的排序就叫拓扑排序。
当然拓扑排序也要检测这个有向图是否有环，即存在循环依赖的情况，因为这种情况是不能做线性排序的。所以拓扑排序也是图论中判断有向无环图的常用方法。
本题使用 BFS 的拓扑排序思路

寻找出发边，特征是入度为0 出度为2，也就是没有边指向它，而它有两条边是指出去的。
接下来我给出拓扑排序的过程，其实就两步：
1. 找到入度为0 的节点，加入结果集
2. 将该节点从图中移除
循环以上两步，直到所有节点都在图中被移除了。
模拟过程

如果有环出现

这个图，我们只能将入度为0 的节点0 接入结果集。
之后，节点1、2、3、4 形成了环，找不到入度为0 的节点了，所以此时结果集里只有一个元素。
那么如果我们发现结果集元素个数不等于图中节点个数，我们就可以认定图中一定有有向环！
这也是拓扑排序判断有向环的方法。

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

int main() {
    int m, n, s, t;
    cin >> n >> m;
    // 记录入度
    vector<int> inDegree(n, 0);
    // 使用邻接表记录图依赖关系
    unordered_map<int, vector<int>> umap;
    // 记录结果
    vector<int> res;
    for (int i = 0; i < m; ++i) {
        cin >> s >> t;
        inDegree[t]++;
        umap[s].push_back(t);
    }
    // 拓扑排序开始
    queue<int> que;
    // 寻找入度为0的元素加入队列
    for (int i = 0; i < n; ++i) {
        if (inDegree[i] == 0) que.push(i);
    }
    while (!que.empty()) {
        // 当前节点
        int cur = que.front();
        que.pop();
        res.push_back(cur);
        // 遍历节点指向
        for (int idx : umap[cur]) {
            inDegree[idx]--; // 通过 入度-- 实现图中删除这个节点
            if (inDegree[idx] == 0) que.push(idx);
        }
    }

    // 若不等于n说明有向图中有环
    if (res.size() == n) {
        for (int i = 0; i < n-1; ++i) {
            cout << res[i] << " ";
        }
        cout << res[n-1] << endl;
    }
    else cout << -1 << endl;
}

47. 参加科学大会（第六期模拟笔试）
最短路径 dijkstra 算法，求图中最短路径

思路
类似于 prim 算法，dijkstra 算法 同样是贪心的思路，不断寻找距离 源点最近的没有访问过的节点。
这里我也给出 dijkstra三部曲：
1. 第一步，选源点到哪个节点近且该节点未被访问过
2. 第二步，该最近节点被标记访问过
3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）
在dijkstra算法中，同样有一个数组很重要，起名为：minDist。
minDist数组用来记录每一个节点距离源点的最小距离。
理解这一点很重要，也是理解 dijkstra 算法的核心所在。
朴素算法
初始化节点这里在强点一下 minDist数组的含义：记录所有节点到源点的最短路径，那么初始化的时候就应该初始为最大值，这样才能在后续出现最短路径的时候及时更新。

（图中，max 表示默认值，节点0 不做处理，统一从下标1 开始计算，这样下标和节点数值统一，方便大家理解，避免搞混）
源点（节点1） 到自己的距离为0，所以 minDist[1] = 0
此时所有节点都没有被访问过，所以 visited数组都为0
以下为dijkstra 三部曲
1、选源点到哪个节点近且该节点未被访问过，源点距离源点最近，距离为0，且未被访问。
2、该最近节点被标记访问过，标记源点访问过
3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：

更新 minDist数组，即：源点（节点1） 到 节点2 和 节点3的距离。
- 源点到节点2的最短距离为1，小于原minDist[2]的数值max，更新minDist[2] = 1
- 源点到节点3的最短距离为4，小于原minDist[3]的数值max，更新minDist[3] = 4
可能有录友问：为啥和 minDist[2] 比较？
再强调一下 minDist[2] 的含义，它表示源点到节点2的最短距离，那么目前我们得到了源点到节点2的最短距离为1，小于默认值max，所以更新。 minDist[3]的更新同理

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2] = val;
    }

    int start = 1;
    int end = n;

    std::vector<int> minDist(n + 1, INT_MAX);

    std::vector<bool> visited(n + 1, false);

    minDist[start] = 0; 

    //加上初始化
    vector<int> parent(n + 1, -1);

    for (int i = 1; i <= n; i++) {

        int minVal = INT_MAX;
        int cur = 1;

        for (int v = 1; v <= n; ++v) {
            if (!visited[v] && minDist[v] < minVal) {
                minVal = minDist[v];
                cur = v;
            }
        }

        visited[cur] = true;

        for (int v = 1; v <= n; v++) {
            if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {
                minDist[v] = minDist[cur] + grid[cur][v];
                parent[v] = cur; // 记录边
            }
        }

    }

    // 输出最短情况
    for (int i = 1; i <= n; i++) {
        cout << parent[i] << "->" << i << endl;
    }
}