Структури от данни в програмирането 2005/06 - упражнения и практикум

Задачите за търсене на път в граф са два типа: задачи за съществуване (има ли път с дадено свойство, да се намери един път с дадено свойство) и задачи за всяко (да се изведат/съберат всички пътища с дадено свойство).

Тези два типа могат да се обобщят със следните функции от по-висок ред:

Задача 1. Да се напише функция bool findOne(IntGraph& g, int a, IntList& w, bool(*found)(IntGraph& g, IntList& w)), която намира дали в графа има ацикличен път от върха a, който удовлетворява условието found.

С помощта на тази функция да се решат задачите:

1. Има ли ацикличен път от a до b?
2. Има ли ацикличен път от a до b с дължина точно/поне/най-много k?
3. Има ли ацикличен път с дължина поне k?
4. Има ли ацикличен път от a до b, който минава през c?

Задача 2. Да се напише функция void mapAll(IntGraph& g, int a, int b, IntList& w, void(*func)(IntGraph& g, IntList& w)), която за всеки ацикличен път от a до b изпълнява функцията func.

С помощта на тази функция да се решат задачите:

1. Да се отпечатат всички ациклични пътища от a до b.
2. Да се съберат всички ациклични пътища от a до b в списък.
3. Да се намерят всички пътища от a до b, които минават през c.

Задача 3. Да се напише функция void findAll(IntGraph& g, int a, int b, IntList& w, bool(*found)(IntGraph& g, IntList& w),bool(*func)(IntGraph& g, IntList& w)), която за всеки ацикличен път от a до b, който изпълнява условието found, прилага функцията func.

С помощта на тази функция да се решат задачите:

1. mapAll
2. findOne
3. Да се отпечатат всички ациклични пътища, от a до b, в които върхът c е точно по средата.
4. Да се отпечатат всички ациклични пътища от a, в които върхът b се среща след върха c.
5. Да се намерят всички Хамилтонови пътища в даден граф (ациклични пътища, в които всеки връх се среща точно веднъж).
6. Има ли връх, през който минават всички пътища от a до b?

Публикувайте на форума идеи за още задачи, решенията на които стават (сравнително) лесно с функции от по-висок ред.