現在讓我們來考慮另一個可以使用 DFS 來解決的經典範例：拓樸排序問題。想像有 N 件工作要完成，但是這些工作會有一定程度的相依性：我們可以用有向邊 (i → j) 來表示依賴關係——進行工作 j 之前必須要先完成工作 i 。有沒有辦法快速找出一個完成工作順序呢？任何一個滿足答案的順序我們稱之為拓樸排序 (Topologocal Sort)。
考慮以下這張相依關係的圖：
我們可以隨意地從某個點開始進行 "反向" DFS：當我們決定要做這些工作的時候，先看看有哪些工作是得做但是還沒完成的（這對應著沿著箭頭的反方向、尚未探索過的點），直接遞迴呼叫查看他們。顯然在察看完畢以後，就可以安心完成手上的工作了。
原來拓樸排序在 Leetcode 上面居然有這麼多題目... https://leetcode.com/tag/topological-sort/
那我們隨意挑幾題來寫吧！
https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
題目敘述：要找出一個 m*n 矩陣當中最長的一條遞增路線。只能沿著相鄰的四個方向行走，不能踏出矩陣外。
解法：我們可以定義工作 A[i][j] 為「從 (i, j) 這格出發，能走出的最長路線長度」。要完成這個計算，就必須嘗試沿著四個方向走到底能走多遠，也就是說，這個 A[i][j] 的計算工作仰賴於計算其周圍數值比較大的格子。換句話說，如果我們事先找出一個拓樸排序，就可以依照這個排序計算 A[i][j] 的正確數值。
想說還是放點參考程式碼(C++)好了：
class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> maxlen(m, vector<int>(n, 0));
std::function<void(int, int)> dfs = [&](int x, int y) {
maxlen[x][y] = 1;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
for (int f = 0; f < 4; f++) {
if (x + dx[f] >= 0 && x + dx[f] < m && y + dy[f] >= 0 &&
y + dy[f] < n) {
if (matrix[x + dx[f]][y + dy[f]] > matrix[x][y]) {
if (maxlen[x + dx[f]][y + dy[f]] == 0) {
dfs(x + dx[f], y + dy[f]);
}
maxlen[x][y] = max(maxlen[x][y], maxlen[x + dx[f]][y + dy[f]] + 1);
}
}
}
};
int answer = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (maxlen[i][j] == 0) dfs(i, j);
answer = max(answer, maxlen[i][j]);
}
return answer;
}
};
https://leetcode.com/problems/strange-printer-ii/
題目敘述：有一台奇怪的印表機，每一次可以印一個新的顏色矩形，新的矩形印製時，如果那些位置原先就有矩形了，那部分就會被覆蓋過去。現在給你印完的結果，請問這個結果是否真的是從這台奇怪印表機印出來的。
這題乍看之下跟圖論沒什麼關係，但有趣的事情是我們可以把印製矩形的相依性列出來，跑一個拓樸排序。最後再模擬一次繪製過程，檢查看看是否與輸入相符就可以啦！
class Solution {
public:
bool isPrintable(vector<vector<int>>& targetGrid) {
// 首先找出每個矩形邊界
int m = targetGrid.size();
int n = targetGrid[0].size();
map<int, vector<int>> colorsBoundary;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (colorsBoundary.find(targetGrid[i][j]) == colorsBoundary.end()) {
colorsBoundary[targetGrid[i][j]] = {i, i, j, j};
} else {
vector<int>& bounds = colorsBoundary[targetGrid[i][j]];
bounds[0] = min(bounds[0], i);
bounds[1] = max(bounds[1], i);
bounds[2] = min(bounds[2], j);
bounds[3] = max(bounds[3], j);
}
// 接下來找出相依關係
map<int, set<int>> dependencyGraph;
for (auto it : colorsBoundary) {
int color = it.first;
vector<int> bounds = it.second;
for (int i = bounds[0]; i <= bounds[1]; i++)
for (int j = bounds[2]; j <= bounds[3]; j++)
if (targetGrid[i][j] != color)
dependencyGraph[targetGrid[i][j]].insert(color);
}
// 然後跑一次拓樸排序(或是發現圖上有環，失敗)
map<int, int> visited;
vector<int> toposort;
bool has_cycle = false;
std::function<void(int)> dfs = [&](int x) {
visited[x] = 1;
for (int y : dependencyGraph[x]) {
if (visited.find(y) != visited.end()) {
if (visited[y] == 1) has_cycle = true;
} else {
dfs(y);
}
}
visited[x] = 2;
toposort.push_back(x);
};
for (auto it : colorsBoundary) {
int color = it.first;
if (visited.find(color) == visited.end()) dfs(color);
}
if (has_cycle) return false;
// 最後模擬一次畫矩形的順序
vector<vector<int>> grid(m, vector<int>(n, 0));
for (int color : toposort) {
vector<int> bounds = colorsBoundary[color];
for (int i = bounds[0]; i <= bounds[1]; i++)
for (int j = bounds[2]; j <= bounds[3]; j++) grid[i][j] = color;
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] != targetGrid[i][j]) return false;
return true;
}
};
如果下了繪製一張圖的指令卻沒有畫出任何東西的時候，就會感到嘆息，因為生零圖嘆...
iThome鐵人賽
看影片追技術