graph data structure in python

1Graph implementation in Python 3.x using Adjacency Matrix at this link:
2  
3https://github.com/shreyasvedpathak/Data-Structure-Python/tree/master/Graph

1#This Graph implementation uses a dictionary of sets
2class Graph(dict):
3  def add(self, v) # add a vertex
4  	self[v] = set()
5  
6  def add_edge(self, u ,v): # add an edge from u to v
7    self[u].add(v)
8    self[v].add(u)
9
10G = Graph() # Create a graph called G
11for v in 'abcdefghijklm'.split():
12  G.add(v) #add each letter as a vertex
13  
14for u,v in 'ab ac ai cd fg fl km'.split():
15  G.add_edge(u,v) #add an edge from a to b, a to c, a to i and so on
16
17print(G)
18###RESULT### This is how our graph looks
19#{'a': {'i', 'b', 'c'}, 'b': {'a'}, 'c': {'d', 'a'}, 'd': {'c'}, 'e': set(), 'f': {'l', 'g'}, 'g': {'f'}, 'h': set(), 'i': {'a'}, 'j': set(), 'k': {'m'}, 'l': {'f'}, 'm': {'k'}}
20
21print("These are the neighbors of a: ", G['a'])
22###RESULT### These are the neighbors of a, replace the indexing of G to get neighbors of a different vertex
23#These are the neighbors of a: {'b', 'c', 'i'}
24
25#Perform a breadth-first search
26def breadth_first_search(G, start):
27  waiting = [start] #pick a vertex to start the search
28  found = {start}
29  
30  while len(waiting) != 0:
31    w = waiting.pop(0)
32    for x in G[w]: #This line loops through the neighbors of vertex w
33      if x not in found:
34        waiting.append(x)
35        found.add(x)
36  return found

1    def find_path(graph, start, end, path=[]):
2        path = path + [start]
3        if start == end:
4            return path
5        if not graph.has_key(start):
6            return None
7        for node in graph[start]:
8            if node not in path:
9                newpath = find_path(graph, node, end, path)
10                if newpath: return newpath
11        return None
12