拓撲排序
117. 軟件構建 (kamacoder.com)
拓撲排序簡單的說是將一個有向圖轉為線性的排序。
它將圖中的所有結點排序成一個線性序列，使得對于任何的邊uv，結點u在序列中都出現在結點v之前，這樣的序列滿足圖中所有的前驅-后繼關系。
拓撲排序通常用于任務調度、項目計劃、編譯依賴分析等場景，其中活動或任務之間存在依賴關系，需要確定一個合理的執行順序。
拓撲排序的算法步驟如下：
- 選擇一個沒有前驅的結點（即入度為0的結點），將其加入到拓撲排序的序列中，并從圖中刪除該節點及其所有出邊。
- 重復步驟1，直到所有的結點都被加入拓撲排序序列中或者途中不再存在無前驅的結點。
- 如果所有的結點都被加入序列中，則完成了拓撲排序；若圖中還存在結點，則說明圖中存在環，無法進行拓撲排序。
????????由于拓撲排序的結果可能不唯一，當圖中存在多個入度為0的結點，可以任意選擇一個結點進行刪除。
在實際應用中，拓撲排序通常和深度優先搜索或廣度優先搜素結合使用。例如，使用廣度優先搜索（拓撲排序的廣度優先搜索實現通常被稱為Kahn算法）進行拓撲排序的算法流程如下：
-
計算所有節點的入度：遍歷圖中的所有節點，計算每個節點的入度（即有多少邊指向該節點）。
-
初始化隊列：創建一個空隊列，將所有入度為0的節點加入隊列。這些節點是沒有前置依賴的節點，可以開始執行。
-
處理隊列：只要隊列不為空，就重復以下步驟：
- 從隊列中取出一個節點（稱為當前節點），并將其添加到拓撲排序的結果序列中。
- 減少當前節點的所有出邊指向的節點的入度（因為這些節點的依賴減少了）。
- 如果某個節點的入度在減少后變為0，則將其加入隊列，因為它現在沒有前置依賴了。
-
檢查是否有未處理的節點：當隊列為空時，如果所有的節點都已經添加到拓撲排序的結果序列中，則拓撲排序成功完成。如果還有節點未添加到結果序列中，則說明圖中存在環，因此無法進行拓撲排序。
偽代碼
拓撲排序(圖 G):初始化入度為0的隊列 Q初始化拓撲排序的結果序列 L// 計算所有節點的入度對于每個節點 v in G:v.入度 = G 中指向 v 的邊的數量如果 v.入度 == 0:Q.enqueue(v)// 處理隊列當 Q 不為空時:當前節點 u = Q.dequeue()L.add(u) // 將 u 添加到拓撲排序的結果序列中// 減少所有出邊的目標節點的入度對于每個節點 v，其中存在邊 u -> v:v.入度 = v.入度 - 1如果 v.入度 == 0:Q.enqueue(v)// 檢查是否所有節點都已處理如果 L 中的節點數量不等于 G 中的節點數量:返回 "圖 G 包含環，無法進行拓撲排序"否則:返回 L 作為拓撲排序的結果序列
C++代碼參考代碼隨想錄代碼隨想錄 (programmercarl.com)
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;int main() {int N, M; // N個文件存在M條依賴關系cin >> N >> M;vector<int> inDegree(N, 0); // 記錄每個點的入度unordered_map<int, vector<int>> umap;// 讀取M條依賴關系for (int i = 0; i < M; i++) {int s, t;cin >> s >> t;// t依賴于s，因此t的入度加1inDegree[t]++;umap[s].push_back(t);}queue<int> Queue;// 將所有入度為0的節點加入隊列for (int i = 0; i < N; i++) {if (inDegree[i] == 0)Queue.push(i);}vector<int> path; // 存儲拓撲排序結果while (!Queue.empty()) {int cur = Queue.front();Queue.pop();path.push_back(cur);// 遍歷當前節點的所有后繼節點for (int next : umap[cur]) {inDegree[next]--;if (inDegree[next] == 0)Queue.push(next);}}// 檢查是否所有的節點都被處理了if (path.size() == N) {for (int i = 0; i < N - 1; i++) {cout << path[i] << " ";}cout << path[N - 1];} else {// 如果不是所有的節點都被處理，說明存在環cout << -1 << endl;}return 0;
}
在時間復雜度上，初始化入度數組O(N)，讀取依賴關系并構建鄰接表O(M)(M條依賴關系)，將入度為0結點加入隊列，O(N)，BFS的時間復雜度為O(N+M)(每個結點最多訪問一次，每個結點被加入隊列后移除，每條邊會被訪問一次來減少相鄰結點的入度)時間復雜度為O(N+M）
空間復雜度 入度數組O(N)，鄰接表最差情況下O(N^2)，隊列和路徑數組都為O(N)，最差情況下空間復雜度為O(N^2)，但實際應用中，若圖比較稀疏，則空間復雜度為O(M+N)。
dijkstra
47. 參加科學大會（第六期模擬筆試） (kamacoder.com)
????????Dijkatra算法是一種著名的圖搜索算法，它用于在加權圖中找到從一源節點到其余所有結點的最短路徑。
算法步驟：
- 初始化：需要一個最短路徑估計的容器（優先隊列，通常是最小堆）存儲所有結點及其當前的最短路徑估計值，除源節點設置為0外，將所有結點的最短路徑估計值設置為無窮大。
- 訪問源結點：將源結點加入優先隊列。
- 循環處理隊列：當優先隊列非空時，重復以下步驟：
從優先隊列中取出具有最小估計值的節點，稱為當前節點。
對于當前節點的每個鄰接節點，執行以下操作：
- 計算通過當前節點到達鄰接節點的路徑長度。
- 如果這個路徑長度比已知的最短路徑估計值更短，則更新鄰接節點的最短路徑估計值，并更新它的前驅節點為當前節點。
- 將鄰接節點及其新的最短路徑估計值加入優先隊列。?
- 標記完成：當一個結點從優先隊列取出時，意味著它的最短路徑已經確定，可以將其標記為完成。
- 構建最短路徑樹：當算法結束時，可以從源結點開始，通過每個結點的前驅結點信息，構造出從源結點到所有其他結點的最短路徑樹。
需要注意的幾個點：
- Dijkstra算法不能處理帶有負權邊的圖，因為在有負權邊的圖中，可能存在一條路徑，其總權重隨著經過的邊數增加而減少，導致無法正確找到最短路徑。
- Dijkstra算法的時間復雜度為O(V^2)，V為圖中結點的數量，使用優先隊列可以優化到O(E+VlogV),E為邊的數量、
- Dijkstra可以用于有向圖和無向圖。
代碼隨想錄 (programmercarl.com)
#include <iostream>
#include <vector>
#include <climits>
using namespace std;int main() {int N, M; // N個文件存在M條依賴關系cin >> N >> M;vector<vector<int>> grid(N+1, vector<int>(N+1, INT_MAX)); // 創建一個N+1xN+1的二維數組，用于存儲節點之間的權重，初始化為INT_MAXint v1, v2, val;for (int i = 0; i < M; i++) { // 讀取M條依賴關系cin >> v1 >> v2 >> val; // 讀取兩個節點v1和v2以及它們之間的權重valgrid[v1][v2] = val; // 更新權重矩陣，表示v1到v2有邊，權重為val}int start = 1; // 定義起始節點為1int end = N; // 定義目標節點為Nvector<int> minDist(N+1, INT_MAX); // 創建一個長度為N+1的數組，用于存儲從起始節點到其他節點的最短路徑估計值，初始化為INT_MAXvector<int> visited(N+1, 0); // 創建一個長度為N+1的數組，用于標記節點是否被訪問過，0表示未訪問，1表示已訪問minDist[start] = 0; // 起始節點到自身的最短路徑為0for (int i = 0; i <= N; i++) { // 循環，找到未訪問的最短路徑節點int minVal = INT_MAX; // 初始化最小值為INT_MAXint cur = 1; // 初始化當前節點為1for (int v = 1; v <= N; v++) { // 遍歷所有節點，找到未訪問且最短路徑估計值最小的節點if (!visited[v] && minDist[v] < minVal) { // 如果節點v未訪問且最短路徑估計值小于minValminVal = minDist[v]; // 更新最小值cur = v; // 更新當前節點為v}}visited[cur] = 1; // 標記當前節點為已訪問for (int v = 1; v <= N; v++) { // 遍歷所有節點，更新從當前節點出發到其他節點的最短路徑估計值if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {// 如果節點v未訪問，且當前節點到節點v有邊，且通過當前節點到達v的路徑更短minDist[v] = minDist[cur] + grid[cur][v]; // 更新節點v的最短路徑估計值}}}if (minDist[end] == INT_MAX) // 如果目標節點的最短路徑估計值仍然是INT_MAX，表示沒有路徑到達目標節點cout << -1 << endl; // 輸出-1elsecout << minDist[end] << endl; // 否則輸出從起始節點到目標節點的最短路徑長度return 0;
}
算法的時間復雜度為O(N^2)，空間復雜度這里也是O(N^2)（沒有用上最小堆等優先隊列）
