Статья Автор: Лебедев Дмитрий

BFS и DFS: Алгоритмы обходов графа в ширину и глубину. Начало

Многие программистские задачи можно решить, если рассмотреть ситуа- цию как граф и воспользоваться подходящим алгоритмом. 
Алгоритмы обходов графа  BFS (поиск в ширину) и DFS (поиск в глубину) являются фундаментальными  алгоритмами и находят широкое применение во многих областях. 
Поиск в глубину (depth-rst search – DFS) – прямолинейный способ обхода графа. Алгоритм начинает работу в начальной вершине и перебирает все вершины, достижимые из нее по ребрам графа. Поиск в глубину всегда следует по одному пути, пока на нем еще имеются вершины. После этого он возвращается назад и начинает исследовать другие части графа. Алгоритм запоминает посещенные вершины, так что каждая обрабатывается только один раз.

При поиске в ширину (breadth-rst search – BFS) вершины графа посещаются в порядке возрастания расстояния от начальной вершины. Следовательно, используя поиск в ширину, мы сможем вычислить расстояния от начальной вершины до всех остальных. Однако реализовать поиск в ширину труднее, чем поиск в глубину. В процессе поиска в ширину мы обходим вершины уровень за уровнем.
Сначала посещаются вершины, отстоящие от начальной на расстояние 1, затем – на расстояние 2 и т. д. Процесс продолжается, пока не останется непосещенных вершин.
Алгоритмы BFS и DFS решают похожие задачи. Выбор алгоритма зависит от условия задачи, способа представления графа и требованиям к затратам.

С помощью алгоритмов обхода мы можем проверить многие свойства графа. Обычно применимы как поиск в глубину, так и поиск в ширину, но на практике поиск в глубину предпочтительнее, потому что он проще реализуется. 
Проверка связности. Граф называется связным, если между любыми двумя вершинами существует путь. Следовательно, для проверки связности мы можем начать с произвольной вершины и выяснить, все ли вершины достижимы из нее.
Можно также найти все компоненты графа: для этого нужно перебрать все вершины и начинать новый поиск, если текущая вершина не принадлежит ни одной из уже найденных компонент связности.
Обнаружение циклов. Граф содержит цикл, если в процессе обхода мы встречаем такую вершину, что одна из соседних с ней (кроме той, что предшествует ей на текущем пути) уже посещалась. Есть и другой способ узнать, содержит ли граф цикл: просто посчитать количество вершин и ребер в каждой компоненте. Если компонента содержит n вершин и ни одного цикла, то в ней должно быть ровно n-1 ребер (т. е. она должна быть деревом). Если число ребер равно n или больше, то компонента обязательно содержит цикл.
Проверка на двудольность. Граф называется двудольным, если его вершины можно раскрасить двумя цветами, так что никакие две соседние вершины не будут окрашены одним цветом. Удивительно, как просто можно проверить граф на двудольность с помощью алгоритмов обхода.
Идея в том, чтобы выбрать два цвета X и Y, окрасить начальную вершину цветом X, всех ее соседей – цветом Y, всех их соседей – цветом X и т. д.
Если в какой-то момент мы обнаруживаем, что две соседние вершины окрашены одним цветом, значит, граф не является двудольным.
В противном случае граф двудольный, и мы нашли доказывающую это раскраску.
Кратчайшие пути. Нахождение кратчайшего пути между двумя вершинами графа – важная задача, имеющая много практических применений. Очевидный пример – нахождение кратчайшего маршрута между двумя городами, если известна карта дорог и длины всех участков.
В невзвешенном графе длина пути равна количеству ребер в нем, и для поиска кратчайшего пути достаточно применить поиск в ширину.
Но если нас будут интересовать взвешенные графы, то будут нужны более сложные алгоритмы.

 

При  применении  алгоритмов на графах  большое значение имеет способ их представления.
Есть несколько способов представить граф в алгоритмах. Выбор структуры данных зависит от размера графа
и способа его обработки в алгоритме. Ниже рассмотрены три популярных представления.
Списки смежности. В этом случае каждой вершине x сопоставляется список смежности, включающий вершины, соединенные с x ребром.
Списки смежности – самый популярный способ представления графов, они позволяют эффективно реализовать большинство алгоритмов.
Списки смежности удобно хранить в "списке списков" , который может быть представлен следующим образом:
словарь или список graph (graph[x]=  список/словарь, элементы которого есть описание ребер в смежные вершины :
  • вершина -  для невзвешенного графа 
  • (вершина, вес) - для взвешенного граф
Списки смежности позволяют эффективно находить вершины, в которые можно перейти из данной по одному ребру.
Следующий цикл обходит все вершины, в которые можно попасть из вершины s:
for u in graph[s] :
    # обработать вершину u
Матрица смежности показывает, какие ребра есть в графе. С ее помощью можно эффективно проверить, существует ли ребро между двумя вершинами. Матрицу можно хранить в виде двумерного списка  adj[N][N], где элемент adj[a][b] равен 1, если существует ребро, ведущее из верши ны a в вершину b, а в противном случае равен 0. сли граф взвешенный, то представление в виде матрицы смежности можно обобщить:
если две вершины соединены ребром, то в матрице хранится вес этого ребра. 
Недостаток матрицы смежности заключается в том, что она содержит n2 элементов, большая часть которых обычно равна 0. Поэтому такое представление не годится для больших графов. 
Список ребер содержит все ребра графа в некотором порядке. Это представление удобно, если алгоритм обрабатывает все ребра и не требуется находить ребра, начинающиеся в заданной вершине.Список ребер можно хранить в списке и перебирать следующим образом:
for ed in edges :
   # обработка ребра ed 
   # ed - кортеж (a,b) или (a,b,w) a,b - вершины соединяемые ребром, w - вес ребра (для взвешенного)
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать