Обход в глубину (реализация на Python)

Python   7 Февраль 2016  Автор статьи: Александр Гавриков 

Задан неориентированный граф, состоящий из N вершин и M ребер. Исходный граф задается списком ребер. Требуется произвести обход в глубину из всех еще не посещенных вершин графа в порядке увеличения их номера.
С целью осуществления обхода в глубину исходный граф G удобно представлять в памяти ЭВМ списком смежности adj, храня для каждой вершины графа v список adj[v] смежных с ней вершин. Список used, исполняющий роль булевского массива размерности N, служит для отметки о том, стала вершина v посещенной в процессе обхода в глубину или еще нет. При этом, если used[v] = True, то вершина v является посещенной, если used[v] = False, то нет.

1
2
adj = [[] for i in range(n)] #список смежности
used = [False for i in range(n)] #массив для хранения информации о пройденных и не пройденных вершинах

В качестве списка смежности для представления графа на языке Python 3.0 удобно использовать список списков.
В приведенной ниже реализации данные считываются и выводятся в консоль.

Входные данные

В первой строке входного файла задано два целых числа: N (1 \le N \le 10^5) – количество вершин в графе и M (1 \le M \le 10^6) – количество ребер графа соответственно. Каждая из следующих M строк содержит описание ребра графа – два целых числа из диапазона от 1 до N – номера концов ребра.

Выходные данные

В строке выходного файла показаны вершины графа в порядке обхода в глубину, начиная с первой вершины.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
'''
@author: agavrikov
'''


n, m = map(int, input().split()) #количество вершин и ребер в графе
adj = [[] for i in range(n)] #список смежности
used = [False for i in range(n)] #массив для хранения информации о пройденных и не пройденных вершинах
   
#считываем граф, заданный списком ребер
for i in range(m):
    v, w = map(int, input().split())
    v -= 1
    w -= 1
    adj[v].append(w)
    adj[w].append(v)
   
def dfs(v): #процедура обхода в глубину
    if used[v]: #если вершина является пройденной, то не производим из нее вызов процедуры
        return
    used[v] = True #помечаем вершину как пройденную
    print(v + 1, end=' ')
    for w in adj[v]:
        dfs(w) #запускаем обход из всех вершин, смежных с вершиной v
       
def run():
    for v in range(n):
        dfs(v)

run()

 

Пример

Рассмотрим работу алгоритма обхода в глубину на графе G, изображенном на рисунке слева. После работы алгоритма на исходном графе G будет построен лес обхода в глубину G_\pi, изображенный на рисунке справа.

демонстрация обхода в глубину

Входные данные
11 13
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 9
6 10
6 11
7 10
7 11
Выходные данные
1 2 4 8 9 5 3 6 10 7 11

 

Научиться программировать

  • на Delphi

  • на Java

  • на C++