Задачи (2018/2019)
Задача 8а. [5.3.1] bfs.c
Напишете програма за обхождане на граф с n върха в ширина
(BFS), като началният връх има номер 1+ f mod n
където f е факултетният номер на студента.
Вход:
На входа се задава най-напред броя на дъгите на свързан
неориентиран граф, а после списък от тези дъги. Списъкът се състои
от не повече от 1000 дъги, зададени с двойки номера на върхове.
Върховете на графа са номерирани с последователни цели положителни
числа, започвайки от 1.
Изход:
Отпечатва се списък (редица) на един ред (с разделител един
интервал) от номерата на върховете на графа, получени при
обхождането му в ширина.
Примерен вход:
3
1 2
2 3
1 4
Задача 8b.
[5.3.2] dfs.c
Напишете програма за обхождане на граф с n върха в дълбочина
(DFS), като началният връх има номер 1+ f mod n
където f е факултетният номер на студента.
Вход:
На входа се задава най-напред броя на дъгите на свързан
неориентиран граф, а после списък от тези дъги. Списъкът се състои
от не повече от 1000 дъги, зададени с двойки номера на върхове.
Върховете на графа са номерирани с последователни цели положителни
числа, започвайки от 1.
Изход:
Отпечатва се списък (редица) на един ред (с разделител един
интервал) от номерата на върховете на графа, получени при
обхождането му в дълбочина.
Примерен вход:
3
1 2
2 3
1 4