Гуманитарные основы комбинаторных алгоритмов

После некоторых размышлений мне стало интересно, как бы я реализовал алгоритм поиска всех путей из одной начальной точки (a) в какую-то другую единственную конечную точку (f) на ориентированном графе. Я уже было начал читать об алгоритмах поиска в глубину и ширину, но мне

подумалось, что интереснее было бы попробовать «изобрести» алгоритм заново, часто ведь при таком подходе можно получить интересную модификацию уже известного алгоритма. Заодно я поставил себе несколько условий: 1) не использовать литературу; 2) использовать нерекурсивный подход; 3) хранить ребра в отдельных массивах, без вложенности.

Сам граф получился такой:

В общем: на входе ориентированный граф с шестью вершинами, задача найти все пути из а в f без рекурсии и с минимальными затратами средств.

Ребра хранятся в нескольких массивах, имя массива – вершина:

$a=array (’b’,’c’,’d’);

$b=array (’d’,’e’,’f’);

$c=array (’d’,’e’,’f’);

$d=array (’e’,’f’);

$e=array (’f’);

Чтобы получить первый путь, я решил пройтись по нулевым индексам каждого массива и склеить их в одну строку х (в этой переменной на каждом этапе будет хранится найденный путь).

В массиве int все элементы, которые есть в графе в обратном порядке.

$int=array (’f’,’e’,’d’,’c’,’b’,’a’);

Тогда получить первый путь очень просто, достаточно пройтись циклом по всем массивам, добавлять в х новое значение с помощью конкатенации, и на каждом этапе использовать элемент из предыдущего массива в качестве указателя на следующий массив.

Этот стиль немного напоминает bash, но код выглядит довольно понятным:

$x=’a’;

$z=$a [0];

while (1) {

$x.=$z;

$z=$ {$z} [0];

if ($z == ’f’) {$x.=$z; break;}

}

И так, мы получили первый путь x=abdef.

Можем вывести его на экран и заняться непосредственно самим алгоритмом, так как все, что было выше, – это только подготовительная часть. По идее от нее можно было бы избавиться, но я ее оставляю и публикую, чтобы был лучше понятен ход мысли.

Выводим на экран первый путь и запускаем первую функцию.

print $x;

print '
»;

search_el ($x,$a,$b,$c,$d,$e);

Сам алгоритм фактически сводится к двум циклам, которые вынесены в отдельные функции.