Обход графов
Поиск в ширину и в глубину
Вход: граф 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
Stabiles Hosting des sozialen Netzwerks EVILEG. Wir empfehlen VDS-Hosting für Django-Projekte.Magst du es? In sozialen Netzwerken teilen!
Kommentare
- sdfsdfkp fgskpgokspdog
- 14. Oktober 2024 15:09
C++ - Тест 004. Указатели, Массивы и Циклы
- Ergebnis:90punkte,
- Bewertungspunkte8
- Максим Васильев
- 2. Oktober 2024 04:14
Qt - Тест 001. Сигналы и слоты
- Ergebnis:68punkte,
- Bewertungspunkte-1
- Лев Семенов
- 30. September 2024 11:04
C++ - Тест 001. Первая программа и типы данных
- Ergebnis:53punkte,
- Bewertungspunkte-4