Python networkx прекращает рекурсию по краям - PullRequest
Новая
       9

Python networkx прекращает рекурсию по краям

0 голосов
/ 05 марта 2020

Я использую библиотеку networkx здесь. FYI G[i] перечисляет связанные узлы в словаре 

def find_next_vertex(G):
    def dfs(i):
        if G.nodes[i]['visited'] == 'no':
            G.nodes[i]['visited'] = 'yes'
            return i
        else:
            for adj in G[i]:
                dfs(adj)
    return dfs(1)

Моя цель здесь - найти следующий не посещенный узел, но он должен быть одним из смежных узлов предыдущего, который, я считаю, называется DFS (поиск в глубину)? Отсюда и название функции. Проблема с кодом в том, что G[i] становится None в какой-то момент. Я попытался заменить предпоследнюю строку на return dfs(adj), и теперь я получаю максимальную ошибку рекурсии.

Я обнаружил, что G[i] показывает своего родителя, то есть ребро, и оно зацикливается навсегда. Как мне на самом деле прекратить l oop. Вот что я попробовал: 

def find_next_vertex(G):
    def dfs(i, parent):
        if G.nodes[i]['visited'] == 'no':
            G.nodes[i]['visited'] = 'yes'
            return i
        else:
            for adj in G[i]:
                j = dfs(adj, parent)
                if j == parent:
                    continue
                return j
    return dfs(1, None)

Но я все равно получаю максимальную ошибку рекурсии.

...