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

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

Задача 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?

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

Последно модифициране: събота, 12 ноември 2011, 17:38