ТГиК-2019-Лекция-25.11.2019: различия между версиями
Перейти к навигации
Перейти к поиску
(→BFS) |
|||
| Строка 10: | Строка 10: | ||
1. <math>white</math> - "вершина не посещена" | 1. <math>white</math> - "вершина не посещена" | ||
| − | 2. <math> { \color{gray} gray} </math> - "вершина рассматривается" | + | 2. <math> { \color{gray} {gray}} </math> - "вершина рассматривается" |
3. <math> { \color{black} black} </math> - "вершина уже просмотрена" | 3. <math> { \color{black} black} </math> - "вершина уже просмотрена" | ||
Версия 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 \)
