Поиск (гарантированно уникального) пути между двумя узлами в дереве

Вы можете избежать обхода пути, возвращая None в случае ошибки и частичный путь в случае успеха. Таким образом, вы не сохраняете своего рода «цепочку навигации» от корня к текущему узлу, а только строите путь от цели обратно к корню, если найдете его. Непроверенный код:

def VisitNode(self, node, target):
    # Base case. If we found the target, return target in a list
    if node == target:
        return [node]

    # If we're at a leaf and it isn't the target, return None 
    if len(self.neighbors(node)) == 0:
        return None

    # recursively iterate over children
    for i in self.neighbors_iter(node):
        tail = self.VisitNode(i, target)
        if tail: # is not None
            return [node] + tail # prepend node to path back from target
    return None #none of the children contains target

Я не знаю, какую графическую библиотеку вы используете, но я предполагаю, что даже листы содержат метод neighbours_iter, который, очевидно, не должен давать дочерних элементов для листа. В этом случае вы можете опустить явную проверку листа, сделав ее немного короче:

def VisitNode(self, node, target):
    # Base case. If we found the target, return target in a list
    if node == target:
        return [node]
    # recursively iterate over children
    for i in self.neighbors_iter(node):
        tail = self.VisitNode(i, target)
        if tail: # is not None
            return [node] + tail # prepend node to path back from target
    return None # leaf node or none of the child contains target

Я также удалил некоторые операторы else, так как внутри истинной части if вы возвращаетесь из функции. Это распространенный шаблон рефакторинга (который не нравится некоторым приверженцам старой школы). Это удаляет некоторые ненужные отступы.

Вы можете вообще избежать аргумента пути, инициализировав путь в теле метода. Если метод возвращается до того, как найдет полный путь, он может вернуть пустой список.

Но ваш вопрос также касается использования стека вместо списка в реализации поиска в глубину, верно? Здесь вы получите представление: http://en.literateprograms.org/Depth-first_search_%28Python%29.

Короче говоря, вы

def depthFirstSearch(start, isGoal, result):
    ###ensure we're not stuck in a cycle

    result.append(start)

    ###check if we've found the goal
    ###expand each child node in order, returning if we find the goal

    # No path was found
    result.pop()
    return False

с

###<<expand each child node in order, returning if we find the goal>>=
for v in start.successors:
    if depthFirstSearch(v, isGoal, result):
        return True

а также

###<<check if we've found the goal>>=
if isGoal(start):
    return True

Используйте networkx напрямую:

all_simple_paths(G, источник, цель, отсечение=нет)