Checking if 2 nodes on a graph are connected recursively C#-CodePudding

I'm trying to create a simple implementation of Depth-First Search recursively.

Here is the graph I've set up, searching for a path between Node 1 and Node 5:

int[][] graph = new int[5][];
graph[0] = new int[] { 1, 2 };
graph[1] = new int[] { 1, 3 };
graph[2] = new int[] { 2, 4 };
graph[3] = new int[] { 3, 4 };
graph[4] = new int[] { 4, 5 };

if (FindNode(graph, 1, 5))
{
    //Success
}

Node 1 is connected to Nodes 2 and 3, Node 2 to Node 4, Node 3 to Node 4, and Node 4 to 5.

Here is the recursion method:

public static Boolean FindNode(int[][] graph, int start, int end)
{
    if (start == end)
    {
        return true;
    }
    for (int i = 0; i < graph.Length; i  )
    {
        if (graph[i][0] == start)
        {
            start = graph[i][1];
            if (FindNode(graph, start, end))
            {
                return true;
            }
        }
    }
    return false;
}

Essentially it's looking for the starting value in the 'left column' of the graph data, and then changes the starting node to be its associated node.

The code works as intended for this graph example (i.e. it finds the path 1 -> 2 -> 4 -> 5), but when it has to go back up the recursive loop it can't find the solution (e.g. if graph[4] was {3,5}).

I'm not too familiar with recursion so I'm not sure how to fix it.

I'm not too concerned about optimising it to ignore previously visited nodes.

I would like to return the path as a list (e.g. 1,2,4,5).

Thanks

CodePudding user response：

The logic in your answer is correct but displaying the path would require you to push the successful links onto a stack or onto the beginning of a list.

If you can only add to the end of a list (as is the case with trying to just Console.WriteLine each step) then you can do this without remembering (or returning) the path, but you have to be clever by building path in reverse order. (find the last step of the chain first)

If you have a link from n -> end, and there is a path from start -> n. Then you can display the link from n -> end. In so determining that there is a path from start -> n, you will have displayed all those links already.

using System;

class Program
{
    public static Boolean FindNode(int[][] graph, int start, int end)
    {
        if (start == end) {
            return true;
        }
        for (int i = 0; i < graph.Length; i  ) {
            if (graph[i][1] == end) {
                if (FindNode(graph, start, graph[i][0])) {
                    Console.WriteLine("{0} -> {1}", graph[i][0], end);
                    return true;
                }
            }
        }
        return false;
    }
    static void Main(string[] args)
    {
        int[][] graph = new int[5][];
        graph[0] = new int[] { 1, 2 };
        graph[1] = new int[] { 1, 3 };
        graph[2] = new int[] { 2, 4 };
        graph[3] = new int[] { 3, 4 };
        graph[4] = new int[] { 4, 5 };

        if (FindNode(graph, 1, 5)) {
            //Success
        }
    }
}