Why is my implementation of bfs so inefficient?

Question

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.

Here is the code in python 3.5.2:

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()

Answer 1

The primary delay in running the code is this optimization:

if neighbor not in explored:
    frontier.append(neighbor)

as it simply doesn't work. Add an else: clause to this to print the word skipped to the console and you'll see the else: is never taken. The optimization isn't working as the things you're putting into the set are all unique. @user2357112's comment about missing __hash__, __eq__ and __ne__ methods is the right way to address this (I used a simpler fix below.)

The secondary delay is you're creating (and drawing) lots of Node instances that you end up not using as they've already been explored.

Below is a rework of your code that tries to address both issues:

from collections import deque
from graphics import *

TITLE = "Breadth-First Search"

WIDTH, HEIGHT = 500, 500

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 unexplored_neighbors(state):
    neighbors = []

    for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
        if (state.x + dx, state.y + dy) not in explored:
            neighbors.append(Node(state.x + dx, state.y + dy, state))

    return neighbors

def bfs():
    start = (10, 10)
    finish = (15, 15)

    frontier = deque()
    frontier.append(Node(*start))

    while frontier:
        state = frontier.popleft()

        if state.getPos() == finish:
            break

        explored.add((state.x, state.y))

        for neighbor in unexplored_neighbors(state):
            frontier.append(neighbor)

win = GraphWin(TITLE, WIDTH, HEIGHT)
win.setCoords(0, 0, 20, 20)

explored = set()

bfs()

win.getMouse()
win.close()

What may help you find performance issues is the cProfile module:

# bfs()
import cProfile
cProfile.run('bfs()')

# win.getMouse()
# win.close()

Which you can read about in The Python Profilers