拓撲排序C++

解題思路

本題可約化為： 課程安排圖是否是有向無環圖(DAG)。即課程間規定了前置條件，但不能構成任何環路，否則課程前置條件將不成立。
思路是通過 拓撲排序 判斷此課程安排圖是否是有向無環圖(DAG) 。

拓撲排序原理： 對 DAG 的頂點進行排序，使得對每一條有向邊 $(u,v)$，均有 $u$（在排序記錄中）比 $v$ 先出現。亦可理解為對某點 $v$ 而言，只有當 $v$ 的所有源點均出現了，$v$ 才能出現。

通過課程前置條件列表 prerequisites 可以得到課程安排圖的鄰接表 adjacency，以降低算法時間復雜度，以下兩種方法都會用到鄰接表。

方法一：入度表（BFS）

本方法中幾個數據結構的含義：

• vector<vector<int>> prerequisites 題目給出參數，其中每個元素 p 是一個依賴關系 p[0] 依賴于 p[1] ，在有向圖中，應該是 p[1]->p[0] 。

• vector<int> degress 記錄所有節點的入度

• vector<vector<int>> adjacents 鄰接表，長度為總課程數，下標 $i$ 的元素存放所有依賴節點 $i$ 的節點

• queue<int> zeros 存放所有目前入度為 0 的頂點

算法流程：

1. 統計課程安排圖中每個節點的入度，生成 入度表 indegrees。
2. 借助一個隊列 queue，將所有入度為 0 （沒有任何依賴）的節點入隊。
3. 當 queue 非空時，依次將隊首節點出隊，在課程安排圖中刪除此節點 pre：
   • 并不是真正從鄰接表中刪除此節點 pre，而是將此節點鄰接表對應所有鄰接節點 cur，即所有以來該節點的節點的入度 ?1，即 indegrees[cur] -= 1。
   • 當入度 ?1 后鄰接節點 cur 的入度為 0，說明 cur 所有的前驅節點（依賴節點）已經被 “刪除”，此時將 cur 入隊。
4. 在每次 pre 出隊時，執行 numCourses--；
   • 若整個課程安排圖是有向無環圖（即可以安排），則所有節點一定都入隊并出隊過，即完成拓撲排序。換個角度說，若課程安排圖中存在環，一定有節點的入度始終不為 0。
   • 因此，拓撲排序出隊次數等于課程個數，返回 numCourses == 0 判斷課程是否可以成功安排。

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<int> degrees(numCourses, 0);		// 記錄所有頂點的入度,未初始化的為0vector<vector<int>> adjacents(numCourses);	// 鄰接表queue<int> zero;	// 零入度的頂點int num = numCourses;for (int i=0; i<prerequisites.size(); ++i) {degrees[prerequisites[i][0]]++;		// 入頂點adjacents[prerequisites[i][1]].push_back(prerequisites[i][0]);		// 出頂點}for (int i=0; i<numCourses; ++i) {if (degrees[i] == 0) {zero.push(i);		// 入度為0的先入隊列--num;}}while (!zero.empty()) {int temp = zero.front();zero.pop();for (int j=0; j<adjacents[temp].size(); ++j) {if (--degrees[adjacents[temp][j]] == 0) {zero.push(adjacents[temp][j]);--num;}}}if (num == 0) return true;else return false;}
};

方法二：DFS

原理是通過 DFS 判斷圖中是否有環。

算法流程：

1. 借助一個標志列表 flag，用于判斷每個節點 i （課程）的狀態：
   1. 未被 DFS 訪問：i == 0；
   2. 已被其他節點啟動的 DFS 訪問：i == -1；
   3. 已被當前節點啟動的 DFS 訪問：i == 1。
2. 對 numCourses 個節點依次執行 DFS，判斷每個節點起步 DFS 是否存在環，若存在環直接返回 False。DFS 流程：
   • 終止條件：
     1. 當 flag[i] == -1，說明當前訪問節點已被其他節點啟動的 DFS 訪問，無需再重復搜索，直接返回 True。
     2. 當 flag[i] == 1，說明在本輪 DFS 搜索中節點 i 被第 2 次訪問，即 課程安排圖有環 ，直接返回 False。
   • 將當前訪問節點 i 對應 flag[i] 置 1，即標記其被本輪 DFS 訪問過；
   • 遞歸訪問當前節點 i 的所有鄰接節點 j，當發現環直接返回 False；
   • 當前節點所有鄰接節點已被遍歷，并沒有發現環，則將當前節點 flag 置為 ?1 并返回 True。
3. 若整個圖 DFS 結束并未發現環，返回 True。

class Solution {
public:bool dfs(vector<vector<int>>& adjacents, vector<int>& flags, int curr) {if (flags[curr] == 1) return false;else if (flags[curr] == -1) return true;flags[curr] = 1;for (int i=0; i<adjacents[curr].size(); ++i) {if (!dfs(adjacents, flags, adjacents[curr][i])) return false;}flags[curr] = -1;return true;}bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> adjacents(numCourses);vector<int> flags(numCourses, 0);for (vector<int> p: prerequisites) {adjacents[p[1]].push_back(p[0]);}for (int i=0; i<numCourses; ++i) {if (!dfs(adjacents, flags, i))  return false;}return true;}
};

與上題思路一致

BFS

class Solution {
private:// 存儲有向圖vector<vector<int>> edges;// 存儲每個節點的入度vector<int> indeg;// 存儲答案vector<int> result;public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {edges.resize(numCourses);indeg.resize(numCourses);for (const auto& info: prerequisites) {edges[info[1]].push_back(info[0]);++indeg[info[0]];}queue<int> q;// 將所有入度為 0 的節點放入隊列中for (int i = 0; i < numCourses; ++i) {if (indeg[i] == 0) {q.push(i);}}while (!q.empty()) {// 從隊首取出一個節點int u = q.front();q.pop();// 放入答案中result.push_back(u);for (int v: edges[u]) {--indeg[v];// 如果相鄰節點 v 的入度為 0，就可以選 v 對應的課程了if (indeg[v] == 0) {q.push(v);}}}if (result.size() != numCourses) {return {};}return result;}
};

DFS

class Solution {
private:vector<vector<int>> edges;vector<int> visited;bool valid = true;stack<int> S;void dfs(int u) {visited[u] = 1;for (int v : edges[u]) {if ( visited[v] == 1) {valid = false;return;}else if (visited[v] == 0) {dfs(v);if (!valid) return;}}visited[u] = 2;S.push(u);}public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {edges.resize(numCourses);visited.resize(numCourses);for (const auto& v : prerequisites) {edges[v[1]].push_back(v[0]);}for (int i=0; i<numCourses && valid; i++) {if (!visited[i]) dfs(i);}if (!valid) return {};else {vector<int> res;while (!S.empty()) {res.push_back(S.top());S.pop();}return res;}

解題思路參考：https://leetcode-cn.com/problems/course-schedule/solution/course-schedule-tuo-bu-pai-xu-bfsdfsliang-chong-fa/