Merge pull request #41 from anish03/bfs

abranhe · web-flow · commit 7698ca1da136 · 2018-10-04T15:49:07.000-04:00
Added python implementation for breadth first search
diff --git a/graphs/breadth_first_search.py b/graphs/breadth_first_search.py
@@ -0,0 +1,40 @@
+# Breadth First Search
+
+from collections import defaultdict
+
+class Graph:
+    def __init__(self):
+        self.graph = defaultdict(list)
+    
+    def add_edges(self,_from,_to):
+        for t in _to:
+            self.graph[_from].append(t)
+
+    def display(self):
+        print self.graph
+
+    def bfs(self,graph,start):
+        queue = [start]
+        visited = []
+
+        while queue:
+            a = queue.pop(0)
+            if a not in visited:
+                visited.append(a)
+                for neighbor in graph[a]:
+                    queue.append(neighbor)
+        print visited
+
+def main():
+
+    G = Graph()
+    G.add_edges(1,[2,7,8])
+    G.add_edges(2,[3,6])
+    G.add_edges(3,[4,5])
+    G.add_edges(8,[9,12])
+    G.add_edges(9,[10,11])
+    G.display()
+    G.bfs(G.graph,1)
+    
+if __name__ == '__main__':
+    main()
