Обход графика

• Основы обхода графа

  • Обход графа включает проверку и обновление каждой вершины в графе. 
  • Обходы классифицируются по порядку посещения вершин. 
  • Обход дерева является частным случаем обхода графа. 

• Избыточность обхода графа

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

• Методы обхода графа

  • Поиск в глубину (DFS) и поиск по ширине (BFS) являются адаптацией древовидных алгоритмов. 
  • DFS посещает дочерние вершины перед родственными, BFS — наоборот. 
  • DFS использует стек, BFS — очередь. 
  • DFS начинается с корневой вершины и итеративно исследует граф, возвращаясь к уже посещенным вершинам. 
  • BFS также начинается с корневой вершины, но исследует граф в ширину, возвращаясь к исходной вершине только после посещения всех смежных вершин. 

• Приложения обхода графа

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

• Исследование графа

  • Задача исследования графа — это онлайн-проблема, где информация о графе раскрывается во время выполнения алгоритма. 
  • Цель состоит в том, чтобы посетить все вершины графа и вернуться в исходную вершину с минимальной суммой весов ребер. 
  • Для неориентированных графов с единичным весом существует жадный алгоритм с конкурентной границей 2 − ε. 
  • Для ориентированных графов с единичным весом жадный тур не более чем в (n − 1) раз длиннее оптимального. 

• Универсальные последовательности обхода

  • Алелиунас и соавторы показали существование универсальной последовательности обхода с количеством инструкций, пропорциональным O(n5). 
  • Последовательность указывает на следующий узел для посещения на основе текущего узла и его соседей.