主页 / 问题 / 1607289
Accepted
Polundra
Asked:2025-02-20 16:08:11 +0000 UTC2025-02-20 16:08:11 +0000 UTC

正确遍历图。可以优化吗？

  • 772

该图以邻接字典的形式给出。需要遍历图的顶点（在本例中为迭代 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

2 个回答

  1. Best Answer

    尝试这个选项：

    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））遍历时间。

    • 2

  2. 我对这个问题有稍微不同的理解。我的代码使用堆栈实现迭代 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)
    • 0

相关问题