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

Question

Дан неориентированный граф. Необходимо реализовать алгоритм DFS. Код неправильно реализует поиск в глубину, не могли бы подсказать в чем проблема ?

n = int(input('Vertices: '))
m = int(input('Edges: '))
adj = [[0] * n for _ in range(n)]
for i in range(m):
    j, k = map(int, input().split())
    adj[j][k] =  adj[k][j] = 1

def dfs(v):
    used = [v]
    to_explore = [v]
    while to_explore:
        u = to_explore.pop()
        print (u)
        for w in range(n):
            if (adj[u][w] == 1) and (w not in used):
                used.append(w)
                to_explore.append(w)

print ('DFS')
dfs(0)

Пример: (Входные данные программы) Vertices: 8 Edges: 10

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

Вывод: 0 4 6 7 3 2 1 5

Ожидаемый ответ: 0 1 5 6 2 4 7 3

Answer 1

В коде реализован алгоритм BFS(поиск в ширину). Алгоритм DFS выглядел бы так:

def dfs(v):
    used = [v]
    for u in range(n):
        if u not in used:
            print(u)
            used.append(u)
            dfs(u)

БЛОГ НА HUSL

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

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