代码随想录算法训练营 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;// 与 Prim 相似度达到 90%
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;// 存储从原点到每个节点的最短距离vector<int> minDist(n+1, INT_MAX);// 记录节点访问情况 prim是isTree标记vector<bool> vis(n+1, false);minDist[start] = 0; // 起始点到自身距离为0// 遍历所有节点计算最短距离for (int i = 1; i <= n; ++i) {int minVal = INT_MAX;int cur = 1;// prim 1.选择距离生成树最近的节点// dijkstra 1.选择距离原点最近尾访问过的节点for (int v = 1; v <= n; ++v) {if (!vis[v] && minDist[v] < minVal) {minVal = minDist[v];cur = v;}}// prim 2.最近节点加入生成树// dijkstra 2.标记访问vis[cur] = true;// prim 3.更新非生成树到生成树的距离// dijkstra 3.更新非访问节点到原点距离 与Prim的核心不同点for (int v = 1; v <= n; ++v) {// cur为当前最小距离节点值if (!vis[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {minDist[v] = minDist[cur] + grid[cur][v];}}}if (minDist[end] == INT_MAX) cout << -1 << endl;else cout << minDist[end] << endl; // 抵达终点return 0;
}

Prim 算法

#include <iostream>
#include <vector>
#include <climits>using namespace std;int main() {// 构造图int v, e;cin >> v >> e;int x, y, k;// 构造最大值10001vector<vector<int>> grid(v+1, vector<int>(v+1, 10001));for (int i = 0; i < e; ++i) {cin >> x >> y >> k;grid[x][y] = k;grid[y][x] = k;}// 所有节点到最小生成树的距离vector<int> minDist(v+1, 10001);// 节点是否在最小生成树中vector<bool> isTree(v+1, false);// 最小生成树只需要v-1条边就可以链接n个顶点 序号从1开始for (int i = 1; i < v; ++i) {// prim 三部曲 1 选择距离生成树最近的节点int cur = -1;int minVal = INT_MAX;// 遍历当前顶点 寻找 1.不在生成树内 2.最近生成树的节点for (int j = 1; j <= v; ++j) {if (!isTree[j] && minDist[j] < minVal) {minVal = minDist[j];cur = j;}}// prim 三部曲 2 最近节点加入生成树isTree[cur] = true;// prim 三部曲 3 更新非生成树到生成树的距离 即更新 minDist数组for (int j = 1; j <= v; ++j) {// 更新条件 1.不在生成树中 2.与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小if (!isTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}}}// 统计总距离int res = 0;for (int i = 2; i <= v; ++i) {res += minDist[i];}cout << res << endl;
}

打印 dijkstra 算法的路径

#include <iostream>
#include <vector>
#include <climits>using namespace std;int main() {int n, m, x, y, val;cin >> n >> m;vector<vector<int>> grid(n+1, vector<int>(n+1, INT_MAX));vector<int> minDist(n+1, INT_MAX);vector<bool> vis(n+1, false);vector<int> parent(n+1, -1); // 打印路径使用for (int i = 0; i < m; ++i) {cin >> x >> y >> val;grid[x][y] = val;}int start = 1;int end = n;for (int i = 1; i <= n; ++i) {int cur = 1;int minVal = INT_MAX;// 1for (int v = 1; v <= n; ++v) {if (!vis[v] && minDist[v] < minVal) {minVal = minDist[v];cur = v;}}// 2vis[cur] = true;// 3for (int v = 1; v <= n; ++v) {if (!vis[v] && grid[cur][v] != INT_MAX && grid[cur][v] + minDist[cur] < minDist[v]) {minDist[v] = grid[cur][v] + minDist[cur];parent[v] = cur;}}}// 输出边for (int i = 1; i <=n; ++i) {cout << parent[i] << "->" << i << endl;}
}