Algorithms For Dummies

 Understanding the Need to Sort and Search

Building graphs

Most  developers  use  dictionaries  (or  sometimes  lists)  to  build  graphs.  Using  a 

dictionary makes building the graph easy because the key is the node name and 

the values are the connections for that node. For example, here is a dictionary that 

creates the graph shown in Figure 6-2. (You can find this code in the 

A4D; 06; 

Graphs.ipynb

 file on the Dummies site as part of the downloadable code; see the 

Introduction for details.)

graph = {'A': ['B', 'F'],

         'B': ['A', 'C'],

         'C': ['B', 'D'],

         'D': ['C', 'E'],

         'E': ['D', 'F'],

         'F': ['E', 'A']}

This  dictionary  reflects  the  bidirectional  nature  of  the  graph  in  Figure  6-2.  It 

could  just  as  easily  define  unidirectional  connections  or  provide  nodes  without 

any connections at all. However, the dictionary works quite well for this purpose, 

and you see it used in other areas of the book. Now it’s time to traverse the graph 

using the following code:

def find_path(graph, start, end, path=[]):

        path = path 

+ [start]

  

        if start == end:

            print("Ending")

            return path

  

        for node in graph[start]:

            print("Checking Node ", node)

  

            if node not in path:

                print("Path so far ", path)

  

                newp = find_path(graph, node, end, path)

                if newp:

                    return newp

  

find_path(graph, 'B', 'E')

  

Checking Node  A

Path so far  ['B']

Checking Node  B

---

CHAPTER 6