用DFS判断是否是有环图

Posted on

大致思路

DFS: 首先访问一个节点，然后访问他的邻居，再访问邻居的邻居......如果再某一次访问的路径中，访问到了之前已经访问过的节点，则表示有环。如果全部遍历完以后，未遍历到之前访问过的节点，则表示无环。

实现技巧

算法理解起来并不难，不过实现起来有一些小技巧。

  1. 设置visited变量，存储之前总体访问情况。visited变量存储的应该是之前访问过，且它和它的邻居不存在环的变量。不能用这个变量来判断是否存在环，否则实现起来会有混乱。

  2. 设置path变量，记录当前此次路径中的访问情况。我们应该用这个变量来判断是否存在环。注意，因为判断的是当前路径，所以每次对于新路径要进行重置，注意这里的重置并不是将path中所有的全部清空，而是清空前一子节点所访问的路径。有如下例子：

1
2
3
4
5
[0, 1], [0，2], [1, 2]
       0
     /   \
    ◣     ◢
    1 ---▶ 2

节点0有两个邻居——节点1和节点2。我们对节点0的两个子节点进行遍历，判断有没有环。对邻居节点1访问时，会将1，2加入path中，而访问完成后，我们要将1，2从path中移除，才能接着访问下一个邻居节点2。如果不移除，直接访问了节点2，就会发现节点2已经在path中，从而得到存在环这一结论。很明显，这个图是没有环的，我们得到了错误的结论。

  1. path中路径重置的技巧。因为DFS是递归的算法，所以在重置变量上具有一定的技巧性。我们将代码分成3部分：访问、递归调用、RESET。比方所我们当前的path为：1234,接下来要访问5节点。对5节点和5节点的邻居的代码部分而言，5节点是访问了的；对节点1,2,3,4的代码部分而言，5节点是未访问的。所以我们可以在5节点的代码中这样书写： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // path：[1,2,3,4]

    访问：将5节点放入path中

    // path: [1,2,3,4,5]

    递归调用：访问5节点的邻居们

    // path: [1,2,3,4,5]

    RESET：将5节点从path中取出

    // path: [1,2,3,4]

了解了这一点以后就没有什么难点了。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
 public:
  int* matrix;
  int numCourses;
  int* path;
  int* visited;

  bool dfsCyclic(int v) {
    if (this->path[v] == 1)
      return true;

    if (this->visited[v] == 1)
      return false;

    // Add vertex v to the path
    this->visited[v] = this->path[v] = 1;

    for (int i = 0; i < this->numCourses; i++) {
      if (i == v)
        continue;
      if (matrix[v * this->numCourses + i] == 1) {
        if (dfsCyclic(i))
          return true;
      }
    }
    // Reset current path.
    return this->path[v] = 0;
  }

  bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
    this->matrix = (int*)malloc(numCourses * numCourses * sizeof(int));
    this->visited = (int*)malloc(numCourses * sizeof(int));
    this->path = (int*)malloc(numCourses * sizeof(int));
    this->numCourses = numCourses;
    bool can = true;

    memset(this->matrix, 0, numCourses * numCourses * sizeof(int));
    memset(this->visited, 0, numCourses * sizeof(int));
    for (auto el : prerequisites) {
      this->matrix[el.second * numCourses + el.first] = 1;
    }

    for (int i = 0; i < numCourses; i++) {
      memset(this->path, 0, numCourses * sizeof(int));
      if (this->visited[i] == 0 && dfsCyclic(i)) {
        return false;
      }
    }

    return true;
  }
};
0%