Обход графов
Поиск в ширину и в глубину
Вход: граф G(V, Е), представленный списками смежности Г.
Выход: последовательность вершин обхода.
for v ∊ V do
x[v]: =0{ вначале все вершины не отмечены}
end for
select v ∊ V{ начало обхода — произвольная вершина }
v → Т{ помещаем v в структуру данных Т ... }
x[v] : = 1{... и отмечаем вершину v }
repeat u← Т{ извлекаем вершину из структуры данных Т ... }
yield u{ ... и возвращаем ее в качестве очередной пройденной вершины }
for w ∊ Г(u) do
if x[w] =0 then
w → Т{ помещаем w в структуру данных Т ... }
x[w]: = 1{ ... и отмечаем вершину w }
end if
end for
until Т = Ø
Если Т — это стек (LIFO — Last In First Out), то обход называется поиском в глубину. Если Т — это очередь (FIFO — First In First Out), то обход называется поиском в ширину.
На входе программы задаётся количество вершин и списки смежности вершин (в порядке возрастания номера вершины). Результат работы программы: последовательность обхода вершин в глубину, через запятую - в ширину.
Есть алгоритм и его необходимо воплотить в программу на С++
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.Вам это нравится? Поделитесь в социальных сетях!
Комментарии
Пожалуйста, авторизуйтесь или зарегистрируйтесь
- Akiv Doros
- 12 ноября 2024 г. 1:58
C++ - Тест 004. Указатели, Массивы и Циклы
- Результат:50баллов,
- Очки рейтинга-4
- molni99
- 26 октября 2024 г. 11:37
C++ - Тест 004. Указатели, Массивы и Циклы
- Результат:80баллов,
- Очки рейтинга4
- molni99
- 26 октября 2024 г. 11:29
C++ - Тест 004. Указатели, Массивы и Циклы
- Результат:20баллов,
- Очки рейтинга-10