built-in gangthoughwe need to move on to the next section graph searching many problems that crop up in both real life and real programming can be fairly represented as graph-- set of states with transitions ("arcs"that lead from one state to another for exampleplanning route for trip is really graph search problem in disguisethe states are places you' like to visitand the arcs are the transportation links between them program that searches for trip' optimal route is graph searcher for that matterso are many programs that walk hyperlinks on the web this section presents simple python programs that search through directedcyclic graph to find the paths between start state and goal graphs can be more general than trees because links may point at arbitrary nodes--even ones already searched (hence the word cyclicmoreoverthere isn' any direct built-in support for this type of goalalthough graph searchers may ultimately use built-in typestheir search routines are custom enough to warrant proprietary implementations the graph used to test searchers in this section is sketched in figure - arrows at the end of arcs indicate valid paths ( leads to beand gthe search algorithms will traverse this graph in depth-first fashionand they will trap cycles in order to avoid looping if you pretend that this is mapwhere nodes represent cities and arcs represent roadsthis example will probably seem bit more meaningful figure - directed graph implementing graph search the first thing we need to do is choose way to represent this graph in python script one approach is to use built-in datatypes and searcher functions the file in example - builds the test graph as simple dictionaryeach state is dictionary key data structures