环的检测

无向图的无环验证：

不要与有向图的环混淆，无向图中的环是一条同一个节点作为首尾节点的路径。如果无环检测通过，那么

一个无环的无向图（默认连通的）叫一棵树。

这里我们有两种方法可以来检验无向图的环：UnionFind和深度优先搜索。

UnionFind验证无向图的无环性

UnionFind是一种寻找节点连通性的重要算法。这里我们用它来判定无向图是不是一棵树（无环且连通）。

uf = UF(n)
for p, q in edges:
    if not uf.union(p, q): # 已经连通，图中有环
        return False
return uf.count==1         # 只有一个连通分量

连通之后如果只有一个“岛屿“（aka连通分量），那这就是一棵树。否则的话，要么图中有环，要么有几个连通分量。

深度优先搜索验证无向图的无环性

从一个节点出发，访问所有从此出发的邻节点。如果不会重复访问节点，且最后访问了所有的节点，那么这就是一棵树。否则的话，要么图中有环，要么有其他未连接的节点。

def dfs(i):
    vis.add(i)
    for j in graph[i]:
        if j in vis:
            return True
        dfs(j)
    return False

vis = set()
if dfs(0):         # 已经连通，图中有环
    return False
return len(vis)==n # 只有一个连通分量

有向图的无环验证

前面我们看到了无环有向图求最值的方法，它特别依赖于无环这一个假设。下面我们来看一看如何来检测DAG中的"A" - acyclic，也就是无环。

有向图中环的定义是：一个指向方向相同的环。如果这样的环存在的话，我们会在拓扑排序是遇到错误。

有两种方法可以验证DAG中无环。其中基于广度优先搜索的拓扑排序方法更直观。

拓扑排序验证DAG的无环性

这一段编码与拓扑排序一致，仅需要最后验证一下。最终遍历过的节点个数若小于总节点个数，那么图中有环的存在。

# 计算初始入度
N = len(graph)
nodes = range(N)
indegrees = {n: 0 for n in nodes}
for i in nodes:
    for j in graph[i]:
        indegrees[j] += 1

# 开始排序，先遍历队列中一直存着入度为0的节
queue = [n for n in n if indegrees[n]==0]
cnt = 0
while queue:
    res.append(queue.pop())
    for j in graph[i]:
        indegrees[j] -= 1
        if indegrees[j]==0:
            queue.append(j)
    cnt += 1
return cnt < n # True：图中有环

深度优先搜索验证DAG的无环性

我们用三种颜色对每个节点染色，分别代替

$$\text{vis}= \begin{cases} 0:\text{未遍历} \\ 1:\text{未遍历所有子节点} \\ 2:\text{已遍历所有子节点} \\ \end{cases}$$

这样的染色方法可以帮我们验证环。

def dfs(i):
    if vis[i]==1: return True
    if vis[i]==2: return False
    vis[i] = 1  # start visiting children,
                # if any
    for j in graph[i]:
        if dfs(j):
            return True
    vis[i] = 2  # done visiting children
    return False

N = len(graph)
vis = [0 for _ in range(N)]
for i in range(N):
    if dfs(i):
        return True # 图中有环
return False

如果DAG中没有环，那么最终染色结束后所有节点的颜色vis=2。