Question

in c++ and in one function please

Print All possible Paths

Implement the following member function: PrintPaths(int u, int v). This function prints all possible paths from vertex u to vertex v. Assume that the graph doesn't contain cycles.

Answer 1

Code For Above problem:

// C++ program to print all paths from a source to destination. 
#include<iostream> 
#include <list> 
using namespace std; 
  
// A directed graph using adjacency list representation 
class Graph 
{ 
    int V; // No. of vertices in graph 
    list<int> *adj; // Pointer to an array containing adjacency lists 
  
    // A recursive function used by printAllPaths() 
    void printAllPathsUtil(int , int , bool [], int [], int &); 
  
public: 
    Graph(int V); // Constructor 
    void addEdge(int u, int v); 
    void printAllPaths(int s, int d); 
}; 
  
Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 
  
void Graph::addEdge(int u, int v) 
{ 
    adj[u].push_back(v); // Add v to u’s list. 
} 
  
// 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; 
          
    } 
    else // If current vertex is not destination 
    { 
        // 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; 
} 
  
// Driver program 
int main() 
{ 
    // Create a graph given in the above diagram 
    Graph g(4); 
    g.addEdge(0, 1); 
    g.addEdge(0, 2); 
    g.addEdge(0, 3); 
    g.addEdge(2, 0); 
    g.addEdge(2, 1); 
    g.addEdge(1, 3); 
  
    int s = 2, d = 3; 
    cout << "Following are all different paths from " << s 
        << " to " << d << endl; 
    g.printAllPaths(s, d); 
  
    return 0; 
} 

Output Of Above Code:

Following are all different paths from 2 to 3
2 0 1 3 
2 0 3 
2 1 3 

Images Of Code:

10 12 20 26 117 C++ program to print all paths from a source to destination. 2 #include<iostream> 3 #include <list> 4 using namespace std; 5 6 // A directed graph using adjacency list representation 7 class Graph 8{ 9 int V; // No. of vertices in graph listint> *adj; // Pointer to an array containing adjacency lists // A recursive function used by printALlPaths() 13 void printALlPathsUtil(int , int, bool [], int [], int &); 14 15 public: 16 Graph(int V); // Constructor 17 void addEdge(int u, int v); 18 void printAllPaths(int s, int d); 19 }; 21 Graph:: Graph(int V) 22 { 23 this->V = V; 24 adj = new list int>[V]; 25} 27 void Graph::addEdge(int u, int v) 28 { 29 adj (u).push_back(v); // Add v to u's list. 30} 31 32 // Prints all paths from 's' to 'd' 33 void Graph:: printALlPaths(int u, int v) 34 { 35 // Mark all the vertices as not visited 36 bool *visited = new bool [V]; 37 38 // Create an array to store paths 39 int *path = new int[V]; 40 int path_index = 0; // Initialize path[] as empty 41 42 // Initialize all vertices as not visited 43 for (int i = 0; i < V; i++) 44 visited[i] = false; 45 46 // call the recursive helper function to print all paths 47 printALlPathsUtil(u, v, visited, path, path_index); 48} 49 50 // A recursive function to print all paths from 'u' to 'd'. 51 // visited[] keeps track of vertices in current path. 52 // path[] stores actual vertices and path_index is current

56 { 57 58 59 60 61 62 63 64 66 52 // path[] stores actual vertices and path_index is current 53 // index in path[] 54 void Graph::printALLPathsUtil(int u, int v, bool visited[], 55 int path[], int Spath_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 == v) 65 { for (int i = 0; i<path_index; i++) 67 cout << path[i] = ""; 68 cout << endl; 69 70 } 71 else // If current vertex is not destination 72 73 // Recur for all the vertices adjacent to current vertex 74 list int>::iterator i; 75 for (i = adj [u].begin(); i != adj[u].end(); Hi) 76 if (!visited["i]) 77 printAllPathsUtil*i, v, visited, path, path_index); 78 79 80 // Remove current vertex from path[] and mark it as unvisited 81 path_index--; 82 visited[u] = false; 83} 84 85 // Driver program 86 int main() // Create a graph given in the above diagram Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); 92 g.addEdge (0, 3); 93 g.addEdge (2, 0); 94 g.addEdge (2, 1); 95 g.addEdge(1, 3); 96 97 int u = 2, V = 3; 98 cout << "Following are all different paths from " « u 99 «" to " <V << endl; 100 g.printALlPaths(u, v); 101 return 0; 102 } } 87 { 88 89 90 91

Image Of Output:

apiiit-rkv@apiiitrkv-TravelMate-P243-M:-/Desktop$ 9++ AllPaths.cpp apiiit-rkv@apiiitrkv-TravelMate-P243-M :-/Desktop$ ./a.out Following are all different paths from 2 to 3 2 0 1 3 2 O 3 2 1 3