DFS (Обход графа в глубину)

Question

Дан неориентированный граф без кратный ребер и петель. Программа выдает данную ошибку:

File "dfsbfs.py", line 12, in dfs
    new_vertices = [j for j in adj[u] if j not in visited]
IndexError: list index out of range.

Не понимаю почему так происходит.

n = int(input('Vertices: '))
m = int(input('Edges: '))
adj = []
for i in range(m):
    adj.append(list(map(int, input().split())))
def dfs(v):
    visited = {v}
    to_explore = [v]
    while to_explore:
        u = to_explore.pop()
        print (u)
        new_vertices = [j for j in adj[u] if j not in visited]
        to_explore.extend(new_vertices)
        visited.update(new_vertices)
dfs(0)

Answer 1

В to_explore у вас список вершин, которые нужно ещё посетить. А в adj - список рёбер между вершинами, при этом вы берёте из to_explore индексы вершин и обращаетесь с этим индексом к adj, поэтому если у вас вершин больше, чем рёбер, индекс этот выходит за пределы списка рёбер adj.

Как конкретно починить ваш алгоритм я не разбирался, но вам нужно как минимум:

Разобраться, где у вас хранятся вершины, а где рёбра
Назвать все переменные соответственно этому, чтобы не нужно было думать-вспоминать, где у вас что

После этого проще будет уже разбираться с алгоритмом, просто приводя в соответствие при манипуляциях с данными чтобы вершины были к вершинам, а рёбра к рёбрам.

БЛОГ НА HUSL

DFS (Обход графа в глубину)

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