Обход графов
Поиск в ширину и в глубину
Вход: граф 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 хостинг.Ол саған ұнайды ма? Әлеуметтік желілерде бөлісіңіз!
Пікірлер
- Ora Iro
- Жел. 24, 2024, 6:38 Т.Ж.
C++ - Тест 001. Первая программа и типы данных
- Нәтиже:40ұпай,
- Бағалау ұпайлары-8
- Akiv Doros
- Қар. 11, 2024, 2:58 Т.Қ.
C++ - Тест 004. Указатели, Массивы и Циклы
- Нәтиже:50ұпай,
- Бағалау ұпайлары-4
- molni99
- Қаз. 26, 2024, 1:37 Т.Ж.
C++ - Тест 004. Указатели, Массивы и Циклы
- Нәтиже:80ұпай,
- Бағалау ұпайлары4