ТГиК-2019-Лекция-25.11.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 \)