Program to trace all the paths of a directed graph from source to destination

Program to trace all the paths of a directed graph from the given source node to the destination node is discussed here. Given the adjacency representation of a directed graph, find all the paths of the graph from source to destination.

paths of a directed graph from source to destination

Algorithm to trace all the paths of a directed graph from source to destination

  • Input the adjacency list representation of the directed graph.
  • Start the traversal from the given source node.
  • Store the visited vertices in a temporary array and mark the vertices ‘visited’.
  • On reaching the destination vertex, print the temporary array.

Program to trace all the paths of a directed graph from source to destination is given below.

/* C++ program to trace all the paths of a directed graph from source to destination */

#include<iostream>
#include <list>
using namespace std;

class Graph
{
int V;
list<int> *adj;
void trace_all_paths(int , int , bool [], int [], int &);

public:
Graph(int V);
void add_edge_graph(int u, int v);
void trace_all_paths(int s, int d);
};

Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}

void Graph::add_edge_graph(int u, int v)
{
adj[u].push_back(v);
}

void Graph::trace_all_paths(int s, int d)
{
bool *visited = new bool[V];

int *path = new int[V];
int path_index = 0;

for (int i = 0; i < V; i++)
visited[i] = false;

trace_all_paths(s, d, visited, path, path_index);
}

void Graph::trace_all_paths(int u, int d, bool visited[], int path[], int &path_index)
{
visited[u] = true;
path[path_index] = u;
path_index++;

if (u == d)
{
for (int i = 0; i<path_index; i++)
cout << path[i] << ” “;
cout << endl;

}
else
{
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (!visited[*i])
trace_all_paths(*i, d, visited, path, path_index);
}

path_index–;
visited[u] = false;
}

int main()
{
Graph g(4);
char choice;
int u, v;
/*g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(2, 0);
g.addEdge(2, 1);
g.addEdge(1, 3); */
cout << “\nEnter the connections of the nodes in the graph \n”;
do
{
cin >> u >> v;
cin >> choice;
g.add_edge_graph(u, v); /* Enter the vertex connection */
}while(choice == ‘y’ || choice == ‘Y’); /* If you want to continue */

int source, destination;
cout <<“\nEnter the source node : “;
cin >> source;
cout << endl;

cout << “\nEnter the destination node : “;
cin >> destination;
cout << endl;
cout << “\nDifferent paths from ” << source << ” to ” << destination << endl;
g.trace_all_paths(source, destination);

return 0;
}

Click edit button to change this text. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.