Понятие обхода графа |
137 |
|
|
|
|
|
|
|
Рис. 5.13
Вот как работает алгоритм:
1.Он начинает с первой вершины, Amin, которая является единственной вер шиной на первом уровне.
2.Затем переходит на второй уровень и по очереди посещает все три вершины,
Wasim, Nick и Mike.
3.После этого переходит на третий и четвертый уровни, которые содержат по одной вершине каждый, — Imran и Faras.
Как только все вершины были посещены, они добавляются в структуру visited, после чего итерации прекращаются (рис. 5.14).
Теперь попробуем с помощью BFS найти в этом графе конкретного человека. Давайте уточним данные для поиска и посмотрим на результаты (рис. 5.15).
Перейдем к алгоритму поиска в глубину.
DFS — поиск в глубину
DFS — это альтернатива BFS, используемая для поиска данных в графе. DFS отличается от BFS тем, что после запуска из корневой вершины алгоритм про ходит как можно дальше по каждому из уникальных путей‚ перебирая их один за другим. Как только он успешно достигает конечной глубины каждого пути, он помечает флагом все вершины на этом пути как посещенные. После завер шения пути алгоритм возвращается назад. Если он может найти еще один уни кальный путь от корневого узла, процесс повторяется. Алгоритм продолжает двигаться по новым ветвям до тех пор, пока все ветви не будут посещены.
138 |
Глава 5. Графовые алгоритмы |
Рис. 5.14
Понятие обхода графа |
139 |
|
|
|
|
|
|
|
Рис. 5.15
Обратите внимание, что граф может содержать цикл. Как уже упоминалось, во избежание зацикливания мы используем логический флаг для пометки обра ботанных вершин.
Для реализации DFS мы будем использовать структуру данных стек (см. главу 2). Как мы помним, стек основан на принципе «последним пришел — первым ушел» (LIFO). Это противопоставляет его очереди, которая работает по принципу «первым пришел — первым ушел» (FIFO) и использовалась для BFS.
Код для DFS выглядит таким образом:
def dfs(graph, start, visited=None): if visited is None:
visited = set() visited.add(start) print(start)
for next in graph[start] - visited: dfs(graph, next, visited)
return visited
Вновь используем следующий код для тестирования функции dfs, определенной ранее:
graph={ 'Amin' : {'Wasim', 'Nick', 'Mike'}, 'Wasim' : {'Imran', 'Amin'}, 'Imran' : {'Wasim','Faras'}, 'Faras' : {'Imran'},
'Mike' :{'Amin'}, 'Nick' :{'Amin'}}
Если мы запустим этот алгоритм, результат будет выглядеть так (рис. 5.16).
Рис. 5.16
Рассмотрим полный маршрут обхода графа с использованием методологии DFS.