ТГиК-2019-Лекция-25.11.2019

Материал из Кафедра Прикладной Математики
Версия от 11:32, 25 ноября 2019; KochetkovaUA (обсуждение | вклад) (Новая страница: «Тема лекции - алгоритм поиска в ширину и алгоритм поиска в глубину == BFS == Пусть задан гра...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к навигации Перейти к поиску

Тема лекции - алгоритм поиска в ширину и алгоритм поиска в глубину

BFS

Пусть задан граф \(G = (V,E) \). Зададим его списком смежности.

  • Выберем некую вершину, корень. Обозначим её \(s\)
  • Пусть \(colors\) - массив "цветов вершин".
  • Цветов всего 3:
  • white - "вершина не посещена"
  • gray - "вершина рассматривается"
  • black - "вершина уже просмотрена"
  • d - расстояние от данной вершины до корня
  • P - предок вершины