Solution: Find All Paths Between Two Nodes

class Program
{
    /// <summary>
    /// Finds all paths between the source and destination in a given graph.
    /// </summary>
    /// <param name="graph">A directed graph.</param>
    /// <param name="source">Source vertex.</param>
    /// <param name="destination">Destination vertex.</param>
    /// <param name="visited">A list to mark visited vertices.</param>
    /// <param name="path">List to store one path to source from destination.</param>
    /// <param name="paths">2D list to store all paths.</param>
    static void FindAllPathsRecursive(Graph graph, int source, int destination, bool[] visited, List<int> path, List<List<int>> paths)
    {
        // Mark the current node as visited and store in path
        visited[source] = true;
        path.Add(source);
        //  If current vertex is same as destination, then print
        // stores the current path in 2D list (Deep copy)
        if (source == destination)
        {
            paths.Add(new List<int>(path));
        }
        else
        {
            // If current vertex is not destination
            // Recur for all the vertices adjacent to this vertex
            AdjNode temp = graph.graph[source];
            while (temp != null)
            {
                int i = temp.Vertex;
                if (!visited[i])
                {
                    FindAllPathsRecursive(graph, i, destination, visited, path, paths);
                }
                temp = temp.Next;
            }
        }
        // Remove current vertex from path[] and mark it as unvisited
        path.RemoveAt(path.Count - 1);
        visited[source] = false;
    }
    /// <summary>
    /// Finds all paths between the source and destination in a given graph.
    /// </summary>
    /// <param name="graph">A directed graph.</param>
    /// <param name="source">Source vertex.</param>
    /// <param name="destination">Destination vertex.</param>
    public static List<List<int>> FindAllPaths(Graph graph, int source, int destination)
    {
        // Mark all the vertices as not visited
        bool[] visited = new bool[graph.V];
        List<List<int>> paths = new List<List<int>>();
        List<int> path = new List<int>();
        // Create a list to store paths
        FindAllPathsRecursive(graph, source, destination, visited, path, paths);
        return paths;
    }
    // Main program to test above function
    static void Main(string[] args)
    {
        Graph g = new Graph(6);
        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 3);
        g.AddEdge(1, 4);
        g.AddEdge(3, 5);
        g.AddEdge(4, 5);
        g.AddEdge(2, 5);
        int source = 0;
        int destination = 5;
        List<List<int>> paths = FindAllPaths(g, source, destination);
        var sb = new System.Text.StringBuilder("[");
        for (var i = 0; i < paths.Count; i++)
        {
            sb.Append("[" + string.Join(", ", paths[i]) + "]");
            if (i < paths.Count - 1)
                sb.Append(", ");
        }
        sb.Append("]");
        Console.WriteLine(sb.ToString());
    }
}