그래프 구현에서 모든 주기 찾기 (Find all cycles in a graph implementation)

문제 설명

그래프 구현에서 모든 주기 찾기 (Find all cycles in a graph implementation)

여기에서 그래프의 모든 주기를 찾는 간단한 알고리즘을 찾았습니다. 사이클도 인쇄해야 합니다. 이 알고리즘으로 가능합니까? 아래의 코드를 찾아주세요.

정확하게 사이클 수를 구하고 있습니다!

node1, node2는 정수입니다. 방문은 사전입니다

def dfs(self,node1, node2):
    if self.visited[node2]:
        if(node1 == node2):
            self.count += 1
            print node2
        return

    self.visited[node2] = True

    for x in self.adj_lst[node2‑1]:
        self.dfs(node1, x)

    self.visited[node2] = False

def allCycles(self):
    self.count = 0
    for x in self.VList:
        self.dfs(x.num, x.num)
        self.visited[x.num] = True

    print "Number of cycles: "+str(self.count)

참조 솔루션

방법 1:

Yes of course you can construct the path, now you can do it recursively but I'm not a great fan of managing temporary state in the class.

Here's a simple implementations using a stack:

def dfs(graph, start, end):
    fringe = [(start, [])]
    while fringe:
        state, path = fringe.pop()
        if path and state == end:
            yield path
            continue
        for next_state in graph[state]:
            if next_state in path:
                continue
            fringe.append((next_state, path+[next_state]))

>>> graph = { 1: [2, 3, 5], 2: [1], 3: [1], 4: [2], 5: [2] }
>>> cycles = [[node]+path  for node in graph for path in dfs(graph, node, node)]
>>> len(cycles)
7
>>> cycles
[[1, 5, 2, 1], [1, 3, 1], [1, 2, 1], [2, 1, 5, 2], [2, 1, 2], [3, 1, 3], [5, 2, 1, 5]]

Note: 4 cannot get back to itself.

방법 2:

Yes, it's possible. You can just store the parent of each vertex and then iterate over the array of parents (until you reach the start vertex) to print the cycle when you find one.

(by Kalyan Chavali、AChampion、kraskevich)

참조 문서

1. Find all cycles in a graph implementation (CC BY‑SA 2.5/3.0/4.0)