ТГиК-2019-Лекция-25.11.2019: различия между версиями

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску
Строка 14: Строка 14:
 
3. black - "вершина уже просмотрена"
 
3. black - "вершина уже просмотрена"
  
*<math>d</math> - расстояние от данной вершины до корня
+
* <math>d</math> - расстояние от данной вершины до корня
*<math>P</math> - предок вершины
+
* <math>P</math> - предок вершины

Версия 11:40, 25 ноября 2019

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

BFS

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

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

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

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

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

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