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