iT邦幫忙

2021 iThome 鐵人賽

DAY 5
0
Software Development

圖論與演算法之間的相互應用系列 第 5

拓樸排序問題

6 拓樸排序問題

現在讓我們來考慮另一個可以使用 DFS 來解決的經典範例:拓樸排序問題。想像有 N 件工作要完成,但是這些工作會有一定程度的相依性:我們可以用有向邊 (i → j) 來表示依賴關係——進行工作 j 之前必須要先完成工作 i 。有沒有辦法快速找出一個完成工作順序呢?任何一個滿足答案的順序我們稱之為拓樸排序 (Topologocal Sort)。

考慮以下這張相依關係的圖:
https://ithelp.ithome.com.tw/upload/images/20210919/20112376QHWxVIgScX.png

我們可以隨意地從某個點開始進行 "反向" DFS:當我們決定要做這些工作的時候,先看看有哪些工作是得做但是還沒完成的(這對應著沿著箭頭的反方向、尚未探索過的點),直接遞迴呼叫查看他們。顯然在察看完畢以後,就可以安心完成手上的工作了。

原來拓樸排序在 Leetcode 上面居然有這麼多題目... https://leetcode.com/tag/topological-sort/
那我們隨意挑幾題來寫吧!

6.1 Leetcode 329. Longest Increasing Path in a Matrix

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

6.2 Leetcode 1591. Strange Printer II

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

6.X 冷笑話

如果下了繪製一張圖的指令卻沒有畫出任何東西的時候,就會感到嘆息,因為生零圖嘆...


上一篇
圖的走訪 - DFS 篇
下一篇
強連通元件
系列文
圖論與演算法之間的相互應用30

尚未有邦友留言

立即登入留言