Повторяем шаги 1-3 до тех пор, пока
Выполняем для неё процедуру DFS().
Из множества всех белых вершин выберем любую вершину, обозначим её .
Пусть задан , где множество вершин графа, множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:
[ ] Алгоритм поиска в глубину
Поиск в глубину ( Depth-first search, DFS) один из методов обхода . Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент, топологической сортировки.
Материал из Википедии свободной энциклопедии
Поиск в глубину Википедия
Комментариев нет:
Отправить комментарий