Algorithms For Dummies

 

»

A queue for BFS, a list that works according to the FIFO principle. Newly 

discovered vertexes don’t wait long for processing.

 

»

A stack for DFS, a list that works according to the last in/first out (LIFO) 

principle.

The following code shows how to create a DFS:

def dfs(graph, start):

    stack = [start]

    parents = {start: start}

    path = list()

    while stack:

        print ('Stack is: %s' % stack)

        vertex = stack.pop(-1)

        print ('Processing %s' % vertex)

        for candidate in graph[vertex]:

            if candidate not in parents:

                parents[candidate] = vertex

                stack.append(candidate)

                print ('Adding %s to the stack'

                       % candidate)

        path.append(parents[vertex]

+'>'+vertex)

    return path[1:]

steps = dfs(graph, 'A')

print ('\nDFS:', steps)

Stack is: ['A']

Processing A

Adding B to the stack

Adding C to the stack

---

CHAPTER 9