Задачи за тренинг
Задача 8а. [5.3.1] bfs.c
Напишете програма за обхождане на граф в ширина (BFS(1))
Вход:
На входа се задава най-напред броя на дъгите на ориентиран
граф, а после списък от тези дъги.Списъкът се състои от не повече от
1000 дъги, зададени с двойки номера на върхове - начало, край.
Върховете на графа са номерирани с последователни цели положителни
числа, започвайки от 1.
.
Изход:
Отпечатва се списък (редица) от върховете на графа, получени при
обхождането му в ширина. Първият член на редицата трябва да бъде 1.
Пример:
3
1 2
2 3
1 4
Решение на примера:
1 2 4 3
https://www.hackerrank.com/contests/cscb010-2015-t08/challenges
Задача
8b. [5.3.2] dfs.c
Обхождане
на граф в дълбочина (DFS(1)),
Вход:
На входа се задава най-напред броя на дъгите на ориентиран
граф, а после списък от тези дъги.Списъкът се състои от не повече от
1000 дъги, зададени с двойки номера на върхове - начало, край.
Върховете на графа са номерирани с последователни цели положителни
числа, започвайки от 1.
.
Изход:
Отпечатва се списък (редица) от върховете на графа, получени при
обхождането му в дълбочина. Първият член на редицата трябва да бъде
1.
Пример:
3
1 2
2 3
1 4
Решение на примера:
1 2 3 4