GeeksforGeeks - Print all paths from a given source to a destination

GeeksforGeeks - Print all paths from a given source to a destination

Given a directed graph, a source vertex ‘s’ and a destination vertex ‘d’, print all paths from given ‘s’ to ‘d’.

The idea is to do Depth First Traversal of given directed graph. Start the traversal from source. Keep storing the visited vertices in an array say ‘path[]’. If we reach the destination vertex, print contents of path[]. The important thing is to mark current vertices in path[] as visited also, so that the traversal doesn’t go in a cycle.

class Graph

{

   int V;    // No. of vertices in graph

   list<int> *adj; // Pointer to an array containing adjacency lists

// Prints all paths from 's' to 'd'

void Graph::printAllPaths(int s, int d)

{

    // Mark all the vertices as not visited

    bool *visited = new bool[V];

 

    // Create an array to store paths

    int *path = new int[V];

    int path_index = 0; // Initialize path[] as empty

 

    // Initialize all vertices as not visited

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

        visited[i] = false;

 

    // Call the recursive helper function to print all paths

    printAllPathsUtil(s, d, visited, path, path_index);

}

 

// A recursive function to print all paths from 'u' to 'd'.

// visited[] keeps track of vertices in current path.

// path[] stores actual vertices and path_index is current

// index in path[]

void Graph::printAllPathsUtil(int u, int d, bool visited[],

                              int path[], int &path_index)

{

    // Mark the current node and store it in path[]

    visited[u] = true;

    path[path_index] = u;

    path_index++;

 

    // If current vertex is same as destination, then print

    // current path[]

    if (u == d)

    {

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

           cout << path[i] << " ";

       cout << endl;

    }

 

    // Recur for all the vertices adjacent to current vertex

    list<int>::iterator i;

    for (i = adj[u].begin(); i != adj[u].end(); ++i)

        if (!visited[*i])

            printAllPathsUtil(*i, d, visited, path, path_index);

 

    // Remove current vertex from path[] and mark it as unvisited

    path_index--;

    visited[u] = false;

}




}

GeeksforGeeks - Print all paths from a given source to a destination