bfs python

1graph = {
2  'A' : ['B','C'],
3  'B' : ['D', 'E'],
4  'C' : ['F'],
5  'D' : [],
6  'E' : ['F'],
7  'F' : []
8}
9
10visited = [] # List to keep track of visited nodes.
11queue = []     #Initialize a queue
12
13def bfs(visited, graph, node):
14  visited.append(node)
15  queue.append(node)
16
17  while queue:
18    s = queue.pop(0) 
19    print (s, end = " ") 
20
21    for neighbour in graph[s]:
22      if neighbour not in visited:
23        visited.append(neighbour)
24        queue.append(neighbour)
25
26# Driver Code
27bfs(visited, graph, 'A')

1graph = {
2  '5' : ['3','7'],
3  '3' : ['2', '4'],
4  '7' : ['8'],
5  '2' : [],
6  '4' : ['8'],
7  '8' : []
8}
9
10visited = [] # List for visited nodes.
11queue = []     #Initialize a queue
12
13def bfs(visited, graph, node): #function for BFS
14  visited.append(node)
15  queue.append(node)
16
17  while queue:          # Creating loop to visit each node
18    m = queue.pop(0) 
19    print (m, end = " ") 
20
21    for neighbour in graph[m]:
22      if neighbour not in visited:
23        visited.append(neighbour)
24        queue.append(neighbour)
25
26# Driver Code
27print("Following is the Breadth-First Search")
28bfs(visited, graph, '5')    # function calling
29

1class Graph:
2    def __init__(self):
3        # dictionary containing keys that map to the corresponding vertex object
4        self.vertices = {}
5 
6    def add_vertex(self, key):
7        """Add a vertex with the given key to the graph."""
8        vertex = Vertex(key)
9        self.vertices[key] = vertex
10 
11    def get_vertex(self, key):
12        """Return vertex object with the corresponding key."""
13        return self.vertices[key]
14 
15    def __contains__(self, key):
16        return key in self.vertices
17 
18    def add_edge(self, src_key, dest_key, weight=1):
19        """Add edge from src_key to dest_key with given weight."""
20        self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)
21 
22    def does_edge_exist(self, src_key, dest_key):
23        """Return True if there is an edge from src_key to dest_key."""
24        return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])
25 
26    def __iter__(self):
27        return iter(self.vertices.values())
28 
29 
30class Vertex:
31    def __init__(self, key):
32        self.key = key
33        self.points_to = {}
34 
35    def get_key(self):
36        """Return key corresponding to this vertex object."""
37        return self.key
38 
39    def add_neighbour(self, dest, weight):
40        """Make this vertex point to dest with given edge weight."""
41        self.points_to[dest] = weight
42 
43    def get_neighbours(self):
44        """Return all vertices pointed to by this vertex."""
45        return self.points_to.keys()
46 
47    def get_weight(self, dest):
48        """Get weight of edge from this vertex to dest."""
49        return self.points_to[dest]
50 
51    def does_it_point_to(self, dest):
52        """Return True if this vertex points to dest."""
53        return dest in self.points_to
54 
55 
56class Queue:
57    def __init__(self):
58        self.items = []
59 
60    def is_empty(self):
61        return self.items == []
62 
63    def enqueue(self, data):
64        self.items.append(data)
65 
66    def dequeue(self):
67        return self.items.pop(0)
68 
69 
70def display_bfs(vertex):
71    """Display BFS Traversal starting at vertex."""
72    visited = set()
73    q = Queue()
74    q.enqueue(vertex)
75    visited.add(vertex)
76    while not q.is_empty():
77        current = q.dequeue()
78        print(current.get_key(), end=' ')
79        for dest in current.get_neighbours():
80            if dest not in visited:
81                visited.add(dest)
82                q.enqueue(dest)
83 
84 
85g = Graph()
86print('Menu')
87print('add vertex <key>')
88print('add edge <src> <dest>')
89print('bfs <vertex key>')
90print('display')
91print('quit')
92 
93while True:
94    do = input('What would you like to do? ').split()
95 
96    operation = do[0]
97    if operation == 'add':
98        suboperation = do[1]
99        if suboperation == 'vertex':
100            key = int(do[2])
101            if key not in g:
102                g.add_vertex(key)
103            else:
104                print('Vertex already exists.')
105        elif suboperation == 'edge':
106            src = int(do[2])
107            dest = int(do[3])
108            if src not in g:
109                print('Vertex {} does not exist.'.format(src))
110            elif dest not in g:
111                print('Vertex {} does not exist.'.format(dest))
112            else:
113                if not g.does_edge_exist(src, dest):
114                    g.add_edge(src, dest)
115                else:
116                    print('Edge already exists.')
117 
118    elif operation == 'bfs':
119        key = int(do[1])
120        print('Breadth-first Traversal: ', end='')
121        vertex = g.get_vertex(key)
122        display_bfs(vertex)
123        print()
124 
125    elif operation == 'display':
126        print('Vertices: ', end='')
127        for v in g:
128            print(v.get_key(), end=' ')
129        print()
130 
131        print('Edges: ')
132        for v in g:
133            for dest in v.get_neighbours():
134                w = v.get_weight(dest)
135                print('(src={}, dest={}, weight={}) '.format(v.get_key(),
136                                                             dest.get_key(), w))
137        print()
138 
139    elif operation == 'quit':
140        break

1# tree level-by-level traversal. O(n) time/space
2def breadthFirstSearch(root):
3    q = [root]
4
5    while q:
6        current = q.pop(0)
7        print(current)
8        if current.left is not None: q.append(current.left)
9        if current.right is not None: q.append(current.right)