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

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску
Строка 14: Строка 14:
 
3. black - "вершина уже просмотрена"
 
3. black - "вершина уже просмотрена"
  
* <math>d</math> - расстояние от данной вершины до корня
+
*<math>d</math> - расстояние от данной вершины до корня
* <math>P</math> - предок вершины
+
*<math>P</math> - предок вершины
 +
 
 +
Замечание: если пути нет, <math>d = \infty \mbox{. } d(s)=0 </math>
 +
 
 +
<br />

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

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

BFS

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

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

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

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

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

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

Замечание: если пути нет, \(d = \infty \mbox{. } d(s)=0 \)