with a list of keys of nodes it leads to (i.e., its arcs). This file also defines a function that
we’ll use to run a few searches in the graph.
Example 18-16. PP4E\Dstruct\Classics\gtestfunc.py
"dictionary based graph representation"
Graph = {'A': ['B', 'E', 'G'],
'B': ['C'], # a directed, cyclic graph
'C': ['D', 'E'], # stored as a dictionary
'D': ['F'], # 'key' leads-to [nodes]
'E': ['C', 'F', 'G'],
'F': [ ],
'G': ['A'] }
def tests(searcher): # test searcher function
print(searcher('E', 'D', Graph)) # find all paths from 'E' to 'D'
for x in ['AG', 'GF', 'BA', 'DA']:
print(x, searcher(x[0], x[1], Graph))
Now, let’s code two modules that implement the actual search algorithms. They are
both independent of the graph to be searched (it is passed in as an argument). The first
searcher, in Example 18-17, uses recursion to walk through the graph.
Example 18-17. PP4E\Dstruct\Classics\gsearch1.py
"find all paths from start to goal in graph"
def search(start, goal, graph):
solns = []
generate([start], goal, solns, graph) # collect paths
solns.sort(key=lambda x: len(x)) # sort by path length
return solns
def generate(path, goal, solns, graph):
state = path[-1]
if state == goal: # found goal here
solns.append(path) # change solns in-place
else: # check all arcs here
for arc in graph[state]: # skip cycles on path
if arc not in path:
generate(path + [arc], goal, solns, graph)
if name == 'main':
import gtestfunc
gtestfunc.tests(search)
The second searcher, in Example 18-18, uses an explicit stack of paths to be expanded
using the tuple-tree stack representation we explored earlier in this chapter.
Graph Searching| 1391