Обход графа - Graph traversal
 | Эта статья нужны дополнительные цитаты для проверка. (Октябрь 2014 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
| График и дерево алгоритмы поиска |
|---|
| Списки |
|
| похожие темы |
В Информатика, обход графа (также известен как Поиск граф) относится к процессу посещения (проверки и / или обновления) каждой вершины в график. Такие обходы классифицируются по порядку посещения вершин. Обход дерева это частный случай обхода графа.
Резервирование
В отличие от обхода дерева, обход графа может потребовать, чтобы некоторые вершины были посещены более одного раза, так как перед переходом к вершине не обязательно известно, что она уже была исследована. Поскольку графиков становится больше плотный, эта избыточность становится все более распространенной, что приводит к увеличению времени вычислений; по мере того как графики становятся более разреженными, верно и обратное.
Таким образом, обычно необходимо помнить, какие вершины уже были исследованы алгоритмом, чтобы вершины пересматривались как можно реже (или, в худшем случае, чтобы предотвратить бесконечное продолжение обхода). Это может быть выполнено путем связывания каждой вершины графа с состоянием «цвет» или «посещение» во время обхода, которое затем проверяется и обновляется, когда алгоритм посещает каждую вершину. Если вершина уже была посещена, она игнорируется и путь больше не используется; в противном случае алгоритм проверяет / обновляет вершину и продолжает движение по текущему пути.
Некоторые частные случаи графов подразумевают посещение других вершин в их структуре и, таким образом, не требуют явной записи посещения во время обхода. Важным примером этого является дерево: во время обхода можно предположить, что все вершины-предки текущей вершины (и другие в зависимости от алгоритма) уже посещены. Оба в глубину и поиск по графу в ширину представляют собой адаптации древовидных алгоритмов, отличающиеся в первую очередь отсутствием структурно определенной «корневой» вершины и добавлением структуры данных для записи состояния посещения обхода.
Алгоритмы обхода графа
Примечание. - Если каждая вершина в графе должна быть пройдена древовидным алгоритмом (например, DFS или BFS), то алгоритм должен вызываться по крайней мере один раз для каждого связный компонент графа. Этого легко добиться, перебирая все вершины графа, выполняя алгоритм на каждой вершине, которая еще не посещена при проверке.
Поиск в глубину
Поиск в глубину (DFS) - это алгоритм обхода конечного графа. DFS посещает дочерние вершины перед посещением родственных вершин; то есть, он проходит глубину любого конкретного пути, прежде чем исследовать его широту. Стек (часто программный стек вызовов через рекурсия ) обычно используется при реализации алгоритма.
Алгоритм начинается с выбранной «корневой» вершины; затем он итеративно переходит от текущей вершины к соседней, непосещенной вершине, пока не перестанет находить неисследованную вершину для перехода из ее текущего местоположения. Тогда алгоритм отступления вдоль ранее посещенных вершин, пока не найдет вершину, связанную с еще более неизведанной территорией. Затем он продолжит движение по новому пути, как и раньше, с обратным отслеживанием, когда он встречается с тупиками, и завершится только тогда, когда алгоритм вернется назад мимо исходной «корневой» вершины с самого первого шага.
DFS является основой многих алгоритмов, связанных с графами, включая топологические виды и проверка планарности.
Псевдокод
- Вход: График грамм и вершина v из грамм.
- Выход: Разметка ребер связного компонента v как края открытия и задние края.
процедура DFS (грамм, v) является метка v как исследовано для всех края е в грамм.incidentEdges (v) делать если край е неизведанный тогда ш ← грамм.adjacentVertex (v, е) если вершина ш неизведанный тогда метка е как обнаруженное ребро рекурсивно вызвать DFS (грамм, ш) еще метка е как задний край
Поиск в ширину
![[значок]](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 посещает родственные вершины перед посещением дочерних вершин, а очередь используется в процессе поиска. Этот алгоритм часто используется для поиска кратчайшего пути от одной вершины к другой.
Псевдокод
- Вход: График грамм и вершина v из грамм.
- Выход: Ближайшая к v удовлетворяющие некоторым условиям, или null, если такой вершины не существует.
процедура BFS (грамм, v) является создать очередь Q ставить в очередь v на Q отметка v пока Q не пусто делать ш ← Q.dequeue () если ш это то, что мы ищем тогда возвращаться ш для всех края е в грамм.adjacentEdges (ш) делать Икс ← грамм.adjacentVertex (ш, е) если Икс не отмечен тогда отметка Икс ставить в очередь Икс на Q возвращаться ноль
Приложения
Поиск в ширину можно использовать для решения многих задач теории графов, например:
- найти все вершины в одной связный компонент;
- Алгоритм Чейни;
- найти кратчайший путь между двумя вершинами;
- тестирование графика для двудольность;
- Алгоритм Катхилла – Макки нумерация ячеек;
- Алгоритм Форда – Фулкерсона для вычисления максимальный поток в проточная сеть;
- сериализация / десериализация двоичного дерева по сравнению с сериализацией в отсортированном порядке (позволяет эффективно реконструировать дерево);
- алгоритмы создания лабиринта;
- заливка алгоритм маркировки смежных областей двухмерного изображения или n-мерного массива;
- анализ сетей и отношений.
Исследование графа
Задачу исследования графа можно рассматривать как вариант обхода графа. Это онлайн-проблема, означающая, что информация о графе раскрывается только во время выполнения алгоритма. Общая модель выглядит следующим образом: дан связный граф грамм = (V, E) с неотрицательными краевыми весами. Алгоритм начинается с некоторой вершины и знает все исходящие ребра, а также вершины на концах этих ребер, но не более того. Когда посещается новая вершина, снова становятся известны все инцидентные исходящие ребра и вершины в конце. Цель - посетить все п вершины и вернуться в исходную вершину, но сумма весов тура должна быть как можно меньше. Проблема также может быть понята как конкретная версия задача коммивояжера, где продавец должен находить график на ходу.
Для общих графов наиболее известные алгоритмы как для неориентированных, так и для ориентированных графов представляют собой простые жадный алгоритм:
- В неориентированном случае жадный тур не более чем О(ln п)в разы длиннее оптимального тура.[1] Лучшая нижняя граница, известная для любого детерминированного онлайн-алгоритма, равна 2.5 − ε;[2]
- В направленном случае жадный тур не превышает (п − 1) в разы длиннее оптимального тура. Это соответствует нижней границе п − 1.[3] Аналогичная конкурентная нижняя граница Ω(п) также выполняется для рандомизированных алгоритмов, которым известны координаты каждого узла геометрического вложения. Если вместо посещения всех узлов необходимо найти только один узел "сокровище", то конкурентные границы будут Θ(п2) на ориентированных графах с единичным весом как для детерминированных, так и для рандомизированных алгоритмов.
Универсальные последовательности обхода
| Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Декабрь 2016 г.) |
А универсальная последовательность обхода представляет собой последовательность инструкций, составляющих обход графа для любого регулярный граф с заданным количеством вершин и для любой начальной вершины. Вероятностное доказательство было использовано Aleliunas et al. чтобы показать, что существует универсальная последовательность обхода с числом инструкций, пропорциональным О(п5) для любого регулярного графа с п вершины.[4] Шаги, указанные в последовательности, относятся к текущему узлу, а не абсолютны. Например, если текущий узел vj, и vj имеет d соседи, то в последовательности обхода будет указан следующий узел для посещения, vj+1, как яth сосед vj, где 1 ≤ я ≤ d.
Рекомендации
- ^ Rosenkrantz, Daniel J .; Стернс, Ричард Э .; Льюис, II, Филип М. (1977). «Анализ нескольких эвристик для задачи коммивояжера». SIAM Журнал по вычислениям. 6 (3): 563–581. Дои:10.1137/0206041.
- ^ Добрев, Стефан; Кралович, Растислав; Марку, Еврипид (2012). «Исследование графов онлайн с советом». Proc. 19-го Международного коллоквиума по структурной информационно-коммуникационной сложности (SIROCCO). Конспект лекций по информатике. 7355: 267–278. Дои:10.1007/978-3-642-31104-8_23. ISBN 978-3-642-31103-1.
- ^ Ферстер, Клаус-Тихо; Ваттенхофер, Роджер (декабрь 2016 г.). «Нижняя и верхняя границы конкуренции для исследования ориентированного графа в Интернете». Теоретическая информатика. 655: 15–29. Дои:10.1016 / j.tcs.2015.11.017.
- ^ Алелиунас, Р .; Karp, R .; Lipton, R .; Lovász, L .; Ракофф, К. (1979). «Случайные блуждания, универсальные последовательности обходов и сложность задач лабиринта». 20-й ежегодный симпозиум по основам компьютерных наук (SFCS 1979): 218–223. Дои:10.1109 / SFCS.1979.34.