Как переписать этот код итеративно

Question

Есть код для получения пути, у меня с рекурсией траблы, помогите переписать итеративно, я понимаю, что должен быть стек, с которого будет что-то доставаться, но как переписать без понятия

def all_paths(a, b, n, graph):
    visited = [False] * n
    path = []
    get_all_paths(a, b, visited, path, graph)


def get_all_paths(a, b, visited, path, graph):
    visited[a] = True
    path.append(a)

    if a == b:
        print(path)
    else:
        for vertex in graph[a]:
            if not visited[vertex[0]]:
                get_all_paths(vertex[0], b, visited, path, graph)

    path.pop()
    visited[a] = False

Answer 1

В стеке нужно хранить те переменные, что у вас уникальны для каждого вызова. В этом случае это текущая вершина a и текущее ребро (у вас задано конечной вершиной ребра vertex). Для удобства я храню пару (вершина, индекс в массиве ребер):

def all_paths_iter(a, b, n, graph):
    visited = [False] * n
    path = [[a, 0]]
    while path:
        a, idx = path[-1]
        if idx == 0:
            visited[a] = True

        if a == b:
            print([v[0] for v in path])
        else:
            if idx < len(graph[a]):
                vertex = graph[a][idx]
                path[-1][1] += 1
                if not visited[vertex[0]]:
                    path.append([vertex[0], 0])
                continue
        # сюда попадаем если дальше из а идти не нужно
        # т.е. все просмотрели или а это конец пути
        path.pop()
        visited[a] = False

Answer 2

n = 5
g = [[0,1,0,1,1],[0,0,1,1,1],[0,0,0,1,1],[0,0,0,0,1],[0,0,0,0,0]]
visited = [False] * n

def get_all_paths(a, b, path):
    if a == b:
        print(path)
    else:
        for vertex in range(n):
            if g[a][vertex] and (not visited[vertex]):
                visited[vertex] = True
                get_all_paths(vertex, b, path + [vertex])
                visited[vertex] = False

visited[0] = True
get_all_paths(0,4,[0])

[0, 1, 2, 3, 4]
[0, 1, 2, 4]
[0, 1, 3, 4]
[0, 1, 4]
[0, 3, 4]
[0, 4]

БЛОГ НА HUSL

Как переписать этот код итеративно

Ответы (2 шт):