title: Why is my implementation of bfs so inefficient?
body: <p>I have recently began an attempt to write a program which uses the graphics.py module from Zelle's python programming book. The idea of the program is it makes a graphics window and accepts two points, the start and the end. It draws the start point and does a bfs search, and then once it reaches the end point it draws the shortest path (no diagonals yet anyway). And it technically works, but it is extremely slow, and getting anywhere past the first two to three iterations take forever. And I have tried looking everywhere for data structures that have fast lookup, and efficient ways to implement a node so as to allow for backtracking, and I just can't figure it out. I would greatly appreciate any help in explaining to me what I could to to improve my implementation. </p>
  
  <p>Here is the code in python 3.5.2:</p>
  
  <pre><code>from graphics import *
  from collections import deque
  TITLE = "Breadth-First Search"
  WIDTH = 500
  HEIGHT = 500
  
  
  win = GraphWin(TITLE, WIDTH, HEIGHT)
  win.setCoords(0,0,20,20)
  
  class Node:
      def __init__(self, x, y, parent = None):
          self.x = x
          self.y = y
          self.parent = parent
          self.pos2D = Point(self.x, self.y)
          self.pos2D.draw(win)
  
      def getPos(self):
          return (self.x, self.y)
  
      def draw(self, win, color = None):
          if color != None:
              self.pos2D.undraw()
              self.pos2D.setFill(color)
              self.pos2D.draw(win)
              return
          self.pos2D.draw(win)
  
  
  def neighbors(state):
      return (Node(state.x, state.y+1, state), Node(state.x, state.y-1, 
  state), Node(state.x-1, state.y, state), Node(state.x+1, state.y, 
  state))
  
  def drawPath(endState):
      state.draw(win, 'red')
      while state.parent != None:
          state = state.parent
          state.draw(win, 'red')
  
  def bfs():
      start = (10,10)
      finish = (15,15)
  
      explored = set()
  
      frontier = deque()
      frontier.append((Node(start[0], start[1])))
  
      while len(frontier) != 0:
          state = frontier.popleft()
          explored.add(state)
  
          if state.getPos() == finish:
              break
  
          for neighbor in neighbors(state):
              if neighbor not in explored:
                  frontier.append(neighbor) 
  bfs()
  </code></pre>