Finding all routes of a C# graph?

Question

C++ / C#

There is a graph described by a matrix

0 1 1 1 0 0 0
1 0 0 0 0 0 0
1 0 0 1 0 0 1
1 0 1 0 0 1 0
0 0 0 0 0 1 1
0 0 0 1 1 0 1
0 0 1 0 1 1 0

It is necessary to build all the routes to the vertex x from the vertex v

Here is what I wrote

private void dfs(int[][] a, ref bool[] visited, int n, int v, int x, ref int cnt, ref List<List<int>> p, ref List<int> r)
            {
                if (v == x)
                {
                    cnt++;
                    r.Add(x + 1);
                    p.Add(r);
                    r = new List<int>();
                    return;
                }
                visited[v] = true;
                r.Add(v + 1);
                for (int i = 0; i < n; i++)
                {
                    if (a[v][i] == 1 && !visited[i])
                    {
                        dfs(a, ref visited, n, i, x, ref cnt, ref p, ref r);
                    }
                }
                visited[v] = false;
                r.Remove(v + 1);
            }

here a - graph matrix, visited - array of visited vertices, v - start vertex, x - end vertex, cnt - number of routes, p - list of routes, r - current route

But it doesn't work correctly, tell me how to fix it.

Answer 1

Here is the modified algorithm, it works correctly.

private void findRoute(int[][] a, int v, int dest, int n, bool[] visited, string route)
    {
        if (v == dest)
        {
            richTextBox1.Text += route + "\n";
        }
        else
        {
            visited[v] = true;
            for (int i = 0; i < n; i++)
            {
                if (a[v][i] == 1 && !visited[i])
                {
                    findRoute(a, i, dest, n, visited, route + (i+1) + " ");
                }
            }
            visited[v] = false;
        }
    }

Answer 2

In my opinion, your recursion is not organized correctly. The point is that r is passed by reference to all search branches. And if one of these branches succeeds, r is set to zero, thus discarding the competing paths. In addition, in the search loop, r should also always contain the same thing (i.e. the path to the current top v. But in your code this is not the case, because r will change inside the recursive call.
I'm not sure if everything else is correct, but I would change:

dfs(a, ref visited, n, i, x, ref cnt, ref p, ref r);

on the

dfs(a, ref visited, n, i, x, ref cnt, ref p,  r.ToArray());

And accordingly, ref would be removed from the definition of dfs. So when going through all the vertices of the paths in the loop, a copy of r will be created for each path . Also in this case you don't need r.Remove(v + 1); and r = new List();
In general, passing a large number of arguments by reference is not a very good solution from an architectural point of view. You should think about how to organize the code so that the recursive function is "pure" - that is, calling it with the same parameters would always lead to the same result. The ability to write in this style greatly reduces the likelihood of error.
Update:
At the request of Michail7, here is my solution:

class Program
    {

        public  struct Path {
            public  List<int> Vertexes { readonly get;  private set; } 
            
            public Path(int vertex) {
                this.Vertexes = new List<int>();
                this.Vertexes.Add(vertex);
            }

            public Path(List<int> vertexes, int vertex) {
                if (vertexes != null) {
                    this.Vertexes = new List<int>(vertexes);
                }
                else {
                    this.Vertexes = new List<int>();
                }
                this.Vertexes.Add(vertex);
            }

            public Path Add(int vertex) {
                Path p = new Path(this.Vertexes, vertex);
                return p;
            }

            public bool hasVertex(int vertex) {
                return Vertexes.Contains(vertex);
            }

            public int LastVertex() {
                return Vertexes.Last();
            }
        }

        public static List<Path> RunDfs(in  int[,] graph, int n, in Path currentPath, int targetVertex) {
            int currentVertex = currentPath.LastVertex();
            if (currentVertex == targetVertex) {
                return new List<Path> { currentPath };
            }
            else {
                List<Path> result = new List<Path>();
                for (int i = 0; i < n; i++) {
                    if (graph[currentVertex,i] == 1 && ! currentPath.hasVertex(i) ) {
                        List<Path> newPaths = RunDfs(graph, n, currentPath.Add(i), targetVertex );
                        result.AddRange(newPaths);
                    }
                }
                return result;
            }
        }

        static void Main(string[] args) {
            int[,] graph =  { {0,1,1,0},{0,0,0,1},{0,1,0,0}, {0,0,0,0}};
            Path curPath = new Path().Add(0);
            List<Path> paths = RunDfs(graph, 4,  curPath, 3);
            Console.WriteLine("Hello World!");
        }

Его наверняка можно улучшить. И не факт, что он по скорости выиграет. Но. В нём сведено к миниму количество параметров и метод RunDfs является "чистым" в том понятии, что для одинакового входа он всегда выдаёт тот же выход и не имеет сайд-эффектов в виде записи в передаваемые структуры. Единственное, что я не стал оптимизировать - это передачу графа в виде двумерного массива. Очевидно для настоящих больших графов так оставлять нельзя, т к есть вероятность, что компиллятор всё же решит его копировать по значению, несмотря на то, что запись внутри RunDfs в него не происходит. (Это наверное можно проверить, делая бенчмарки по времени на графе достаточного размера и сравнив версию, где граф передаётся через ref) Но правильнее и проще для графа также ввести какую то структуру или даже класс, который будет передаваться по ссылке, но при этом не будет давать себя менять.