Обход графа¶
Дерево представляет отношение «один ко многим», тогда как граф обладает большей свободой и может выражать произвольные отношения «многие ко многим». Поэтому дерево можно рассматривать как частный случай графа. Очевидно, что операции обхода дерева также являются частным случаем операций обхода графа.
И графы, и деревья требуют применения алгоритмов обхода. Способы обхода графа также делятся на два типа: обход в ширину и обход в глубину.
Обход в ширину¶
Обход в ширину - это способ обхода от ближнего к дальнему, при котором начиная с некоторого узла сначала посещают ближайшие вершины, а затем слой за слоем расширяются наружу. Как показано на рисунке ниже, начиная с вершины в левом верхнем углу, мы сначала обходим все смежные вершины этой вершины, затем все смежные вершины следующей вершины и так далее, пока не будут посещены все вершины.
Реализация алгоритма¶
BFS обычно реализуется с помощью очереди, код приведен ниже. Очередь обладает свойством «первым пришел - первым вышел», что хорошо соответствует идее BFS «от ближнего к дальнему».
- Поместить стартовую вершину обхода
startVetв очередь и запустить цикл. - На каждой итерации цикла извлекать вершину из головы очереди и записывать ее посещение, после чего добавлять все смежные вершины этой вершины в хвост очереди.
- Повторять шаг
2.до тех пор, пока не будут посещены все вершины.
Чтобы предотвратить повторный обход вершин, нам нужно хеш-множество visited , в котором записывается, какие вершины уже посещены.
Tip
Хеш-множество можно рассматривать как хеш-таблицу, которая хранит только key и не хранит value . Оно позволяет выполнять добавление, удаление и проверку наличия key за \(O(1)\) времени. Благодаря уникальности key хеш-множество обычно используется, например, для устранения повторов.
Код сравнительно абстрактен, поэтому для лучшего понимания рекомендуется сопоставлять его с тем, что показано на рисунке ниже.
Является ли последовательность обхода в ширину единственной?
Нет. Обход в ширину требует только соблюдения порядка «от ближнего к дальнему», а порядок обхода нескольких вершин на одинаковом расстоянии может произвольно меняться. Например, на рисунке выше можно поменять местами порядок посещения вершин \(1\) и \(3\) , а вершины \(2\), \(4\), \(6\) также можно переставлять произвольно.
Анализ сложности¶
Временная сложность: все вершины по одному разу помещаются в очередь и извлекаются из нее, что требует \(O(|V|)\) времени. При обходе смежных вершин, поскольку граф неориентированный, все ребра будут посещены по \(2\) раза, что требует \(O(2|E|)\) времени. В сумме получается \(O(|V| + |E|)\) .
Пространственная сложность: список res , хеш-множество visited и очередь que в худшем случае могут содержать до \(|V|\) вершин, поэтому требуется \(O(|V|)\) памяти.
Обход в глубину¶
Обход в глубину - это способ обхода, при котором сначала идут до самого конца, а когда дальше идти нельзя, возвращаются назад. Как показано на рисунке ниже, начиная с вершины в левом верхнем углу, мы выбираем некоторую смежную вершину текущей вершины, идем до упора, затем возвращаемся назад, снова идем до упора и так далее, пока не будут посещены все вершины.
Реализация алгоритма¶
Такой алгоритмический шаблон «дойти до конца и вернуться» обычно реализуется через рекурсию. Подобно обходу в ширину, в обходе в глубину мы также используем хеш-множество visited для записи уже посещенных вершин и тем самым избегаем повторного посещения.
Алгоритмический процесс обхода в глубину показан на рисунке ниже.
- Прямая пунктирная линия обозначает нисходящую рекурсию , то есть запуск нового рекурсивного метода для посещения новой вершины.
- Изогнутая пунктирная линия обозначает восходящую рекурсию , то есть данный рекурсивный метод завершился и управление вернулось туда, откуда он был вызван.
Чтобы лучше понять алгоритм, рекомендуется сопоставить код с тем, что показано на рисунке ниже, и мысленно проследить весь процесс DFS, включая моменты запуска и возврата каждого рекурсивного вызова.
Является ли последовательность обхода в глубину единственной?
Как и в случае обхода в ширину, последовательность DFS тоже не является единственной. Для заданной вершины допустимо сначала углубиться в любое направление, то есть порядок смежных вершин может быть произвольным, и все такие варианты будут корректными обходами в глубину.
Если взять в качестве примера обход дерева, то варианты «корень \(\rightarrow\) лево \(\rightarrow\) право», «лево \(\rightarrow\) корень \(\rightarrow\) право» и «лево \(\rightarrow\) право \(\rightarrow\) корень» соответствуют прямому, симметричному и обратному обходам соответственно. Они показывают три разных приоритета обхода, но все они относятся к обходу в глубину.
Анализ сложности¶
Временная сложность: все вершины будут посещены по \(1\) разу, что требует \(O(|V|)\) времени. Все ребра будут посещены по \(2\) раза, что требует \(O(2|E|)\) времени. Суммарно получается \(O(|V| + |E|)\) .
Пространственная сложность: число вершин в списке res и хеш-множестве visited в худшем случае достигает \(|V|\) , максимальная глубина рекурсии тоже равна \(|V|\) , поэтому требуется \(O(|V|)\) памяти.