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

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

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

BFS

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

  • Выберем некую вершину, корень. Обозначим её \(s\)
  • Пусть \(colors\) - массив "цветов вершин".
  • Цветов всего 3:

1. white - "вершина не посещена"

2. gray - "вершина рассматривается"

3. black - "вершина уже просмотрена"

  • \(d\) - расстояние от данной вершины до корня
  • \(P\) - предок вершины