Merge branch 'bfs' into develop

1 files changed, 36 insertions, 2 deletions

diff --git a/search.py b/search.py
index c9c438e..b360091 100644
--- a/search.py
+++ b/search.py
@@ -129,8 +129,42 @@ def depthFirstSearch(problem):
 
 def breadthFirstSearch(problem):
     """Search the shallowest nodes in the search tree first."""
-    "*** YOUR CODE HERE ***"
-    util.raiseNotDefined()
+
+    # main search function
+
+    # initialize
+    queue = util.Queue()
+    visited = []
+    path = []
+    start = (problem.getStartState(), None, 0)
+
+    queue.push(start)
+    path.append(start)
+    visited.append(problem.getStartState())
+
+    def getActions(list, goal):
+        start = problem.getStartState()
+        path = []
+        list = list[1:]
+        list = list[::-1]
+        state = next((node for node in list if node[0][0] == goal), None)
+        while state[0][1] is not start:
+            path.insert(0, state[0][1])
+            state = next((node for node in list if node[0] == state[1]), None)
+            if state is None:
+                return path
+        return path
+
+    while not queue.isEmpty():
+        state = queue.pop()
+        if problem.isGoalState(state[0]):
+            return getActions(path, state[0])
+        for successor in problem.getSuccessors(state[0]):
+            if successor[0] not in visited:
+                visited.append(successor[0])
+                path.append((successor, state))
+                queue.push(successor)
+
 
 def uniformCostSearch(problem):
     """Search the node of least total cost first."""