Count paths between two vertices in un-directed graph

Count paths for a a given graph G has simple path from source s to destination d. Assume that graph is represented using adjacent matrix.

Solution:

• Use DFS
• When we explored all neighbours of a unvisited vertex then we set visited of that vertex to false so, that we ca n use for next iteration

Algorithm:

1.  Set count = 0
2. Create boolean visited matrix for each vertex of graph G
3. Call Count_Path function
4. In count_path function
   1. Set visited of source_vertex to true
   2. If source_vertex == destination_vertex then
      1. Increment vertext counter
      2. Set visited of destination_vertex to false
   3. Explore all adjacent_vertices of sources_vertex
   4. If adjacent_vertex is not visited then
      1. Call count_path recursively with adjacent_vertex as sources vertex
      2. After exploring all neighbours of adjacent_vertex set visited of this vertex to false

Latest Source Code:
Github: GraphPathFinder.java

Output:

 
 -   T   T   T   -  
 T   -   -   T   -  
 T   -   -   T   -  
 T   T   T   -   T  
 -   -   -   T   -  
Path Count between 0 to 5 are: 3