在无向图中找到长度为 4 的循环

Question

我希望打印找到的长度为 4 的循环，这段代码可以帮助我正确计算循环数，但我也希望打印这些循环，例如在这个特定的输入图中，循环是：

0 -> 1 -> 2 -> 3 -> 0
0 -> 1 -> 4 -> 3 -> 0
1 -> 2 -> 3 -> 4 -> 1

但是我无法打印它们，谁能帮忙或提示我如何打印它们？

这里是使用 dfs 进行计数的代码：

# Python Program to count 
# cycles of length n 
# in a given graph. 

# Number of vertices 
V = 5

def DFS(graph, marked, n, vert, start, count): 

    # mark the vertex vert as visited 
    marked[vert] = True

    # if the path of length (n-1) is found 
    if n == 0: 

        # mark vert as un-visited to make 
        # it usable again. 
        marked[vert] = False

        # Check if vertex vert can end with 
        # vertex start 
        if graph[vert][start] == 1: 
            count = count + 1
            return count 
        else: 
            return count 

    # For searching every possible path of 
    # length (n-1) 
    for i in range(V): 
        if marked[i] == False and graph[vert][i] == 1: 

            # DFS for searching path by decreasing 
            # length by 1 
            count = DFS(graph, marked, n-1, i, start, count) 

    # marking vert as unvisited to make it 
    # usable again. 
    marked[vert] = False
    return count 

# Counts cycles of length 
# N in an undirected 
# and connected graph. 
def countCycles( graph, n): 

    # all vertex are marked un-visited initially. 
    marked = [False] * V 

    # Searching for cycle by using v-n+1 vertices 
    count = 0
    for i in range(V-(n-1)): 
        count = DFS(graph, marked, n-1, i, i, count) 

        # ith vertex is marked as visited and 
        # will not be visited again. 
        marked[i] = True

    return int(count/2) 

# main : 
graph = [[0, 1, 0, 1, 0], 
        [1 ,0 ,1 ,0, 1], 
        [0, 1, 0, 1, 0], 
        [1, 0, 1, 0, 1], 
        [0, 1, 0, 1, 0]] 

n = 4
print("Total cycles of length ",n," are ",countCycles(graph, n))```

Answer 1

将您正在访问的节点保存在列表中，并在 dfs 函数中传递它。如果找到循环，则将路径添加到所有路径列表中。

修改后的代码如下：

# cycles of length n 
# in a given graph. 

# Number of vertices 
V = 5
paths = []
def DFS(graph, marked, n, vert, start, count, path): 

    # mark the vertex vert as visited 
    marked[vert] = True

    # if the path of length (n-1) is found 
    if n == 0: 

        # mark vert as un-visited to make 
        # it usable again. 
        marked[vert] = False

        # Check if vertex vert can end with 
        # vertex start 
        if graph[vert][start] == 1: 
            count = count + 1
            paths.append(path)
            return count 
        else: 
            return count 

    # For searching every possible path of 
    # length (n-1) 
    for i in range(V): 
        if marked[i] == False and graph[vert][i] == 1: 

            # DFS for searching path by decreasing 
            # length by 1 
            next_path = path[:]
            next_path.append(i)
            count = DFS(graph, marked, n-1, i, start, count, next_path) 

    # marking vert as unvisited to make it 
    # usable again. 
    marked[vert] = False
    return count 

# Counts cycles of length 
# N in an undirected 
# and connected graph. 
def countCycles( graph, n): 

    # all vertex are marked un-visited initially. 
    marked = [False] * V 

    # Searching for cycle by using v-n+1 vertices 
    count = 0
    for i in range(V-(n-1)): 
        count = DFS(graph, marked, n-1, i, i, count,[i]) 

        # ith vertex is marked as visited and 
        # will not be visited again. 
        marked[i] = True

    return int(count/2) 

# main : 
graph = [[0, 1, 0, 1, 0], 
        [1 ,0 ,1 ,0, 1], 
        [0, 1, 0, 1, 0], 
        [1, 0, 1, 0, 1], 
        [0, 1, 0, 1, 0]] 

n = 4
print("Total cycles of length ",n," are ",countCycles(graph, n))

如果您打印 paths 列表，您将得到： [[0, 1, 2, 3], [0, 1, 4, 3], [0, 3, 2, 1], [0, 3, 4, 1], [1, 2, 3, 4], [1, 4, 3, 2]]

在无向图中找到长度为 4 的循环

find cycles of length 4 in undirected graph

python

algorithm

graph

depth-first-search

undirected-graph