Обход графа
 | Эта статья нуждается в дополнительных цитатах для проверки . ( октябрь 2014 г. ) |
В информатике ) обход графа (также известный как поиск по графу относится к процессу посещения (проверки и/или обновления) каждой вершины графа . Такие обходы классифицируются по порядку посещения вершин. Обход дерева — это частный случай обхода графа.
Резервирование
[ редактировать ]В отличие от обхода дерева, обход графа может потребовать посещения некоторых вершин более одного раза, поскольку до перехода к вершине не обязательно известно, что она уже исследована. По мере того, как графы становятся более плотными , эта избыточность становится более распространенной, что приводит к увеличению времени вычислений; поскольку графики становятся все более разреженными, справедливо обратное.
Таким образом, обычно необходимо помнить, какие вершины уже были исследованы алгоритмом, чтобы вершины посещались как можно реже (или, в худшем случае, чтобы обход не продолжался бесконечно). Этого можно достичь путем связывания каждой вершины графа с состоянием «цвета» или «посещения» во время обхода, которое затем проверяется и обновляется по мере посещения алгоритмом каждой вершины. Если вершина уже была посещена, она игнорируется и путь дальше не продолжается; в противном случае алгоритм проверяет/обновляет вершину и продолжает движение по текущему пути.
Некоторые частные случаи графов предполагают посещение других вершин в их структуре и, таким образом, не требуют явной записи посещения во время обхода. Важным примером этого является дерево: при обходе можно предположить, что все «предковые» вершины текущей вершины (и другие в зависимости от алгоритма) уже посещены. как в глубину, так и Поиск в графе в ширину представляет собой адаптацию древовидных алгоритмов, отличающихся, прежде всего, отсутствием структурно определенной «корневой» вершины и добавлением структуры данных для записи состояния посещения.
Алгоритмы обхода графа
[ редактировать ]Примечание. — Если каждая вершина графа должна быть пройдена с помощью древовидного алгоритма (например, DFS или BFS), то этот алгоритм должен быть вызван хотя бы один раз для каждого связного компонента графа. Этого легко достичь, перебирая все вершины графа, выполняя алгоритм для каждой вершины, которая еще не посещена при проверке.
Поиск в глубину
[ редактировать ]Поиск в глубину (DFS) — это алгоритм обхода конечного графа. DFS посещает дочерние вершины перед посещением родственных вершин; то есть он пересекает глубину любого конкретного пути, прежде чем исследовать его ширину. программы Стек (часто стек вызовов через рекурсию ) обычно используется при реализации алгоритма.
Алгоритм начинается с выбранной «корневой» вершины; Затем он итеративно переходит от текущей вершины к соседней, непосещенной вершине, пока не перестанет находить неисследованную вершину для перехода из ее текущего местоположения. Затем алгоритм возвращается к ранее посещенным вершинам, пока не найдет вершину, связанную с еще более неизведанной территорией. Затем он продолжит идти по новому пути, как и раньше, возвращаясь назад, когда сталкивается с тупиками, и заканчивая только тогда, когда алгоритм вернулся за исходную «корневую» вершину с самого первого шага.
DFS является основой для многих алгоритмов, связанных с графами, включая топологическую сортировку и проверку планарности .
Псевдокод
[ редактировать ]- Входные данные граф G и вершина v графа G. :
- Выходные данные : Маркировка ребер в компоненте связности v как ребра открытия и задние ребра.
procedure DFS(G, v) is
label v as explored
for all edges e in G.incidentEdges(v) do
if edge e is unexplored then
w ← G.adjacentVertex(v, e)
if vertex w is unexplored then
label e as a discovered edge
recursively call DFS(G, w)
else
label e as a back edge
Поиск в ширину
[ редактировать ]![[икона]](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png){kind=small} | Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( октябрь 2012 г. ) |
Поиск в ширину (BFS) — это еще один метод обхода конечного графа. BFS посещает одноуровневые вершины перед посещением дочерних вершин, и очередь в процессе поиска используется . Этот алгоритм часто используется для поиска кратчайшего пути от одной вершины к другой.
Псевдокод
[ редактировать ]- Входные данные граф G и вершина v графа G. :
- Выходные данные : ближайшая к v вершина , удовлетворяющая некоторым условиям, или ноль, если такой вершины не существует.
procedure BFS(G, v) is
create a queue Q
enqueue v onto Q
mark v
while Q is not empty do
w ← Q.dequeue()
if w is what we are looking for then
return w
for all edges e in G.adjacentEdges(w) do
x ← G.adjacentVertex(w, e)
if x is not marked then
mark x
enqueue x onto Q
return null
Приложения
[ редактировать ]Поиск в ширину можно использовать для решения многих задач теории графов, например:
- нахождение всех вершин внутри одной компоненты связности ;
- алгоритм Чейни ;
- поиск кратчайшего пути между двумя вершинами;
- проверка графа на двудольность ;
- Нумерация ячеек алгоритма Катхилла – Макки ;
- Алгоритм Форда – Фулкерсона для расчета максимального потока в проточной сети ;
- сериализация/десериализация двоичного дерева или сериализация в отсортированном порядке (позволяет эффективно перестроить дерево);
- алгоритмы построения лабиринтов ;
- алгоритм заливки для маркировки смежных областей двумерного изображения или n-мерного массива;
- анализ сетей и взаимоотношений.
Исследование графа
[ редактировать ]Задачу исследования графа можно рассматривать как вариант обхода графа. Это онлайн-задача , а это означает, что информация о графе раскрывается только во время выполнения алгоритма. Общая модель выглядит следующим образом: задан связный граф G = ( V , E ) с неотрицательными весами ребер. Алгоритм начинается с некоторой вершины и знает все инцидентные исходящие ребра и вершины на концах этих ребер, но не более того. При посещении новой вершины снова известны все инцидентные исходящие ребра и вершины в конце. Цель — посетить все n вершин и вернуться в начальную вершину, но сумма весов тура должна быть как можно меньше. Задачу также можно понимать как конкретную версию задачи о коммивояжере , где продавцу приходится на ходу находить граф.
Для общих графов наиболее известным алгоритмом как для неориентированных, так и для ориентированных графов является простой жадный алгоритм :
- В неориентированном случае жадный обход не более чем в O (ln n ) раз длиннее оптимального. [1] Наилучшая нижняя граница, известная для любого детерминированного онлайн-алгоритма, равна 10/3. [2]
- Неориентированные графы единичного веса можно исследовать с конкурентным коэффициентом 2 − ε , [3] что уже является жесткой границей для графов головастиков . [4]
- В направленном случае жадный тур не более чем в ( n − 1 ) раз длиннее оптимального тура. Это соответствует нижней границе n − 1 . [5] Аналогичная конкурентная нижняя граница Ω ( n ) также справедлива для рандомизированных алгоритмов, которым известны координаты каждого узла в геометрическом вложении. Если вместо посещения всех узлов необходимо найти только один узел «сокровища», конкурентные границы равны Θ ( n 2 ) на ориентированных графах с единичным весом как для детерминированных, так и для рандомизированных алгоритмов.
Универсальные последовательности обхода
[ редактировать ] | Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( декабрь 2016 г. ) |
Универсальная последовательность обхода — это последовательность инструкций, содержащая обход любого регулярного графа с заданным количеством вершин и для любой начальной вершины. Вероятностное доказательство было использовано Алелиунасом и др. чтобы показать, что существует универсальная последовательность обхода с числом инструкций, пропорциональным O ( n 5 ) для любого регулярного графа с n вершинами. [6] Шаги, указанные в последовательности, относятся к текущему узлу, а не абсолютно. Например, если текущий узел — v j , а v j имеет d соседей, то последовательность обхода будет указывать следующий узел для посещения, v j +1 , как i й сосед v j , где 1 ≤ i ≤ d .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Розенкранц, Дэниел Дж.; Стернс, Ричард Э.; Льюис, II, Филип М. (1977). «Анализ нескольких эвристик для задачи коммивояжера». SIAM Journal по вычислительной технике . 6 (3): 563–581. дои : 10.1137/0206041 . S2CID 14764079 .
- ^ Биркс, Александр; Диссер, Янн; Хопп, Александр В.; Карусату, Кристина (май 2021 г.). «Улучшенная нижняя граница для исследования конкурентных графов». Теоретическая информатика . 868 : 65–86. arXiv : 2002.10958 . дои : 10.1016/j.tcs.2021.04.003 . S2CID 211296296 .
- ^ Миядзаки, Шуичи; Моримото, Наоюки; Окабе, Ясуо (2009). «Проблема онлайн-исследования графов на ограниченных графах». IEICE Транзакции по информации и системам . Е92-Д (9): 1620–1627. Бибкод : 2009ИЕИТИ..92.1620М . дои : 10.1587/transinf.E92.D.1620 . HDL : 2433/226939 . S2CID 8355092 .
- ^ Брандт, Себастьян; Ферстер, Клаус-Тихо; Маурер, Джонатан; Ваттенхофер, Роджер (ноябрь 2020 г.). «Онлайн-исследование графов ограниченного класса графов: оптимальные решения для графов-головастиков». Теоретическая информатика . 839 : 176–185. arXiv : 1903.00581 . дои : 10.1016/j.tcs.2020.06.007 . S2CID 67856035 .
- ^ Ферстер, Клаус-Тихо; Ваттенхофер, Роджер (декабрь 2016 г.). «Нижняя и верхняя конкурентные границы для онлайн-исследования направленных графов» . Теоретическая информатика . 655 : 15–29. дои : 10.1016/j.tcs.2015.11.017 .
- ^ Алелюнас, Р.; Карп, Р.; Липтон, Р.; Ловас, Л.; Ракофф, К. (1979). «Случайные блуждания, универсальные последовательности обхода и сложность задач лабиринта». 20-й ежегодный симпозиум по основам информатики (SFCS, 1979) : 218–223. дои : 10.1109/SFCS.1979.34 . S2CID 18719861 .