G&R Blog Release Regulation

图的环检测

1.环的检测通常用于检测某些关系存在循环依赖的问题, 看到 [判断循环依赖] 的问题, 可以把这种结构抽象成有向图, 如果 A 情况的发生是依赖 B 情况, 那么我们可以转化成图里面 B 指向 A 的图; 比如下面的 207 的先修课程的问题, 检测多个课程之间是否存在循环依赖
2.我们只通过判定图是有环的, 确定图是存在循环依赖的. 如何判定图是有环的呢 ? 一种方法是进行拓扑排序, 拓扑排序的过程中会返回一个可能的图节点依赖性的有序的结果, 如果在排序的过程中我们发现了环的存在, 那么我们就判定循环依赖的存在; 反之如果拓扑排序过程完成都没有发现循环依赖, 那么环是不存在的

拓扑排序

1.拓扑排序算法是对图节点的依赖性形成某种排序, 如果一个有向图里面存在环, 是无法进行拓扑排序的; 如果一幅图是有向无环图, 那么一定可以拓扑排序; 有向无环图的可行的拓扑排序的结果有不止一种, 因为同一层的依赖关系之间本质没有先后之分
2.拓扑排序直观的来看, 是可以将有向无环图进行 [拉平], 在这个 [拉平] 的图里面, 所有箭头方向是一致的;
3.如何对图节点进行拓扑排序? 有两种思想可以完成
(i). bfs. 逐层寻找那些不被依赖的节点, 也就是入度为 0 的节点. 先找到图中没有指向它的节点, 也就是不被依赖的节点, 放入结果集合里面, 同时将该依赖关系去除, 然后重复如上过程直到所有节点完成
(ii). dfs. 深度优先遍历, 维持遍历过程的回溯有序性, 如果找到邻居节点是已经访问过的, 那么就是存在环的；如果是标准的有向无环图, 那么只需要在遍历到的回溯之后的位置, 我们称之为后序位置 (类比二叉树的后续遍历), 加入当前节点到遍历的结果; 最终再将后序遍历的结果进行一次翻转, 从 [被依赖关系] 翻转到得到 [依赖关系] 的排序

拓扑排序-bfs实现

1.先从 bfs 的方法入手理解拓扑排序
(a).每个节点有入度和出度, 如果入度为 0 表示没有指向它的
(b).一开始从入度为 0 的开始找, 我们将这些入度 为 0 的保存在队列里面; 然后将这些节点指向的节点入度 -1, 表示已经删除掉了依赖性, 每次删除完看看有没有新增入度为 0 的继续入队
(c).直到最后所有的都出队列

// 假设有 n 个节点, 按照 [0, 1, .., n-1] 编号
// 依赖关系输入: [[0,1], [3,2]] 表示 0 节点完成依赖 1 节点, 3 节点完成依赖 2 节点
// 依赖关系抽象图: 1->0  2->3
// 邻接见图时, 对一个节点的相邻入度节点建立邻接链表
vector<vector<int>> edges(n); // 邻接链表建图
vector<int> indegree(n)       // 存储每个节点的入度
queue<int> q;
vector<int> res;
// 邻接链表建图
for (auto x: t) {
  edges[x[1]].push_back(x[0]);
  ++indegree[x[0]];
}
// 先将入度为 0 加入队列
for (int i = 0; i < n; ++i) {
  if (indegree[i] == 0) {
    q.push(i);
  }
}
// bfs 拓扑排序
while (!q.empty()) {
  int cur = q.front();
  q.pop();
  res.push_back(cur); // 存放拓扑排序的结果
  for (auto x: edges[cur]) {
    --indegree[x];
    if (indegree[x] == 0) {
      q.push(x);
    }
  }
}

拓扑排序-dfs 实现

1.dfs 拓扑排序, 本质上是执行有向 (可能带环) 图的 dfs (包含回溯) 的遍历
(i). 对于一个节点 c, 如果它的相邻结点 (相邻节点这里重新定义为包括从 c 出发可达的所有节点) 所有路径都已经搜索完成, 那么搜索回溯到 c 的时候, c 本身变成一个已经搜索完成的节点
(ii). 搜索的过程中, 总共有 3 中可能的状态

a. 未搜索: 没搜过
b. 搜索中: 搜索过这个节点, 但是还没有回溯到该节点; 从维护栈的观点看, 该节点还没有入栈
c. 已完成: 搜索过这个节点且回溯过这个节点; 从维护栈的观点看, 该节点已经入栈

     u
    / \ 
  a     b
 / \   /  \
c   d e    f

2.遍历到的节点有三种状态, 用 vector visited 数组去标记
visited[c] = 0 表示从未搜索过
visited[c] = 1 表示搜索中, 但是未完成回溯
visited[c] = 2 表示搜索完成并且回溯也完成

3.假设我们遍历到 节点 c 为搜索中, 遍历它的相邻节点是 n
a.如果 visited[n] == 0 未搜索, dfs(n), 搜索完成回溯到 c
b.如果 visited[n] == 1 也就是为搜索中状态, 那么就找到图中有一个环
c.如果 visited[n] == 2 不进行任何操作

// 假设有 n 个节点, 按照 [0, 1, .., n-1] 编号
// 依赖关系输入: [[0,1], [3,2]] 表示 0 节点完成依赖 1 节点, 3 节点完成依赖 2 节点
// 依赖关系抽象图: 1->0  2->3
// 邻接表见图时, 对一个节点的相邻入度节点建立邻接链表
vector<vector<int>> edges(n); // 邻接链表建图
vector<int> visited;          // 标记状态 0/1/2 分别代表未搜索/搜索中未完成回溯/该节点已经完成回溯
vector<int> res;              // 数组模拟栈
bool hasCycle = false;        // 标记有环

// 邻接链表建图
for (auto x: t) {
  edges[x[1]].push_back(x[0]);
}
void dfs(int c) {
  visited[c] = 1;
  for (auto n : edges[c]) {
    if (visited[n] == 0) {
      dfs(n);
      if (hasCycle) {
        return;
      }
    } else if (visited[n] == 1) {
      hasCycle = true; 
      return;
    }
  }
  // 后序位置标记回溯完成
  visited[c] = 2;
  // 后序位置记录下来结果
  res.push_back(c);
}

for (int i = 0; i < n; ++i) {
  if (visited[i] == 0 && !hasCycle) {
    dfs(i);
  }
}

// 翻转记录下来的结果, 得到依赖的关系
vector<int> ans = reverse(res.begin(), res.end());

我们采用二叉树的例子理解上面 dfs 拓扑排序的核心思路: 对二叉树 (可以理解为上面的图) 进行后序遍历, 然后再将后序遍历的序列翻转一下; 为什么 [后序遍历再翻转] 能够实现拓扑排序, 是因为一个任务必须要等到它依赖的所有任务都完成后才能开始执行, 可以从二叉树的后序遍历去模拟一下, 将二叉树想象成一个简化之后的有向图, 比如有如下的图 (也是一个二叉树)

      1
     /  \
    2     3
   / \   / \
  5   4  8  9 
     / \
    6   7

它的后序遍历结果是 [5,6,7,4,2,8,9,3,1], 按照我们的定义, 边表达的是一种 [依赖] 的关系, 后序遍历和拓扑排序正好是实现相反的效果,
先看后序遍历: 对于节点1来说, 先 (递归地) 处理完它的两个孩子 2, 3 (及其子树) 之后, 才能访问节点1, 换句话说, [访问节点1的任务] 依赖 [访问子树2完成和3完成] 的任务, 这种依赖关系和二叉树父节点指向子节点的形成的图上的依赖关系是完全相同的. 也就是说在二叉树的后序遍历的依赖关系上, 先把左子树消除依赖, 然后把右子树消除依赖, 根节点是最后一步消除依赖的;
再看拓扑排序, 我们是优先对那些不需要被依赖的节点, 也就是入度为 0 的节点, 进行消除依赖, 然后将其右侧子树继续消除依赖, 再将其左侧子树消除依赖, 那么正好是后序遍历的逆过程.

210.课程表II

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：输入：numCourses = 2, prerequisites = [[1,0]] 输出：[0,1] 解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] 输出：[0,2,1,3] 解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：输入：numCourses = 1, prerequisites = [] 输出：[0]

分析:
1.课程之间的关系可以抽象为图结构的依赖关系, 返回可行的结果就是给出一种拓扑排序的结果; 我们尝试对课程图进行拓扑排序, 如果检测到环, 直接停止下来返回空的结果;
2.给出 bfs 和 dfs 的两种实现;

// bfs 实现
class Solution {
 private:
  vector<vector<int>> edges;
  vector<int> indegree;
  vector<int> ans;
  queue<int> q;
  int cnt = 0;
 public:
  vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    edges.resize(numCourses, vector<int>());
    indegree.resize(numCourses);
    for (auto x : prerequisites) {
      edges[x[1]].push_back(x[0]);
      ++indegree[x[0]];
    }
    for (int i = 0; i < numCourses; ++i) {
      if (indegree[i] == 0) {
        q.push(i);
      }
    }
    while (!q.empty()) {
      int c = q.front();
      q.pop();
      ++cnt;
      ans.push_back(c);
      for (auto n : edges[c]) {
        --indegree[n];
        if (indegree[n] == 0) {
          q.push(n);
        }
      }
    }
    if (cnt < numCourses) {
      return vector<int>();
    }
    return ans;
  }
};

然后写下 dfs 实现

// dfs 实现
class Solution {
 private:
  vector<vector<int>> edges;
  vector<int> visited;
  vector<int> ans;
  bool hasCycle;
 public:
  void dfs(int c) {
    if (hasCycle) {
      return;
    }
    visited[c] = 1;
    for (auto n : edges[c]) {
      if (visited[n] == 0) {
        dfs(n);
      } else if (visited[n] == 1) {
        hasCycle = true; 
        return;
      }
    }
    visited[c] = 2;
    ans.push_back(c);
  }
  vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    edges.resize(numCourses, vector<int>());
    visited.resize(numCourses);
    for (auto x : prerequisites) {
      edges[x[1]].push_back(x[0]);
    } 
    for (int i = 0; i < numCourses; ++i) {
      if (hasCycle) {
        break;
      }
      if (visited[i] == 0) {
        dfs(i);
      }
    }
    if (hasCycle) {
      return vector<int>();
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

207.课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：输入：numCourses = 2, prerequisites = [[1,0]] 输出：true 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：输入：numCourses = 2, prerequisites = [[1,0],[0,1]] 输出：false 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

分析:
1.课程之间的关系可以抽象为图结构的依赖关系, 返回可行的结果就是给出一种拓扑排序的结果; 我们尝试对课程图进行拓扑排序, 如果检测到环, 直接停止下来返回 false;
2.给出 bfs 和 dfs 的两种实现;

// bfs 实现
class Solution {
 private:
  vector<vector<int>> edges;
  vector<int> indegree;
  queue<int> q;
  int cnt = 0;
 public:
  bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    edges.resize(numCourses, vector<int>());
    indegree.resize(numCourses);
    for (auto x : prerequisites) {
      edges[x[1]].push_back(x[0]);
      ++indegree[x[0]];
    }
    for (int i = 0; i < numCourses; ++i) {
      if (indegree[i] == 0) {
        q.push(i);
      }
    }
    while (!q.empty()) {
      int c = q.front();
      q.pop();
      ++cnt;
      for (auto n : edges[c]) {
        --indegree[n];
        if (indegree[n] == 0) {
          q.push(n);
        }
      }
    }
    return cnt == numCourses;
  }
};

然后写下 dfs 实现

// dfs 实现
class Solution {
 private:
  vector<vector<int>> edges;
  vector<int> visited;
  bool hasCycle;
 public:
  void dfs(int c) {
    if (hasCycle) {
      return;
    }
    visited[c] = 1;
    for (auto n : edges[c]) {
      if (visited[n] == 0) {
        dfs(n);
      } else if (visited[n] == 1) {
        hasCycle = true; 
        return;
      }
    }
    visited[c] = 2;
  }
  bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    edges.resize(numCourses, vector<int>());
    visited.resize(numCourses);
    for (auto x : prerequisites) {
      edges[x[1]].push_back(x[0]);
    } 
    for (int i = 0; i < numCourses; ++i) {
      if (hasCycle) {
        break;
      }
      if (visited[i] == 0) {
        dfs(i);
      }
    }
    return !hasCycle;
  }
};

---

转载请注明来源, from goldandrabbit.github.io