Given the directed, connected and unweighted graph G, and the task to find the number of all paths possible between two given vertices.
Note: The path does not contain any cycle which means path have finite number of vertices.
The idea is to use backtracking. Traverse the path from the source node and check if path leads to destination node then increment the count and backtrack to other path.
Count_Path_Recur(u, Destination, Check_Node_Visited, Path_Count): u <- make it visited if u is equal to Destination Path_Count += 1 otherwise i = 0 while i < len(Graph[u]): if not Check_Node_Visited[Graph[u][i]]: // Recursive calling Count_Path_Recur(Graph[u][i], Destination, Check_Node_Visited, Path_Count) i += 1 u <- make it unvisited
Implementation in Python
# Implementation Graph =  V= 0 def gragh_add(x): global Graph, V V=x Graph = [ for i in range(V)] def addEdge(u, v): # Add v to u’s list. global Graph Graph[u].append(v) # 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 def countPathsUtil(u, d, visited, Path_Count): global Graph, V visited[u] = True # If current vertex is same as # destination, then increment count if (u == d): Path_Count += 1 # If current vertex is not destination else: # Recur for all the vertices # adjacent to current vertex i = 0 while i < len(Graph[u]): if (not visited[Graph[u][i]]): countPathsUtil(Graph[u][i], d, visited, Path_Count) i += 1 visited[u] = False # Returns count of paths from 's' to 'd' def Count_Path(s, d): global V # Mark all the vertices # as not visited visited = [False] * V # Call the recursive helper # function to print all paths Path_Count =  countPathsUtil(s, d, visited, Path_Count) return Path_Count # Driver Code if __name__ == '__main__': # Create a graph given in the # above diagram gragh_add(4) addEdge(0, 1) addEdge(0, 2) addEdge(0, 3) addEdge(1, 3) addEdge(2, 1) addEdge(2, 3) s = 0 d = 3 print(Count_Path(s, d))