检查有向图是否包含循环

g = {
    1: [2, 3],
    2: [3]
}

cur_path = set()
def isCyclic(g, vertex):
    global cur_path
    cur_path.add(vertex)
    for neighboor in g.get(vertex, []):
        if neighboor in cur_path:
            return True
        else:
            if neighboor in g and isCyclic(g, neighboor):
                return True
    cur_path.remove(vertex)
    return False

#1 楼

1.审核


没有文档字符串。该功能做什么？我应该通过哪些论点？它返回的是什么？
这种函数可以使一个或两个doctest成为理想的候选函数。
该函数实际上无法确定图形是否包含循环。它确定图形是否包含从给定顶点开始的循环。要检测周期，有必要为图中的每个顶点调用函数。
函数使用状态的全局变量。这使得不可能在多线程程序中使用该功能。这也使调试变得困难，因为无论何时发生任何问题，都必须将cur_path重置为空集，然后才能重新运行该功能。最好将所有状态都封装在函数内。
else: if ...:可以缩写为elif ...:。
如果在()中找不到vertex，最好使用空元组g作为默认值，而不要使用空列表[]。这是因为空元组是一个单例：每次评估()时，您都会得到一个相同的对象。但是，每次评估[]时，都必须分配一个新的空列表。
测试neighbour in g是不必要的，因为您已经处理过vertex不在g中的情况。

2。修改后的代码

应用以上所有注释：

def cyclic(g):
    """Return True if the directed graph g has a cycle.
    g must be represented as a dictionary mapping vertices to
    iterables of neighbouring vertices. For example:

    >>> cyclic({1: (2,), 2: (3,), 3: (1,)})
    True
    >>> cyclic({1: (2,), 2: (3,), 3: (4,)})
    False

    """
    path = set()

    def visit(vertex):
        path.add(vertex)
        for neighbour in g.get(vertex, ()):
            if neighbour in path or visit(neighbour):
                return True
        path.remove(vertex)
        return False

    return any(visit(v) for v in g)

3。分析

该函数遵循图中的所有简单路径，在遇到循环时停止。不幸的是，一个图可能具有许多没有路径的简单路径，因此运行时的输入大小是指数的。

例如，此函数构造一个具有许多简单路径的图：

def test_graph(n):
    """Return an acyclic graph containing 2**n simple paths."""
    g = dict()
    for i in range(n):
        g[3 * i] = (3 * i + 1, 3 * i + 2)
        g[3 * i + 1] = g[3 * i + 2] = (3 * (i + 1),)
    return g

它构建的图形如下所示：



通过实验我们可以检查运行时间是否是指数的：

>>> for i in range(10, 20):
...     print(i, timeit(lambda:cyclic(test_graph(i)), number=1))
... 
10 0.017517157015390694
11 0.03172751097008586
12 0.06926556502003223
13 0.1300737849669531
14 0.25352559401653707
15 0.5073735360056162
16 0.9933696809457615
17 2.004867063020356
18 3.9877060829894617
19 7.927054518950172

您可以看到i的每个增量都会使运行时间翻倍。

4。一种高效的算法

要使该算法高效，我们必须确保不多次访问任何一个顶点，这可以通过保留到目前为止已访问的一组单独的顶点来实现。例如：

def cyclic(g):
    """Return True if the directed graph g has a cycle.
    g must be represented as a dictionary mapping vertices to
    iterables of neighbouring vertices. For example:

    >>> cyclic({1: (2,), 2: (3,), 3: (1,)})
    True
    >>> cyclic({1: (2,), 2: (3,), 3: (4,)})
    False

    """
    path = set()
    visited = set()

    def visit(vertex):
        if vertex in visited:
            return False
        visited.add(vertex)
        path.add(vertex)
        for neighbour in g.get(vertex, ()):
            if neighbour in path or visit(neighbour):
                return True
        path.remove(vertex)
        return False

    return any(visit(v) for v in g)

此函数最多访问每个顶点一次，并考虑每个边缘最多一次，因此其运行时间为\ $ O（V + E）\ $ 。

通过实验，我们可以检查运行时图的大小是否大致线性：

>>> for i in range(10, 20):
...     print(i, timeit(lambda:cyclic(test_graph(i)), number=1))
...
10 0.00017403007950633764
11 0.00014279899187386036
12 0.00015402096323668957
13 0.00016507902182638645
14 0.00017680192831903696
15 0.00019660103134810925
16 0.00020132900681346655
17 0.0002140760188922286
18 0.00022624700795859098
19 0.00023716699797660112

5。避免递归限制

该实现使用递归搜索图。这意味着它使用的堆栈帧数与它在图形中访问的最长路径中的节点数一样多。但是Python的堆栈框架数量有限（请参阅sys.getrecursionlimit）。要绕过此限制，我们可以使用迭代器模式的堆栈，如下所示：

def cyclic(graph):
    """Return True if the directed graph has a cycle.
    The graph must be represented as a dictionary mapping vertices to
    iterables of neighbouring vertices. For example:

    >>> cyclic({1: (2,), 2: (3,), 3: (1,)})
    True
    >>> cyclic({1: (2,), 2: (3,), 3: (4,)})
    False

    """
    visited = set()
    path = [object()]
    path_set = set(path)
    stack = [iter(graph)]
    while stack:
        for v in stack[-1]:
            if v in path_set:
                return True
            elif v not in visited:
                visited.add(v)
                path.append(v)
                path_set.add(v)
                stack.append(iter(graph.get(v, ())))
                break
        else:
            path_set.remove(path.pop())
            stack.pop()
    return False