Логотип
О сервисе
Войти
Информатика • 11 класс
Просмотрено45

Алгоритмы обхода графов (C++)

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

Рекомендуем

Получите бесплатный доступ к сервису «Облако знаний»
  • тысячи интерактивных работ
  • обновлённый контент по ФГОС
  • свежие варианты ОГЭ/ЕГЭ
  • опорные конспекты по всем предметам

Это и многое другое доступно после входа через Educont.ru

Войти через Educont.ru

Если у вас нет доступа к Educont.ru, зарегистрируйтесь, а затем активируйте классу бесплатный доступ к контенту «Облако знаний».

Материалы - Облако знаний
Логотип облако знаний
+7 (499) 322-07-57
info@oblakoz.ru

Контактный центр

МО, г. Долгопрудный, Лихачевский проезд, 4, стр. 1

Отдел заботы о пользователях

Следите за нами:
Группа телеграм облако знанийТелеграмГруппа вконтакте облако знанийВКонтакте
Политика конфиденциальности

© ООО «Физикон Лаб», 2023