Homework SourseGinerva Weasley is playing with the network given below Help
Solution
C++ program to Count number of ways to reach from a source to destination. Added the comments before each line for clear understanding :-
#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 countAllPaths()
void countAllPathsUtil(int , int , bool [], int [], int &, int &);
public:
Graph(int V); // Constructor
void addEdge(int u, int v);
void countAllPaths(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.
}
// counts all paths from \'s\' to \'d\'
void Graph::countAllPaths(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;
//initialize the count;
int count = 0;
// Call the recursive helper function to count the numberf of paths
countAllPathsUtil(s, d, visited, path, path_index, count);
cout << \"\ \" << count << endl;
}
// A recursive function to count 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[]
int Graph::countAllPathsUtil(int u, int d, bool visited[],
int path[], int &path_index , int &count)
{
// 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 increment the count reference
// current path[]
if (u == d)
{
count++;
}
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])
countAllPathsUtil(*i, d, visited, path, path_index, count);
}
// 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(14);
g.addEdge(1, 2);
g.addEdge(1, 7);
g.addEdge(2, 7);
g.addEdge(2, 3);
g.addEdge(2, 8);
g.addEdge(7, 8);
g.addEdge(3, 4);
g.addEdge(3, 9);
g.addEdge(3, 8);
g.addEdge(8, 9);
g.addEdge(4, 5);
g.addEdge(9, 10);
g.addEdge(5, 10);
g.addEdge(5, 6);
g.addEdge(10, 11);
g.addEdge(6, 11);
g.addEdge(9, 12);
g.addEdge(10, 13);
g.addEdge(11, 14);
g.addEdge(12, 13);
g.addEdge(13, 14);
int s = 1, d = 14;
cout << \"The Number of different paths from \" << s
<< \" to \" << d << endl;
g.countAllPaths(s, d);
return 0;
}
You can use the above program for caculating the number of paths from any source to any destination by changing S and D in the main method. You can also use this program for any other graph directed or undirected by adding or removing edges in the Main method.
