9.3 DFS应用：检测环的存在_dfs判断环c++

  图的DFS算法应用太广了，强连接组件、拓扑排序都可以使用DFS算法来解决。但是这些我准备在后续博文中介绍，因为强连接组件和拓扑排序除了DFS之外，还有别的算法。而检测图中环的存在，一般来说就只有DFS算法了。实际应用中，检测是否存在环是很重要的，比如工作流的有向无环图模型，如果存在环，那么工作流将无法结束。再比如一些本来是树的数据结构，如果存在环，那么将会进入死循环，造成程序错误。
  但是查环的难点在于什么呢？难点在于有向图和无向图的不同。对于有向图，两条边指向同一节点，并不表示图中存在着环，因为这很有可能是有向无环图。而无向图为了快速查找，往往是用两条from和to相反的边数据来表示一条边，所以写代码时需要稍微注意一下。

有向图环的检测

  有向图环的检测的基本思路是DFS，然后把路径记录下来，这个路径上的点被称为前驱节点，再看看邻居中是不是有前驱节点存在。如果有，这条指向前驱节点的边，就被成为回边back edge。回边的存在是图中存在环的充分必要条件。如下图的红色部分就是一个回边：

  以上图为例子。采用递归的方式去做会简单一点。递归的算法是这样的，弄两个数组，一个是已访问数组，避免DFS重复访问，一个是路径数组，用一个布尔数组记录DFS遍历的路径。每处理一个节点时，将其加入到路径数组，当所有子树处理完了的时候，再清空路径数组。递归代码如下：

    def dfs_cycle(self):
        # 着色
        visited = [False for _ in self.__vertices]
        path = [False for _ in self.__vertices]
        # key为child, value 为parent
        for i, vertex in enumerate(self.__vertices):
            if not visited[i]:
                if self.is_cycle(i, visited, path):
                    return True

        return False

    def is_cycle(self, vertex_index, visited, path):
        visited[vertex_index] = True
        path[vertex_index] = True
        for edge in self.__edges[vertex_index]:
            if not visited[edge]:
                if self.is_cycle(edge, visited, path):
                    return True
            elif path[edge]:
                return True
        path[vertex_index] = False
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

  测试数据：

vertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
edges = [
    [1, 5],  # 0
    [2, 3],  # 1
    [3, ],  # 2
    [4, 7],  # 3
    [7],  # 4
    [],  # 5
    [5],  # 6
    [6, ]  # 7
]
1
2
3
4
5
6
7
8
9
10
11

  结果为False。

无向图环的检测

  无向图环的检测，算法完全不一样，因为无向图，实际上是双向的图，如果按照有向图的算法来检测的话，那所有的无向图都有环了。无向图环的检测使用一个parent字典或parent数组来做。我们使用递归来进行DFS,然后设置邻居的parent为节点本身。如果出现一个已访问的邻居，并且自身的parent不是该邻居，那么我们就找到了一个环。这有点难以理解，我解释一下，已访问邻居就表示该邻居出现在从根到自身的路径上，如果自身的parent不是这个邻居，那表示不是自己的上一个节点。我举个例子，下面是一个成环的无向图:

  当DFS进行下去的时候，遍历顺序是ABCD。当到D的时候D有两个邻居，B和C。此时D的parent是C。而这时候D的邻居B是一个已访问的邻居，但是不是自己的上一个，表示D回到这条路径了。明显了原理之后用递归来写代码就简单了。

def dfs_cycle_undirected(self):
    # 着色
    visited = [False for _ in self.__vertices]
    parent = [None for _ in self.__vertices]
    # key为child, value 为parent
    for i, vertex in enumerate(self.__vertices):
        if not visited[i]:
            if self.is_cycle_undirected(i, visited, parent):
                return True
    return False

def is_cycle_undirected(self, vertex_index, visited, parent):
    visited[vertex_index] = True

    for neighbor in self.__edges[vertex_index]:
        if not visited[neighbor]:
            parent[neighbor] = vertex_index
            if self.is_cycle_undirected(neighbor, visited, parent):
                return True
        elif parent[vertex_index] != neighbor:
            return True
    return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

  测试代码

def test_cycle_undirected(self):
    # 定义一个图，测试BFS搜索
    vertices = ['A', 'B', 'C', 'D']
    edges = [
        [1, ],  # 0
        [0, 2, 3],  # 1
        [3, 1],  # 2
        [2, 1],  # 3
    ]
    graph = UnweightedGraph()
    graph.vertices = vertices
    graph.edges = edges
    print(graph.dfs_cycle_undirected())

    vertices = ['A', 'B', 'C', 'D']
    edges = [
        [1, ],  # 0
        [0, 2, 3],  # 1
        [ 1],  # 2
        [ 1],  # 3
    ]
    graph = UnweightedGraph()
    graph.vertices = vertices
    graph.edges = edges

    d = graph.dfs_cycle_undirected()
    print(d)
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

  测试使用的图：

  测试结果完全正确：

True
False
1
2