не на чем проверять, нет под рукой ни IDE, ни тестовых данных. Но по итогам комментов, смотрите в следующем направлении:
visited
- целочисленный массив по числу вершин графа. 0
- вершина не посещалась, иначе число - порядковый номер в пути 1..M
, где M
дина пути. В параметры функции вводим глубину рекурсии z
, это каждый новый шаг пути.
procedure dfs(var a:TArray; var visited: Tmas; n, v, x: integer;
var cnt: integer;
z : integer = 1);
var i: integer;
procedure printPath();
var k,m : integer;
begin
for k := 1 to z do begin // количество узлов в пути
for m := 1 to n do begin // длина visited, число вершин
if visited[m] = k then begin // нашли номер шага пути
write('->', m); // номер вершины
break;
end;
end;
end;
writeln();
end;
begin
if v = x then begin // дошли в конечную точку Х
Inc(cnt); // увеличили число путей
printPath(); // напечатали путь
exit; // вернулись к предыдущему шагу пути
end;
visited[v] := z; // сейчас мы посещаем вершину v
for i := 1 to n do begin // просматриваем другие точки
if a[v, i] and // если i-я и текущая связаны
(visited[i] = 0) then begin // и i-я еще не посещалась
dfs(a, visited, n, i, x, cnt, z+1); // то идем в i-ю
end;
end;
visited[v] := 0; // возвращаемся к предыдущему шагу пути
// выходим из рекурсии,
// освобождая вершину v
end;
данный алгоритм работает таким образом, что каждый новый вызов рекурсии дает переход к следующей точке вглубь. При попадании в новый виток рекурсии, раньше мы просто запоминали, что данная вершина посещена. Теперь же мы записываем туда число, информирующее, что посещена она шаге z
.
И вот когда мы пришли в искомую точку, то наш путь завершен и в массиве visited
у записано, в каком порядке надо проходить вершины, чтобы добраться сюда. индексы массива эта вершины, а значения это номер шага.
Теперь остается вывести путь. Мы знаем, что его длина равно текущему z
(т.е. сколько переходов вглубь мы сделали). Так что циклом от 1 до z находим соответствующее значение в массиве. и выводим вершину (индекс).
зы: алгоритм сам по себе прост как валенок. Если у вас затруднения рекурсией, то нарисуйте на бумаге простенький граф, нарисуйте массивы данных, и с карандашом решите этот алгоритм на листе. это быстро все расставит на свои места.
x = v
сигнализирует что вы добрались до конечной вершины, и вы увеличиваетеcnt
- число найденных путей. В этот момент вvisited
у вас помечены все вершины, которые участвуют в текущем пути. Поскольку это просто множество вершин, а вам оно нужно в упорядоченном виде, то можетеvisited
сделать не булевым массивом, а целочисленным, и нумеровать вершины по мере прохождения. Тогда отсортировав массив по возрастанию, получите путь. Ну или стэк можете реализовать помимо этого массива. – teran 1 дек '17 в 14:53false
у вас будет0
, а вместоtrue
(что вершина посещена) будет номер шага пути. естественно придется модифицироватьnot visited[i]
вvisited[i] = 0
. – teran 1 дек '17 в 15:07[0,1,1,0,0,1]
значит в пути у вас встречаются вершины 2-3-5. Если вы начнете считать глубину рекурсии (шагов пути), то массив станет например[0,2,1,0,0,3]
И вот чтобы вывести путь в нормально порядке3-2-5
(индексы - номера вершин, значения - шаг в пути) сортировка и потребуется. Ну можно и не прямо уж сортировать, это так, условно. вам нужно вывести индексы в порядке возрастания значений – teran 1 дек '17 в 15:12