- Обход графа – это процесс систематического просмотра всех рёбер или вершин графа.
- Алгоритм обхода графа в глубину (Рис. А).
- Выбираем стартовую вершину.
- Переходим от вершине к следующей непросмотренной вершине, пока это возможно.
- Возвращаемся в предыдущую вершину.
- Повторяем шаги 2 и 3, пока все вершины не будут просмотрены.
- Алгоритм обхода графа в ширину (Рис. Б).
- Выбираем стартовую вершину.
- Обходим все вершины, смежные со стартовой.
- Обходим все вершины, смежные со смежным стартовой.
- И так далее.
- С помощью обхода в глубину и обхода в ширину можно попасть во все вершины графа только, если граф является связным.
