Depth First Search in Python

Well, it has been a while since I posted some code onto these pages, so what follows is some Python 3 code for a depth-first search as I taught it to some students today.

The code uses a stack to implement the depth first search. The output shows the nodes visited.

I shall use the following graph as an example. The graph has been coded as an adjacency list using a dictionary where the nodes are assigned integer keys and their value is a list containing the nodes that they are connected to.

A graph representing a maze with ten nodes featuring closed loops. You can ignore the path leading from 9. I have chosen a maze that cannot be solved by following the walls method (it will ignore node 5)

The code:
(Also available as a download from OneDrive because it is highly likely that it won't work well pasted from the browser.)

class mystack:
    def __init__(self, size):
        self.__stack = []
        self.__size = size
        for i in range (size):
            self.__stack.append("")
        self.__tos = -1
    def peek(self):
        if self.__isEmpty():
            pass
        else:
            return (self.__stack[ self.__tos ])
   
    def push(self, item):
        if not(self.__isFull()):
            self.__stack[ self.__tos + 1 ] = item
            self.__tos += 1
        else:
            print("STACK OVERFLOW")
           
    def pop(self):
        if not(self.__isEmpty()):
            self.__tos -= 1
            return self.__stack[self.__tos + 1]
        else:
            raise StackEmpty("Stack is empty")
           
    def __isEmpty(self):
        return (self.__tos == -1)
       
    def __isFull(self):
        return self.__tos == self.__size-1

    def display(self):
        for i in range (0, self.__tos+1 ):
            print (self.__stack[i], end=", ")


class dfs(object):
    def __init__(self):
        #map is the adjacency list
        #visited keeps track of which nodes have been visited
        #stack is the stack of current nodes under investigation
        self.__map = {0: [1,5,4], 1:[2,0], 2:[3,1,6], 3:[2], 4:[0,8], 5:[0,6,9,8], 6:[2,7,9,5], 7:[6], 8:[4,5,9], 9:[8,5,6]}
        self.__visited = [False, False, False, False, False, False, False, False, False, False]
        self.__stack = mystack(10)

    def main(self):
        start = 0
        current = start
        solved = False
        while not(solved):
            try:
                print("exploring node", current, end='')
                if not(self.__completed(current)):
                    self.__stack.push(current)
                self.__visited[current] = True
                next = self.__findNextNode(current)
                if next != None:
                    current = next
                else:
                    current = self.__stack.pop()
                    print("...deadend...backtracking to", current, end='\n')
                self.__stack.display()
                print()
   
            except StackEmpty as e:
                #assume maze is solved
                solved = True
  
        print("\nMaze fully explored by dfs :-)")
  

    def __findNextNode(self, p):
        #finds next unvisited node in the adjacency list
        nodes = self.__map[p]
        i = 0
        while i<len(nodes):
            if not(self.__visited[ nodes[i] ]):
                return self.__map[p][ i ]
            else:
                i += 1
        return None

    def __completed(self, p):
 #returns true if node p has been fully explored
        nodes = self.__map[p]
        i = 0
        while i<len(nodes):
            if not(self.__visited[ nodes[i] ]):
                return False
            else:
                i += 1
        return True

   
   
class StackEmpty(Exception):
    def __init__(self, value):
        self.value = value
    def toString(self):
        return self.value


app = dfs()
app.main()


The output

exploring node 0
0,
exploring node 1
0, 1,
exploring node 2
0, 1, 2,
exploring node 3...deadend...backtracking to 2
0, 1,
exploring node 2
0, 1, 2,
exploring node 6
0, 1, 2, 6,
exploring node 7...deadend...backtracking to 6
0, 1, 2,
exploring node 6
0, 1, 2, 6,
exploring node 9
0, 1, 2, 6, 9,
exploring node 8
0, 1, 2, 6, 9, 8,
exploring node 4...deadend...backtracking to 8
0, 1, 2, 6, 9,
exploring node 8
0, 1, 2, 6, 9, 8,
exploring node 5...deadend...backtracking to 8
0, 1, 2, 6, 9,
exploring node 8...deadend...backtracking to 9
0, 1, 2, 6,
exploring node 9...deadend...backtracking to 6
0, 1, 2,
exploring node 6...deadend...backtracking to 2
0, 1,
exploring node 2...deadend...backtracking to 1
0,
exploring node 1...deadend...backtracking to 0
exploring node 0
Maze fully explored by dfs :-)

Maze Generator

I really like this site. at the moment.  Maze Generator from xefer.com is as good as they come.  You can create any size maze (within reason) and then let the computer solve it.  The algorithm uses a depth first tree search to test each path in the maze.  Here you can see the grey path has been 'visited' and rejected.  The current path being investigated is shown in blue.  For really large mazes you will want to leave the app running in a spare tab as the animation takes up most of the run time.

Maze in Microsoft's Edge browser

Settings allow you to alter the width, height and size of each cell.  You can also change the anfractuosity of the maze.  Yes, I had to look 'anfractuosity' up.  It means twisty-ness.

+1 geek experience point awarded to xefer.com. Do go and check out their other projects which include a game of life simulator among other stuff.

Bored already?   Can't wait for the next superdecade games post?  You could either check out our website, have a game of Have Spell Will Travel, or check out all our posts about random maze algorithms.