Упражнение върху обхождане на граф в дълбочина
Тези задачи целят да упражнят техническите навици и идеите при реализиране на варианти на задачата за обхождане на граф в дълбочина.
Задача 1. Да се намерят всички пътища в произволен граф между върховете му i и j, които имат дължина (брой на върховете по пътя) равна на дадено естествено k. Приемаме, че от всеки връх има път до самия него с дължина 0, който не съсържа никакви върхове.
В тази задача е удачно да се поразсъждава защо "избягването на цикли" в този случай е не просто ненужно, но и вредно. Задачата може да се реши във вариант "има ли такъв път", който след това да се модифицира до "да се намери списък от всички такива пътища".
Задача 2. Да се напише функция, която намира всички пътища между върховете i и j в произволен граф, които минават през един определен връх k. Пътищата трябва да са ациклични.
Задачата може да се реши просто чрез филтриране на всички ациклични пътища между i и j с условието "минава през k". Друг вариант е двукратно пускане на функция за намиране на всички ациклични пътища - от i до k и от k до j - но с внимание!
Задача 3. Да се построи фунция, намираща списък от всички цикли, започващи и свършващи в даден връх на граф.
За тази задача нека приемем следната дефиниция за "цикъл": Цикъл ще наричаме такъв път, по който не се повтарят дъги и чийто начален и краен връх съвпадат. Дефиницията не изключва случай, в който началния (и краен) връх се среща повече от два пъти.
Колко различни цикъла, започващи и завършващи във върха a, има на следната картинка (4)?
Хубаво е да се обмисли набор от помощни фунцкии за тази задача, например функция, която проверява дали в даден път се среща дадена дъга.
Задача 4. Да се построи фунцкия, която проверява дали даден граф е дърво.
Дървото е неориентиран граф без цикли, където между всеки два върха има точно един път. За нашите разглеждания, при които работим с ориентирани графи, ще приемем следното достатъчно условие: граф, в който между всеки два върха има "единствен път точно в едната посока", т.е. няма цикли и които и два върха да си вземем, то единият от тях ще е достижим от другия по единствен начин.
Един вариант за решение на тази задача, където неефективно, но елегантно се намесват готовите вече функции, е следният: да се намери "потенциалният корен" на дървото, т.е. някой връх, в който не влиза нито една дъга. След това да се провери дали всеки друг връх v на графа е достижим от този "потенциален корен" и дали могат да се намерят цикли, които минават през v. Хубаво е да си дефинираме помощна функция, която проверява дали даден връх "би могъл да бъде" корен на евентуалното дърво, проверявайки дали в него "влизат" дъги. Необходимо е също всеки връх да е достижим от корена по единствен начин, което може да се провери чрез функцията за намиране на всички пътища от даден връх до даден друг връх, като се провери броя на елементите на резултата от нея.
Задача 5. Да се построи функция, която намира покриващо дърво с корен върха a на граф в дълбочина.
Покриващо дърво на граф G е граф T, който съдържа всички върхове на G и някои от ребрата на G, така че T е дърво (вж горната дефиниция). Строенето на покрващо дърво съответства на еднократно обхождане на върховете му с някаква стратегия. От реализацията на тази задача лесно се вижда, че броят на ребрата в едно дърво е с едно по-малък от броя на върховете.