代码随想录算法训练day64---图论系列8《拓扑排序dijkstra（朴素版）》

代码随想录算法训练

—day64

---

前言

今天是算法营的第64天，希望自己能够坚持下来！
今天继续图论part！今日任务：
● 拓扑排序
●dijkstra（朴素版）

---

一、53. 117. 软件构建—拓扑排序

卡码网题目链接
文章讲解

给出一个 有向图，把这个有向图转成线性的排序 就叫拓扑排序。
适合应用在例如B依赖A，C依赖B，要先有A才能有B，先有B才能有C的依赖关系找出先后顺序的问题。

实现拓扑排序的算法有两种：卡恩算法（BFS）和DFS，一般来说我们只需要掌握 BFS （广度优先搜索）就可以了，清晰易懂。

思路：

找 入度为 0 的节点，只有入度为0，它才是出发节点。
步骤：
1.找到入度为0 的节点，加入结果集
2.该节点指向的节点入度-1

代码如下：

#include<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
using namespace std;int main() {int n, m, s, t;cin >> n >> m;vector<int> inDegree(n, 0); //记录每个文件的入度unordered_map<int, vector<int>> umap; //记录文件的依赖 first指向多个second文件vector<int> result; //记录结果while (m--) {//s->t 先有s才能有tcin >> s >> t;inDegree[t]++;umap[s].push_back(t); //记录s指向哪些文件}//因为会有不只1个文件入度为0，用队列存放入度为0的文件queue<int>que;for (int i = 0; i < n; i++) {if (inDegree[i] == 0) que.push(i);        }//循环从队列中取出文件处理//1.将入度为0的文件加入结果集，2.删掉入度为0的文件while (!que.empty()) {int cur = que.front();que.pop();result.push_back(cur);vector<int> files = umap[cur]; //获取该文件指向的文件for (int j = 0; j < files.size(); j++) {inDegree[files[j]]--; //cur指向的文件入度-1if(inDegree[files[j]] == 0) que.push(files[j]); //新的入度为0的文件加入到队列}}//打印结果if (result.size() == n) {for (int i = 0; i < n - 1; i++) cout << result[i] << " ";cout << result[n - 1]; //最后不包含空格，所以分开打印} else {cout << -1 << endl;}return 0;
}

---

二、47. 参加科学大会—dijkstra（朴素版）

卡码网题目链接
文章讲解

dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。
需要注意两点：

• dijkstra 算法可以同时求 起点到所有节点的最短路径
• 权值不能为负数

dijkstra和prim算法思路很像，只是dijkstra是求最短路径，minDist数组 用来记录 每一个节点距离源点的最小距离；而prim里的minDist数组是记录每个节点到生成树的最小距离。

dijkstra三部曲：
第一步，选源点到哪个节点近且该节点未被访问过
第二步，该最近节点被标记访问过
第三步，更新非访问节点到源点的距离（即更新minDist数组）

为了更好理解，数组下标从1开始，对应节点1，到达节点n对应下标n。
代码如下：

#include<iostream>
#include<vector>
#include<climits>
using namespace std;int main() {int n, m, s, e, v;cin >> n >> m;vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));while (m--) {cin >> s >> e >> v;grid[s][e]= v;}int start = 1;int end = n;vector<int>minDist(n+1, INT_MAX); //记录从原点到达每个节点的最短路径vector<bool>visited(n+1, false);minDist[start] = 0;//遍历所有节点for (int i = 1; i <= n; i++) { int minVal = INT_MAX;int cur = 1; //当前节点//遍历minDist，找出距离原点最近且未访问的节点for (int j = 1; j <= n; ++j) {if (!visited[j] && minDist[j] < minVal) {minVal = minDist[j];cur = j;}}//标记访问过的节点visited[cur] = true;//更新minDist，这里是判断原点到当前节点+当前节点到下一个节点的距离是否比原来的近for (int j = 1; j <= n; j++) {if (!visited[j] && grid[cur][j] != INT_MAX && minDist[cur] + grid[cur][j] < minDist[j]) {minDist[j] = minDist[cur] + grid[cur][j];}}}if (minDist[end] == INT_MAX) cout << -1 << endl; //不能到达终点else cout << minDist[end] << endl; //到达终点最短路径return 0;
}

---

总结

• 拓扑排序 ：
  1.unordered_map<int, vector> umap,存放每个节点指向多个节点
  2.一个vectorinDegrees记录每个节点的入度
  3.遍历inDegrees，用队列queue存放入度为0的节点
  4.遍历queue，将入度为0指向的节点入度-1，并将新的入度为0的节点加入到队列中。

• dijkstra算法：
  1.vector<vector>grid存放节点间的权值, vectorminDist存放每个节点到源点的最小距离，vectorvisited记录已经被访问的节点
  2.遍历每个节点，遍历minDist，找到离源点最小距离且未访问过的节点
  3.标记成已访问的节点
  4.更新minDist数组

明天继续加油！