Дан граф выбери какое из деревьев данного графа получено применением алгоритма поиск в ширину

Добавил пользователь Alex
Обновлено: 19.09.2024

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

Пусть задан граф G=(V, E) и корень s, с которого начинается обход. После посещения узла s, следующими за ним будут посещены смежные с s узлы (множество смежных с s узлов обозначим как q; очевидно, что q⊆V, то есть q – некоторое подмножество V). Далее, эта процедура повториться для вершин смежных с вершинами из множества q, за исключением вершины s, т. к. она уже была посещена. Так, продолжая обходить уровень за уровнем, алгоритм обойдет все доступные из s вершины множества V. Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения наличествующего условия.

Рассматривая пример, будем считать, что в процессе работы алгоритма каждая из вершин графа может быть окрашена в один из трех цветов: черный, белый или серый. Изначально все вершины белые. В процессе обхода каждая из вершин, по мере обнаружения, окрашивается сначала в серый, а затем в черный цвет. Определенный момент обхода описывает следующие условие: если вершина черная, то все ее потомки окрашены в серый или черный цвет.

Имеем смешанный граф (рис. 9.1) с |V| = 4 и |E| = 5. Выполним обход его вершин, используя алгоритм поиска в ширину. В качестве стартовой вершины возьмем узел 3. Сначала он помечается серым как обнаруженный, а затем черным, поскольку обнаружены смежные с ним узлы (1 и 4), которые, в свою очередь, в указанном порядке помечаются серым. Следующим в черный окрашивается узел 1, и находятся его соседи – узел 2, который становится серым. И, наконец, узлы 4 и 2, в данном порядке, просматриваются, обход в ширину завершается.

Рисунок 9.1 – Смешанный граф

Алгоритм поиска в ширину работает как на ориентированных, так и на неориентированных графах. Дать понять это был призван смешанный граф, используемый в примере. Стоит отметить, в неориентированном связном графе данный метод обойдет все имеющиеся узлы, а в смешанном или орграфе это необязательно произойдет. К тому же, до сих пор рассматривался обход всех вершин, но вполне вероятно, достаточным окажется, например просмотр определенного их количества, либо нахождение конкретной вершины. В таком случае придется немного приспособить алгоритм, а не изменять его полностью или вовсе отказаться от использования такового.

Теперь перейдем к более формальному описанию алгоритма поиска в ширину. Основными объектами – тремя структурами данных, задействованными в программе, будут:

· матрица смежности графа GM;

· очередь queue;

· массив посещенных вершин visited.

1. массив visited обнуляется, т. е. ни одна вершина графа еще не была посещена;

2. в качестве стартовой, выбирается некоторая вершина s и помещается в очередь (в массив queue);

3. вершина s исследуется (помечается как посещенная), и все смежные с ней вершины помещаются в конец очереди, а сама она удаляется;

4. если на данном этапе очередь оказывается пустой, то алгоритм прекращает свою работу, иначе посещается вершина, стоящая в начале очереди, и помечается как посещенная, все ее потомки заносятся в конец очереди;

5. выполнять пункт 4, пока это возможно.

Поиск в ширину, начиная со стартовой вершины, постепенно уходит от нее все дальше и дальше, проходя уровень за уровнем. Получается, что по окончанию работы алгоритма будут найдены все кратчайшие пути из начальной вершины до каждого доступного из нее узла.

Для реализации алгоритма на ЯП потребуется: умение программно задавать граф, а также иметь представление о такой структуре данных, как очередь.

Алгоритм поиска в ширину
Подскажите, пожалуйста, алгоритм поиска в ширину в неориентированном графе

Алгоритмы поиска кратчайших путей в ширину и двунаправленный в ширину
Реализовать алгоритм поиска кратчайшего пути. Двунаправленный поиск в ширину. Вот есть 2.

Алгоритмы поиска в глубину и ширину
Помогите с кодом: на входе файл есть файл вида: n m v1 u1 v2 u2 . vm um Здесь n -.

та матрица, что задана у тебя в коде - полная фигня, т.к. матрица смежности - симметрична.

По той ссылке, где я брал код, сказано, что алгоритм работает как с неориентированными графами, так и с ориентированными. Моя матрица смежности - для орграфа.

Решение

Проблема в том, что в Вашей ссылке не описано, как происходит чтение графа. Вы решили, что в g нужно записать матрицу смежности. На самом деле для Вами приведенной матрицы смежности:

В g нужно записать такие данные:
1
2
3
""
Т.е. в каждой строке записаны номера вершин в которые есть путь из вершины, соответствующей этой строке.
В строке 0 находится только 1 (из вершины 0 есть путь в вершину 1).
В строке 1 находится только 2 (из вершины 1 есть путь в вершину 2).
и т.д.
Вот рабочий код:

и еще немного: для того какой результат Вы находите Вам вообще не нужен вектор p. вы просто выводите расстояния от вершины 0 до всех остальных вершин (причем если расстояние 0 (за исключением самой вершины 0), то значит вершина вообще недостижима из вершины 0). Вектор p нужен только когда нужно будет вывести на экран не длинну пути, а сам путь (через какие вершины проходит самый короткий путь от вершины 0 до нужной вершины).

Под обходом понимается последовательное посещение (обработка) вершин графа в определённом порядке. Одним из двух часто использующихся способов обхода является обход в ширину, или BFS (англ. breadth-first search, поиск в ширину). Его иногда также называют волновым, по аналогии с распространяющейся волной.

Суть BFS достаточно проста. Обход начинается с посещения определённой вершины (для обхода всего графа часто выбирается произвольная вершина). Затем алгоритм посещает соседей этой вершины. За ними - соседей соседей, и так далее.

Более формально, пусть \(d[i]\) - расстояние от начальной вершины до вершины с номером \(i\) (длина кратчайшего пути в рёбрах). BFS посещает вершины в порядке возрастания \(d[i]\): от наименее до наиболее отдалённых.

Серым помечены вершины в очереди на посещение, чёрным - уже посещённые.

Алгоритм

Как можно увидеть из иллюстрации, сам алгоритм достаточно тривиален. Поддерживается очередь из вершин для посещения. При посещении очередной вершины в очередь добавляются все её соседи, которые ещё не были посещены и ещё не находятся в очереди. Для проверки, была ли вершина уже посещена, используется массив меток. Изначально \(visited[i] = false\) для всех \(i\) кроме начальной вершины. При добавлении вершины \(i\) в очередь \(visited[i]\) присваивается \(true\).

Реализация

Реализуем простой BFS для графа заданного списком смежности:

Практическое применение: вычисление расстояния до всех вершин

BFS по определению посещает вершины в порядке возрастания расстояния от них до начальной. Поэтому одним из главных его применений является вычисление расстояния от заданной вершины до всех остальных.

Модификация алгоритма, необходимая для этого, минимальна. Пусть при обработке вершины \(i\) мы добавляем в очередь вершину \(j\). Это значит, что кратчайший путь от начальной вершины до вершины \(j\) проходит через вершину \(i\).

Доказательство: допустим, что существует более короткий путь в \(j\), не проходящий через \(i\). Обозначим предпоследнюю вершину этого пути \(k\). Так как путь в \(j\) через \(k\) короче пути в \(j\) через \(i\) можно сделать вывод, что расстояние до \(k\) меньше расстояния до \(i\). Но по определению BFS вершина \(k\) в таком случае была бы уже обработана, а значит, \(j\) бы уже находилась в очереди. Получили противоречие. Следовательно, подходящей вершины \(k\) не существует.

Обозначим расстояние от начальной вершины до вершины \(i\) как \(dst[i]\). В таком случае верно, что \(dst[j] = dst[i] + 1\). Таким образом мы можем рассчитать растояние для всех вершин.

Стоит заметить одно важное свойство. Если существуют вершины, в которые невозможно добраться из 1-й вершины, \(dst[i]\) для них будет равно \(-1\). Можно вспомнить об определении связности графа. Если после окончания работы алгоритма в массиве \(dst\) осталось хоть одно значение \(-1\), то граф не является связным. Таким образом BFS можно также использовать для проверки на связность.

BFS с сохранением пути

Иногда кроме длины кратчайшего пути в задаче требуется также вывести вершины, через которые он проходит. BFS легко модифицируется для решения этой задачи.

Пусть при обработке вершины \(i\) мы добавляем в очередь вершину \(j\). Это значит, что кратчайший путь от начальной вершины до вершины \(j\) проходит через вершину \(i\) (доказательство выше). Значит последним ребром в кратчайшем пути до \(j\) будет ребро \(i - j\), а весь остальной путь будет совпадать с кратчайшим путём до \(i\). Просто сохраним тот факт, что предыдущей вершиной для \(j\) является \(i\). Для этого будем использовать массив \(prev\). Простой пометки \(prev[j] = i\) хватит для восстановления пути после завершения работы алгоритма.

Применение BFS без явных графов

Кроме собственно графов, BFS часто используется для поиска путей в прямоугольном поле, состоящем из клеток. В этом поле находится некоторая “фигура” которая может перемещаться согласно определённым условиям. На самом деле, такое поле задаёт граф, вершины которого - клетки поля, а ребро из одной клетки в другую существует, если фигура может совершить соответствующее перемещение.

Такие задачи можно решать без явного построения списка смежности, работая только с самой матрицей. В качестве примера приведём решение следующей задачи:

На шахматной доске размером \(N * N\) (\(1 \le N \le 1000\)) в клетке \((x_1, y_1)\) находится конь. Определить, за сколько ходов он может попасть в клетку \((x_2, y_2)\).

На всякий случай напомним, что конь может ходить “буквой Г” в любом направлении. Математически это значит, что конь может изменить одну из своих координат на \(2\) или \(-2\), а другую на \(1\) или \(-1\). Это даёт нам следующий набор векторов, задающий ходы коня:

Как видите, отличие заключается лишь в том, что вместо перебора соседних вершин из списка смежности, мы вычисляем их на лету, используя возможные ходы фигуры.

Алгоритм ищет кратчайший путь, и его длину от заданной вершины до всех остальных. При этом просматривается последовательно каждый уровень соседей стартовой вершины. То есть мы в прямом смысле ходим в ширину по всему уровню. Подробнее вы всегда можете почитать на википедии. А вообще, если вы ищете реализацию, то уже знаете сам алгоритм, так что погнали реализовывать поиск в ширину!

Моя реализация поиска в ширину на c++

Граф представлен следующим образом. Массив(vector c++) из n элементов, где n — число вершин в графе. Каждый элемент массива соответствует вершине графа и содержит вложенный массив — список вершин, смежных с данной.

Функция реализации принимает на вход сам граф и номер стартовой вершины, отрабатывает, и заполняет два массива: массив расстояний от каждой вершины до стартовой, и массив предков каждой вершины на пути к стартовой. С помощью второго массива восстанавливается полный путь от стартовой вершины до всех остальных.

Исходный код алгоритма поиска в ширину на c++

Задачи, решаемые с помощью поиска в ширину

Проверка графа на связность

Выполняется проще простого. Инициализируем массив distance и смотрим от всех ли вершин можно добраться до стартовой. Если хотя бы от одной вершины путь отсутствует — граф несвязен.

Подсчет количества компонент связности графа

Смысл в том, что после вызова процедуры BFS для вершины i , в массиве distance будут инициализированы все вершины из ее компоненты. Вызывая процедуру для каждой вершины, мы найдем все возможные компоненты связности.

Одна из основных операций, которые выполняются с графами, — это определение всех вершин, достижимых от заданной вершины. Представьте, что вы пытаетесь определить, как можно добраться от одного города в другой с возможными пересадками. К одним городам можно добраться напрямую, к другим нужно ехать в обход через другие города. Существует много других ситуаций, в которых может понадобиться нахождение всех вершин, к которым можно найти путь от заданной вершины. Так вот, существует два основных способа обхода графов: обход в глубину и обход в ширину , которые мы и рассмотрим. Оба способа обеспечат перебор всех связных вершин. Для дальнейшего рассмотрения алгоритмов в глубину и ширину возьмем следующий граф:

Обход в глубину

Посетить смежную, ранее не посещенную вершину, пометить её и занести в стек.
Перейти на данную вершину.
Повторить этап 1.
Если выполнение пункта 1 невозможно, вернуться к предыдущей вершины и попытаться повторить правило 1. Если это невозможно — вернуться к вершине до нее, и так далее, пока не найдем вершину, с которой можно продолжить обход.
Продолжать до тех пор, пока все вершины не окажутся в стеке.

Так как у нас есть матрица смежности и в методе прохода мы используем цикл, вложенный в цикл, то временная сложность будет O(N²) .

Обход в ширину

Опять же: мы имеем матрицу смежности и используем цикл, вложенный в цикл, поэтому O(N²) — временная сложность приведенного алгоритма.

4. Алгоритм Дейкстры

Таким образом, мы отмечаем что текущий кратчайший путь до AE = 9.

С вершин A и B это могут быть вершины D (7), C (5), E (6).

Наименьший вес ребра имеет С , поэтому к этой вершине и перейдем.

AD = 5( AC ) + 3( CD ) = 8, но так как предыдущий кратчайший путь AC = 7, то есть меньше, чем этот через С , мы так и оставляем кратчайший путь AD = 7, без изменений.
CE = 5( AC ) + 4( CE ) = 9, этот новый кратчайший путь равен прежнему поэтому мы оставляем его без изменения тоже.

AF = 7( AD ) + 3( DF ) = 10

AG = 7( AD ) + 3( DF ) + 4( FG ) = 14

Собственно, вот мы и нашли путь от A до G .

Но чтобы убедиться в том, что он кратчайший, мы должны прогнать наши этапы и для вершины E .

AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, этот путь длиннее прежнего кратчайшего AG(14), поэтому данный путь мы оставляем без изменений.

Так как вершин, ведущих от G , нет, прогонять этапы для данной вершины не имеет смысла. Поэтому работу алгоритма можно считать законченной.

Элементы имеют кратчайшие пути из точки A: A = 0 B = 3 (A -> B) C = 5 (A -> C) D = 7 (A -> D) E = 9 (A -> B -> E) F = 10 (A -> D -> F) G = 14 (A -> D -> F -> G)

Временная сложность данного алгоритма — ничто иное как O(N²) , так как у нас есть циклы, вложенные в цикл. Что же, на этом у меня сегодня всё, спасибо за внимание!

Читайте также: