图算法-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

文章来源：公众号（算法工程师之路）

完