ТГиК-2019-Лекция-25.11.2019: различия между версиями
Перейти к навигации
Перейти к поиску
| Строка 8: | Строка 8: | ||
*Цветов всего 3: | *Цветов всего 3: | ||
| − | 1. white - "вершина не посещена" | + | 1. <math>white</math> - "вершина не посещена" |
| − | 2. gray - "вершина рассматривается" | + | 2. <math> { \color{gray} gray} </math> - "вершина рассматривается" |
| − | 3. black - "вершина уже просмотрена" | + | 3. <math> { \color{black} black} </math> - "вершина уже просмотрена" |
*<math>d</math> - расстояние от данной вершины до корня | *<math>d</math> - расстояние от данной вершины до корня | ||
*<math>P</math> - предок вершины | *<math>P</math> - предок вершины | ||
| − | Замечание: если пути нет, <math>d = \infty \mbox{ | + | Замечание: если пути нет, <math>d = \infty \mbox{, } d(s)=0 </math> |
<br /> | <br /> | ||
Версия 11:51, 25 ноября 2019
Тема лекции - алгоритм поиска в ширину и алгоритм поиска в глубину
BFS
Пусть задан граф \(G = (V,E) \). Зададим его списком смежности.
- Выберем некую вершину, корень. Обозначим её \(s\)
- Пусть \(colors\) - массив "цветов вершин".
- Цветов всего 3:
1. \(white\) - "вершина не посещена"
2. \( { \color{gray} gray} \) - "вершина рассматривается"
3. \( { \color{black} black} \) - "вершина уже просмотрена"
- \(d\) - расстояние от данной вершины до корня
- \(P\) - предок вершины
Замечание: если пути нет, \(d = \infty \mbox{, } d(s)=0 \)
