当前位置：首页 > ds >正文

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

ds 2025/8/28 8:14:52

图论

题目

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;}
}