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

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску
(Новая страница: «Тема лекции - алгоритм поиска в ширину и алгоритм поиска в глубину == BFS == Пусть задан гра...»)
 
Строка 7: Строка 7:
 
* Пусть <math>colors</math> - массив "цветов вершин".  
 
* Пусть <math>colors</math> - массив "цветов вершин".  
 
* Цветов всего 3:
 
* Цветов всего 3:
* white - "вершина не посещена"
+
1. white - "вершина не посещена"
* gray - "вершина рассматривается"
+
2. gray - "вершина рассматривается"
* black - "вершина уже просмотрена"
+
3. black - "вершина уже просмотрена"
* d - расстояние от данной вершины до корня
+
* <math>d</math> - расстояние от данной вершины до корня
* P - предок вершины
+
* <math>P</math> - предок вершины

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

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

BFS

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

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