Simple BFS program

PriyankaKhire · PriyankaKhire · commit 32c1eba96076 · 2017-08-04T21:44:47.000-07:00
diff --git a/BFS.py b/BFS.py
@@ -0,0 +1,65 @@
+#Breadth first search
+class queue():
+    def __init__(self):
+        self.array = []
+    def push(self, data):
+        self.array.append(data)
+    def pop(self):
+        if not self.array:
+            return
+        del self.array[0]
+    def top(self):
+        return self.array[0]
+    def isEmpty(self):
+        if not self.array:
+            return True
+        return False
+
+def bfs(m, q, result, visited):
+    #If q is not empty
+    if not q.isEmpty():
+        #Pop the top element
+        t = q.top()
+        q.pop()
+        #Add it to result
+        result.append(t)
+        #Add all its adjacent unvisited elements to the q
+        for adjacentElement in range(9):
+            if(m[t][adjacentElement] == 1 and visited[adjacentElement] == 0):
+                #Mark it visited
+                visited[adjacentElement] = 1
+                #Add it to the q
+                q.push(adjacentElement)
+        bfs(m, q, result, visited)
+    return result
+
+def foo(matrix):
+    q = queue()
+    q.push(0)
+    v = [0 for col in range(9)]
+    v[0] = 1
+    r = bfs(matrix, q, [], v)
+    print r
+
+#Main Program
+matrix = [[0 for col in range(9)] for row in range(9)]
+matrix[0][1] = 1
+matrix[0][8] = 1
+matrix[1][0] = 1
+matrix[8][0] = 1
+matrix[8][2] = 1
+matrix[8][6] = 1
+matrix[2][3] = 1
+matrix[2][4] = 1
+matrix[2][5] = 1
+matrix[2][8] = 1
+matrix[3][2] = 1
+matrix[4][2] = 1
+matrix[4][7] = 1
+matrix[5][2] = 1
+matrix[5][6] = 1
+matrix[6][8] = 1
+matrix[6][5] = 1
+matrix[7][4] = 1
+matrix[7][6] = 1
+foo(matrix)
