图中循环的算法？

Question

如果有一个表示为邻接列表的图，那么如何在python中检测任何odd length-ed循环？

假设有一个图形作为输入：

A = {
    1: [2, 4],
    2: [1, 5],
    3: [4, 5],
    4: [1, 3, 5],
    5: [2, 3, 4],
    6: []
}

V = {
    1: <node>,
    2: <node>,
    3: <node>,
    4: <node>,
    5: <node>,
    6: <node>
}

A是一个字典，其中键是一个数字，值是一个数字列表，因此键与所有值之间都有一条边。V是一个将数字映射到节点实例的字典。

如何检测是否存在奇数长度的ed循环？

根据上面的输入，实际上有一个使用节点3, 4, 5。

基本上，我怎样才能得到3 4 5的输出？

谢谢

Answer 1

在图中查找循环的常用方法是使用depth-first search算法。在你的例子中，我会用数字1和2标记每个顶点，这样所有相邻的顶点都有不同的数字。如果你发现有两个顶点有相同的标记，那就意味着你找到了一个奇数长度的循环。 下面是我的简短实现（我没有使用V措辞，假设A描述的图形没有原样）：

import sys

A = {
    1: [2, 4],
    2: [1, 5],
    3: [4, 5],
    4: [1, 3, 5],
    5: [2, 3, 4],
    6: []
}

num_vertices = len(A)
sys.setrecursionlimit(num_vertices + 2)

mark = [None] * (num_vertices + 1)
cur_path = []

def DFS(vertex, cur_mark = 1):
    mark[vertex] = cur_mark
    global cur_path
    cur_path.append(vertex)
    for neighbour in A[vertex]:
        if not mark[neighbour]:
            DFS(neighbour, 3 - cur_mark)
        elif mark[neighbour] == cur_mark:
            print 'Found a loop of odd length: ', cur_path[cur_path.index(neighbour):]
            sys.exit(0)

    cur_path = cur_path[:-1]

# Visit all connected components
for vertex in xrange(1, num_vertices + 1):
    if not mark[vertex]:
        DFS(vertex)

print 'Cycle of odd length not found'