Теория
Поиск в глубину используется в теории графов для перебора(посещения) всех вершин графа или для проверки существования пути из одной вершины в другую.Идея метода: поиск начинается с некоторой вершины V. Рассматривается вершина U, смежная с вершиной V. Теперь вершина U является стартовой для поиска. Если на очередном шаге нет смежных вершин или все вершины доступные с текущей вершины уже расмотрены, то возвращаемся к предыдущей вершине. В случае если это стартовая вершина (V), то процесс окончен.
Реализация
После нескольких минут раздумий у меня получилось написать рабочий код на Python 3.4.3.
def dfs(node): # node - начальная вершина ex.add(node) # исключаем ее сразу for i in range(len(g)): if g[node][i] == 1 and i not in ex: # если есть ребро и вершина не исключена print(i) # печать номера вершины dfs(i) # запускаем обход снова, но с этой вершиныg = [[0,1,1], # матрица смежности [1,0,1], [1,1,0]] ex = set() # множество для исключения вершинdfs(1) # вызов функции от первой вершины
