Корректный обход графа. Можно ли оптимизировать?

Рейтинг: 0Ответов: 2Опубликовано: 20.02.2025

Граф задан в виде словаря смежности. Нужно обойти вершины графа (в данном случае итеративный DFS)

def iteractive_dfs(graph, start, path=None):
    if path is None:
        path = []
    q = [start]
    while q:
        v = q.pop()
        print(v)
        if v not in path:   # new point
            path = path + [v]
# need add to stack visited point first
#            l1 = list(graph[v])
#            for point in l1:
#                    if point in path:
#                        q.append(point)
#                        l1.remove(point)
#                        break

#            q += l1
            q +=graph[v]   

    return path

graph = {0: [6, 8, 3, 5], 1: [2, 7], 2: [1, 5], 3: [0, 4], 4: [3], 5: [0, 2], 6: [0], 7: [1], 8: [0]}
iteractive_dfs(graph, 0) # начинаем обход с вершины 0

В нашем случае получаем траекторию обхода: 0 - 5 - 2 - 5 - 1 - 7 - 1 - 2 - 0 - 3 - 4. Но, по логике вещей, корректной должна быть: 0 - 5 - 2 - 1 - 7 - 1 - 2 - 5 - 0 - 3 - 4 Т.е. при добавлении из словаря вверху стека должны оказаться непосещенные вершины Этого можно добиться, если использовать закомментированный фрагмент кода и убрав q +=graph[v] Но есть опасение, что данная конструкция не оптимальна по времени выполнения для больших графов. Можно ли оптимизировать? Спасибо.

python алгоритм графы
Источник: Stack Overflow на русском

Ответы

▲ 2Принят

Попробуйте такой вариант:

def iteractive_dfs(graph, start, cnts, path=None):
    if path is None:
        path = []
    q = [start]
    while q:
        v = q[-1]
        if cnts[v]==0:
            q.pop()
        else:
            print(v, end = ' ')
            path = path + [v]
            t = graph[v][cnts[v]-1]
            while cnts[v] and (t in path):
                cnts[v] -= 1
                t = graph[v][cnts[v]-1]
            if cnts[v]:
                q.append(t)
    return path

graph = {0: [6, 8, 3, 5], 1: [2, 7], 2: [1, 5], 3: [0, 4], 
         4: [3], 5: [0, 2], 6: [0], 7: [1], 8: [0]}
counts = [len(graph[i]) for i in graph.keys()]
iteractive_dfs(graph, 0, counts) # начинаем обход с вершины 0

>>>0 5 2 1 7 1 2 5 0 3 4 3 0 8 0 6 0

Каждая вершина кладётся в стек только один раз, и остаётся там, пока все исходящие рёбра не обработаны.

Счётчики для каждого узла только уменьшаются, так что их использование не увеличивает асимптотически линейное (O(V+E)) время обхода.

▲ 0

У меня несколько иное понимание вопроса. Мой код реализует итеративный DFS с использованием стека. В итеративном DFS:

Вершины посещаются в порядке, обратном их добавлению в стек.

Возврат к предыдущим вершинам не происходит явно, как в рекурсивном DFS.

Порядок посещения зависит от того, как вершины добавляются в стек.

def iterative_dfs(graph, start):
    visited = set()  # Множество для отслеживания посещенных вершин
    stack = [start]  # Стек для хранения вершин, которые нужно посетить

    while stack:
        vertex = stack.pop()  # Извлекаем вершину из стека
        if vertex not in visited:
            print(vertex)  # Посещаем вершину (в данном случае просто выводим её)
            visited.add(vertex)  # Добавляем вершину в множество посещенных

            # Добавляем все смежные вершины в стек
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    stack.append(neighbor)

# Граф задан в виде словаря смежности
graph = {
    0: [6, 8, 3, 5],
    1: [2, 7],
    2: [1, 5],
    3: [0, 4],
    4: [3],
    5: [0, 2],
    6: [0],
    7: [1],
    8: [0]
}

# Запускаем DFS с начальной вершины 0
iterative_dfs(graph, 0)