代碼隨想錄算法訓練

—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數組

明天繼續加油！