圖演算法-LeetCode 133、207（拓撲排序，鄰接表建立）

2019 年 10 月 11 日
筆記

點擊上方「演算法工程師之路」，選擇「星標」公眾號

重磅乾貨，第一時間送達

作者：TeddyZhang，公眾號：演算法工程師之路

貪心演算法問題：LeetCode #133 #207

編程題

【LeetCode #133】克隆圖

給定無向連通圖中一個節點的引用，返回該圖的深拷貝（克隆）。圖中的每個節點都包含它的值 val（Int）和其鄰居的列表（list[Node]）。

解釋：節點 1 的值是 1，它有兩個鄰居：節點 2 和 4 。節點 2 的值是 2，它有兩個鄰居：節點 1 和 3 。節點 3 的值是 3，它有兩個鄰居：節點 2 和 4 。節點 4 的值是 4，它有兩個鄰居：節點 1 和 3 。

提示：

節點數介於 1 到 100 之間。
無向圖是一個簡單圖，這意味著圖中沒有重複的邊，也沒有自環。
由於圖是無向的，如果節點 p 是節點 q 的鄰居，那麼節點 q 也必須是節點 p 的鄰居。
必須將給定節點的拷貝作為對克隆圖的引用返回。

解題思路：

克隆圖，並且是無向連通圖，因此可以使用map來保存兩個節點之間的連接關係，如果在map中沒有該節點tmp，則新建節點tmp_copy將該節點存入map中，然後遍歷該節點的所有鄰居，並遞拷貝其所有鄰居節點至tmp_copy的鄰居數組中。

C++程式碼：

/*  // Definition for a Node.  class Node {  public:      int val;      vector<Node*> neighbors;        Node() {}        Node(int _val, vector<Node*> _neighbors) {          val = _val;          neighbors = _neighbors;      }  };  */  class Solution {  public:      map<Node*,Node*> mp;      Node* cloneGraph(Node* node) {          if(!node)   return nullptr;          if(mp.count(node))  return mp[node];  // 如果存在，就不用新建了          Node* tmp = new Node(node -> val);          mp[node] = tmp;          for(int i = ; i < node -> neighbors.size(); ++ i){              if(node -> neighbors[i])    tmp -> neighbors.push_back(cloneGraph(node -> neighbors[i]));          }          return tmp;      }  };

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/clone-graph

【LeetCode #207】課程表

現在你總共有 n 門課需要選，記為 0 到 n-1。

在選修某些課程之前需要一些先修課程。例如，想要學習課程 0 ，你需要先完成課程 1 ，我們用一個匹配來表示他們: [0,1]

給定課程總量以及它們的先決條件，判斷是否可能完成所有課程的學習？

示例 1: 輸入: 2, [[1,0]] 輸出: true 解釋: 總共有 2 門課程。學習課程 1 之前，你需要完成課程 0。所以這是可能的。示例 2: 輸入: 2, [[1,0],[0,1]] 輸出: false 解釋: 總共有 2 門課程。學習課程 1 之前，你需要先完成課程 0；並且學習課程 0 之前，你還> 應先完成課程 1。這是不可能的。

說明:

輸入的先決條件是由邊緣列表表示的圖形，而不是鄰接矩陣。詳情請參見圖的表示法。你可以假定輸入的先決條件中沒有重複的邊。

解題思路：

由於本題目中的每個課程之間都有相應的聯繫，因此我們可以根據課程關係來構建一個有向圖，如果在這個有向圖中存在一個循環，那麼則不能學完所有的課程，因為每個課程都需要每個先決條件的課程。一個很簡單的思路是使用拓撲排序演算法，可以判斷一個循環是否存在於一個有向圖中。

拓撲排序演算法：計算圖中所有節點的入度，如果某些節點的入度為零，則壓入到隊列todo中，接著循環彈出隊列中的節點（即入讀為零的節點），同時將下一個節點中入度為零的節點壓入隊列中，如果最後圖都可以分離開，也就在此過程中，每個節點在分離時都可能入度為零。說明這個有向圖中沒有循環，否則則有循環。

C++程式碼（拓撲排序）：

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {          std::unordered_map<int, int> indegree;          for(auto& v : prerequisites) {              indegree[v[]]++;          }          queue<int> que;          for(int i=; i<numCourses; ++i) {             if(indegree[i] == ) {                 que.push(i);             }          }          int cnt = ;          while(!que.empty()) {              int k = que.front();              que.pop();              cnt++;              for(auto& v : prerequisites) {                  if(k == v[]) {                      if(--indegree[v[]] == ) {                          que.push(v[]);                      }                  }              }          }          if(cnt != numCourses)              return false;          return true;

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/course-schedule

文章來源：公眾號（演算法工程師之路）

完