There is a directed graph, you need to find all possible paths from one of its vertices to another. I found on the Internet an example of searching graphs in depth, but it’s not the path itself that is being searched for, but the number of possible paths and because of the recursion I cannot yet understand how to record the route. Therefore, I have a question, how can this be done? In the code below, a is the adjacency matrix (bool) , visited is an array of visited (bool) , n is the size of the matrix , v is the starting point , x is the final , cnt is the number of possible paths

 procedure dfs(var a:TArray; var visited: Tmas; n, v, x: integer; var cnt: integer); var i: integer; begin if v = x then begin Inc(cnt); exit; end; visited[v] := true; for i := 1 to n do begin if a[v, i] and not visited[i] then begin Route[v][i] := v; dfs(a, visited, n, i, x, cnt); end; end; visited[v] := false; end;
  • your condition x = v signals that you have reached the final vertex, and you increase cnt - the number of paths found. At this point, you have visited in Mark all the vertices that are participating in the current path. Since this is just a set of vertices, and you need it in an ordered form, you can make the visited not a boolean array, but an integer one, and number the vertices as you go. Then sorting the array in ascending order, get the path. Well, or stack can be implemented in addition to this array. - teran
  • @teran, if you store values ​​in it, then the idea of ​​checking then will not work + why sort it? - NTP
  • instead of false , you will have 0 , and instead of true (that the vertex is visited) there will be a step number of the path. naturally you will have to modify not visited[i] to visited[i] = 0 . - teran
  • Well, sorting when displaying a path, if your visited (bool) looks like [0,1,1,0,0,1] then on the way you have 2-3-5 vertices. If you start to count the depth of the recursion (steps of the path), then the array will be for example [0,2,1,0,0,3] And to output the path in the normal order 3-2-5 on the way) sorting is required. Well, you can not directly sort, it is so conditional. you need to output indices in ascending order of values - teran
  • @teran, and where to grab it? It can change several times in a cycle - NTP

1 answer 1

there is nothing to check, neither IDE nor test data is at hand. But following the results of comments, look in the following direction:

visited - integer array by the number of graph vertices. 0 - the vertex was not visited, otherwise the number is the sequence number in the path 1..M , where M din path. Enter the recursion depth z into the function parameters, this is each new step of the path.

 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;

This algorithm works in such a way that each new recursion call gives a transition to the next point in depth. When we hit the new round of recursion, earlier we just remembered that this vertex was visited. Now we are recording a number there informing that it has been visited in step z .
And when we came to the desired point, then our path was completed, and in the visited array visited we wrote down the order in which we had to pass the peaks to get here. array indices are vertices, and values ​​are the step number.

It now remains to bring the way. We know that its length is equal to the current z (i.e., how many transitions into the depth we have done). So in a cycle from 1 to z we find the corresponding value in the array. and print the vertex (index).

PS: the algorithm itself is simple as boots. If you have difficulties with recursion, then draw a simple graph on paper, draw data arrays, and with a pencil decide this algorithm on a sheet. it will quickly put everything in its place.