圖論

題目

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

Dijkstra 不能處理負數情況