Implement a graph in Python Question : Build a graph in python, given its edge representation.

from collections import defaultdict

graph = { '1' : ['2' ,'4','5'],
          '2' : ['3'] ,
          '3' : ['5'] ,
          '4' : ['2']
          }

def generate_edges(graph):
    edges = []

    for node in graph:
        for next_node in graph[node]:
            #if edge exist than append
            edges.append((node,next_node))
    return edges


def find_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path

        for node in graph[start]:
            if node not in path:
                newpath = find_path(graph, node, end, path)
                if newpath:
                    return newpath
        return None


print generate_edges(graph)

print find_path(graph, '1','5')


How can i improve this code?
find_path is very inefficient. Consider the following example, where we try to find a short path (just one edge) in a graph with just eleven nodes:

&gt;&gt;&gt; G = {i: list(range(10)) for i in range(10)}
&gt;&gt;&gt; G[0].append(10)
&gt;&gt;&gt; find_path(G, 0, 10)
[0, 10]


How long does this take?

&gt;&gt;&gt; from timeit import timeit
&gt;&gt;&gt; timeit(lambda:find_path(G, 0, 10), number=1)
1.3475657280068845


It really shouldn't take more than a second to find a path with a single edge in such a small graph. So why does it take so long?

The way that find_path works is that it generates all simple paths (paths with no repeated nodes) in depth-first order. However, in general there can be exponentially many simple paths in a graph. I constructed the graph G so that it looks like this:



The depth-first search starts by finding the path 0–1–2–3–4–5–6–7–8–9 but then it reaches a dead end:



So the search backtracks a couple of steps and then finds the path 0–1–2–3–4–5–6–7–9–8, but again it reaches a dead end:



You can see that the search will have to visit every path starting with 0 and visiting all of 1 to 9, before it will consider the path 0–10. But there are \$9! = 362,880\$ such paths.

To avoid this exponential runtime, you'll have to use a different approach, for example Dijkstra's algorithm.