Print All Paths
You are given a graph with ‘N’ nodes and ‘M’ unidirectional edges. Also you are given two integers ‘S’ and ‘D’ denoting the source and destination. Your task is to find all the paths from ‘S’ to ‘D’.

Note: An ordered set of nodes { S, u1, u2...un, D} is a valid path between ‘S’ and ‘D’, if all nodes along the path are unique.

For example:

For given N = 4, M = 4, S = 0 and D =3.

In the above example, the path 0 - 1 - 3 is a valid path as all nodes along the path are unique and the path 0 - 1 - 2 - 1 - 3 is not a valid path because node 1 is visited twice.

Input Format:

The first line contains one positive integer ‘T’, denoting the number of test cases, then ‘T’ test cases follows. The first line of each test case contains two integers ‘N’ and ‘M’, denoting the number of nodes and the number of edges. The next ‘M’ lines of each test case contains two space-separated integers ’u’ and ‘v’, denoting the edge between ‘u’ and ‘v’. The last line of each test case contains two integers ‘S’ and ‘D’ denoting the source and destination.

Output Format:

The first line of each test case contains an integer ‘N’ , denoting the number of valid paths from ‘S’ to ‘D’. The next ‘N’ line of each test case contains the all nodes from ‘S’ to ‘D’ along the ‘ith’ path where 1

Question

Print All Paths

You are given a graph with ‘N’ nodes and ‘M’ unidirectional edges. Also you are given two integers ‘S’ and ‘D’ denoting the source and destination. Your task is to find all the paths from ‘S’ to ‘D’.

Note: An ordered set of nodes { S, u1, u2...un, D} is a valid path between ‘S’ and ‘D’, if all nodes along the path are unique.

For example:

For given N = 4, M = 4, S = 0 and D =3.

In the above example, the path 0 -> 1 - > 3 is a valid path as all nodes along the path are unique and the path 0 -> 1 -> 2 -> 1 -> 3 is not a valid path because node 1 is visited twice.

Input Format:

The first line contains one positive integer ‘T’, denoting the number of test cases, then ‘T’ test cases follows.

The first line of each test case contains two integers ‘N’ and  ‘M’, denoting the number of nodes and the number of edges.

The next ‘M’ lines of each test case contains two space-separated integers ’u’ and ‘v’, denoting the edge between ‘u’ and ‘v’.

The last line of each test case contains two integers ‘S’ and ‘D’ denoting the source and destination.

Output Format:

The first line of each test case contains an integer ‘N’ , denoting the number of valid paths from ‘S’ to ‘D’.

The next ‘N’ line of each test case contains the all nodes from ‘S’ to ‘D’ along the ‘ith’ path where 1 <= i <= N. 

If there are more than one path then the ith path should be lexicographically smaller than (i + 1) path.

Output of each test case will be printed on a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 5
1 <= M <= 10
0 <= u, v , S, D <= N - 1 

Time Limit: 1 sec.

Accepted Answer

1. In this approach we will use BFS (breadth first search) to find all possible paths.

2. We will make a queue which contains the following information :

a) Vector that stores the path up to a certain cell.

b) coordinates of the cell.

3. We will start from the top-left cell and push cell value and coordinates in the queue.

4. We will keep on exploring right and down cell (if possible) until queue is not empty

and push them in the queue by updating the current cell vector.

5. If we reach the last cell then we have got one answer and we will print the answer vector.

Accepted Answer

Backtracking

The idea is very simple: we will perform dfs from a given source node and try out all possible paths using the backtracking concept.

The steps are as follows:

Let ‘allAllPaths(n, m, edges, src, des)’ be the function that returns a 2D array that contains all the possible paths.

Take the following variables: 2D array ‘Graph’, to store graphs and ‘Visited’ array to mark each node whether it is visited or not.
Clear graph, initialize the visited array to false.
Run a loop from 0 to 'm' :
- Add the undirected edge between edges[i] [0] and edges[i][1].
Take an 2D array 'allPaths' to store the answer.
Take an array 'currPath' to store the current path.
Push ‘src’ in ‘currPath’ and mark visited[src] equal to true.
Make a dfs(n, allPaths, currPath, src, des, graph, visited) and call the dfs function.
Return ‘allPaths’.

Description of dfs(n, allPaths, currPath, src, des, graph, visited) function

If ‘src’ is equal to ‘des’
- Push ‘currPath’ in ‘allPath’ and return.
Run a loop from 0 to ‘n’:
- If graph[src][i] is equal to 1 and visited[i] == 0.
  - Make visited[i] equal to 1.
  - Push ‘i’ in ‘currPath’ i.e currPath.push_back(i).
  - Recursively call dfs on adjacent nodes ‘i’ i.e dfs(n, ‘allPaths’, ‘currPath’, i, des, graph, visited).
  - Remove the ‘i’th node from currPath i.e currPath.pop_back().
  - Make visited[i] equal to 0.

Space Complexity: O(n^n)Explanation:

O(N ^ N), where ‘N’ is the number of vertices.

To store the paths ( N ^ N) space is needed. Hence the space complexity is O( N ^ N).

Time Complexity: O(n^n)Explanation:

O(N ^ N), where ‘N’ is the number of vertices.

The time complexity is exponential. From each vertex there are ‘N’ vertices that can be visited from the current vertex.

Java (SE 1.8)

/*

    Time Complexity : O(N ^ N)

    Space Complexity: O(N ^ N)



    Where 'N' is the number of nodes.

*/





import java.util.ArrayList;

import java.util.Arrays;

import java.util.LinkedList;



public class Solution {



    private static ArrayList> allPaths;

    private static LinkedList currPath;

    private static int[][] graph;

    private static boolean[] visited ;



    // Utility function that returns the number of nodes in a component

    private static void dfs(int n , int src, int des) {

        // Base case

        if (src == des) {

            // Push 'currPath' in 'allPath' and return.

            allPaths.add(new ArrayList(currPath));

            return ;

        }



        // Run a loop from 0 to 'n':

        for (int i = 0; i < n; i++) {



            // If graph[src][i] is equal to 1 and visited[i] == 0.

            if (graph[src][i] == 1 && visited[i] == false) {



                // Make visited[i] equal to 1.

                visited[i] = true;



                // Push 'i' in currPath.

                currPath.add(i);



                // Recursively call dfs on adjacent nodes 'i' i.e dfs(n, allPaths, currPath, i, des).

                dfs(n, i, des);



                // Remove the 'i' node from currPath.

                currPath.pollLast();



                // Make visited[i] equal to 0.

                visited[i] = false;

            }

        }



        return;

    }



    public static ArrayList> printAllPaths(int n, int m, ArrayList> edges, int s, int d) {

        graph = new int[n][n];

        visited = new boolean[n];



        Arrays.fill(visited, false);



        for (int i = 0; i < n; i++) {

            Arrays.fill(graph[i], 0);

        }



        // Run a loop from 0 to 'm'

        for (int i = 0; i < m ; i++) {

            int u = edges.get(i).get(0);

            int v = edges.get(i).get(1);



            // Add edge u - v in graph

            graph[u][v] = 1;

            graph[v][u] = 1;

        }



        // Take an 2D array 'allPaths' to store the answer.

        allPaths = new ArrayList>();



        // Take an array 'currPath' to store the current path.

        currPath = new LinkedList();

        // Push 'src' in 'currPath' and mark visited[src] equal to true.

        currPath.add(s);

        visited[s] = true;



        // Call the dfs function.

        dfs(n, s, d);



        // Return 'allPaths'.

        return allPaths;



    }

}

Python (3.5)

'''

Time Complexity : O(N ^ N)

    Space Complexity: O(N ^ N)



    Where 'N' is the number of nodes.

'''





from copy import deepcopy





def dfs(n, allPaths, currPath, src, des, graph, visited):

    # base case

    if src == des:

        # Push 'currPath' in 'allPath' and return.

        allPaths.append(deepcopy(currPath))

        return



    # Run a loop from 0 to 'n':

    for i in range(n):

        # If graph[src][i] is equal to 1 and visited[i] == 0.

        if graph[src][i] == 1 and visited[i] == False:



            visited[i] = True



            # Push 'i' in currPath.

            currPath.append(i)



            # Recursively call dfs on adjacent nodes 'i' i.e dfs(n, allPaths, currPath, i, des).

            dfs(n, allPaths, currPath, i, des, graph, visited)



            currPath.pop()



            visited[i] = False

    return





def printAllpaths(n, m, edges, s, d):

    graph = [[0 for i in range(n)] for j in range(n)]



    visited = [False for i in range(n)]



    for i in range(m):

        u = edges[i][0]

        v = edges[i][1]



        graph[u][v] = 1

        graph[v][u] = 1



    # Take an 2D array 'allPaths' to store the answer.

    allPaths = []

    # Take an array 'currPath' to store the current path.

    currPath = []



    #  Push 'src' in 'currPath' and mark visited[src] equal to true.

    currPath.append(s)

    visited[s] = True



    # Call the dfs function.

    dfs(n, allPaths, currPath, s, d, graph, visited)

    # Return 'allPaths'.

    return allPaths

C++ (g++ 5.4)



/*

    Time Complexity : O(N ^ N)

    Space Complexity: O(N ^ N)



    Where ‘N’ is the number of nodes.

*/



// Utilityb function that finds all the paths

void dfs(int n, vector< vector > & allPaths, vector & currPath, int src, int des, vector< vector > &graph, vector< int > &visited )

{

    // Base case

    if(src == des)

    {

        // Push ‘currPath’ in ‘allPath’ and return.

        allPaths.push_back(currPath);

        return ;

    }



    // Run a loop from 0 to ‘n’:

    for(int i = 0; i < n; i++)

    {

        // If graph[src][i] is equal to 1 and visited[i] == 0.

        if(graph[src][i] == 1 && visited[i] == 0)

        {

            // Make visited[i] equal to 1.

            visited[i] = 1;



            // Push ‘i’ in currPath i.e currPath.push_back(i).

            currPath.push_back(i);



            // Recursively call dfs on adjacent nodes ‘i’ i.e dfs(n, allPaths, currPath, i, des).

            dfs(n, allPaths, currPath, i, des, graph, visited);

            

            // Remove the ‘i’th node from currPath i.e currPath.pop_back().

            currPath.pop_back();



            // Make visited[i] equal to 0.

            visited[i] = 0;

        }

    }



    return;

}



void init(int n, vector< vector > &graph, vector< int > &visited)

{

    graph.resize(n);

    visited.clear();

    visited.resize(n);



    for(int i = 0; i < n; i++)

    {

        graph[i].clear();

        graph[i].resize(n);

    }

}



vector< vector > printAllPaths(int n, int m, vector< vector > & edges, int s, int d)

{

    vector< vector > graph;

    vector< int > visited;



    // Clear graph, initialize the visited array to false.

    init(n, graph, visited);



    // Run a loop from 0 to 'm' 

    for(int i = 0; i < m; i++)

    {

        int u = edges[i][0];

        int v = edges[i][1];



        // Add the undirected edge between edges[i] [0] and edges[i][1].

        graph[u][v] = 1;

        graph[v][u] = 1;

    }

    // Take an 2D array 'allPaths' to store the answer.

    vector< vector > allPaths;



    // Take an array 'currPath' to store the current path.

    vector currPath;



    // Push ‘src’ in ‘currPath’ and mark visited[src] equal to true.

    currPath.push_back(s);

    visited[s] = 1;



    // Call the dfs function.    

    dfs(n, allPaths, currPath, s, d, graph, visited);



    // Return ‘allPaths’.

    return allPaths;

}