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, end):

  nodes = collections.deque()

  nodes.append([start])

  all_possible_paths = []

  while nodes:

    previous_path = nodes.popleft()

    last_node = previous_path[-1]

    #Reached path, append it to all_paths

    if last_node == end:

      all_possible_paths.append(previous_path)

    for node in graph[last_node]:

      if node not in previous_path:

        new_path = previous_path + [node]

        nodes.append(new_path)

  return all_possible_paths

    

res = find_all_paths_dfs(graph, 'A', 'D', path = [])

print 'All paths from(A->D) with DFS->', res

res = find_all_paths_bfs(graph, 'A', 'D')

print 'All paths with (A->D) BFS->', res

Output - 
--------

All paths from(A->D) with DFS-> [['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']]

All paths with (A->D) BFS-> [['A', 'B', 'D'], ['A', 'C', 'D'], ['A', 'B', 'C', 'D']]