Skip to main content

Posts

Showing posts from July, 2018

Find all the existing paths in graph from source to destination node - BFS and DFS

#!/usr/bin/env python import collections graph = {'A': ['B', 'C'],              'B': ['C', 'D'],              'C': ['D'],              'D': ['C'],              'E': ['F'],              'F': ['C']} #Using DFS algorithm #Ref -   https://www.python.org/doc/essays/graphs/ def find_all_paths_dfs(graph, start, end, path = []):   path = path + [start]   #Reachd end return path   if start == end:         return [path]   #No path found found   if not graph.has_key(start):         return []   paths = []   for node in graph[start]:     if node not in path:       new_paths = find_all_paths_dfs(graph, node, end, path)       for new_path in new_paths:         paths.append(new_path)   return paths #Using BFS #Reference - http://code.activestate.com/recipes/576675/ def find_all_paths_bfs(graph, start,