Contents of the page


By the end of this lesson, you will be able to implement graph traversal algorithms (DFS and BFS) using queuing structures. 


Hi, and welcome to this lesson about queuing structures. 

In the previous lessons, we’ve looked at the two main algorithms for graph traversal, DFS and BFS, and how to build and use routing tables to navigate their corresponding graphs. In this lesson, we’ll see how these algorithms can be implemented in practice, using queuing structures.

A queuing structure is a memory structure that can be used to manage priorities between tasks. For example, imagine that we have a list of documents, and we need to decide the order in which we will process them. Queuing structures can be used to store the documents and manage their priority. 

There are only two operations that can be performed when using a queuing structure. Namely, adding (or pushing) an element, and removing (or, popping) an element. 

I’ll now introduce two queuing structures that can be used to manage priorities in different ways. 

Stacks / LIFO / Last-In First-Out

A stack, which is known as a Last-In-First-Out, or LIFO for short, is a memory structure for which the last element added in the stack is the first one that will be removed. Let’s imagine a list of documents we have to process. Using a LIFO means putting all the documents in a pile, or stack. You can only pick up the document on the top of the pile, which was the last one added. 

Queues / FIFO / First-In First-Out

On the contrary, a queue,  which is known as a First-In-First-Out, or FIFO for short, is a memory structure for which the first element added will be the first one to be removed. Imagine it as a queue in a shop. Customers are served on a first-come, first-served basis.

A unified algorithm for graph traversal

A queuing structure can be used to manage the priorities with which we explore vertices in a graph when performing graph traversal. When exploring a vertex, a queuing structure can be used to store the neighboring vertices – but only if those vertices weren’t previously explored. By repeating this principle until the queuing structure is empty, we obtain a DFS if we choose to use a LIFO, and BFS when we use a FIFO. Indeed, when using a LIFO, we first explore the last vertices that were added to the queuing structure, and thus keep following the last direction. However, when using a FIFO, we first explore the first added vertices, and thus proceed with increasing hops from the start.

The following unified algorithm will function for both a BFS and a DFS by simply changing the queuing structure. In other words, using the LIFO for a DFS, and the FIFO for a BFS.

# This unified algorithm takes as arguments a graph, and a vertex of this graph from which to start the graph traversal using a queuing structure. The algorithm returns the list of explored_vertices, and a routing table to navigate through the graph.

def traversal (start_vertex, graph) :

    # First we create either a LIFO or a FIFO
    queuing_structure = new_queuing_structure() 

    # Add the starting vertex with None as parent
    queuing_structure.push((start_vertex, None))

    # Initialize the outputs 
    explored_vertices = [] 
    routing_table = {} 

    # Iterate while some vertices remain
    while len(queuing_structure) > 0 :
    
        # This will return the next vertex to be examined, and the choice of queuing structure will change the resulting order
        (current_vertex, parent) = queuing_structure.pop() 
    
        # Tests whether the current vertex is in the list of explored vertices
        if current_vertex not in explored_vertices :

            # Mark the current_vertex as explored
            explored_vertices.append(current_vertex) 
       
            # Update the routing table accordingly
            routing_table[current_vertex] = parent 
       
            # Examine neighbors of the current vertex
            for neighbor in neighbors(graph, current_vertex) :

    	        # We push all unexplored neighbors to the queue
                if neighbor not in explored_vertices :              
                    queuing_structure.push((neighbor, current_vertex))
              
    return explored_vertices, routing_table

Once we have chosen a queuing structure, we first push the starting vertex.

Here, we are interested in building the routing table as well, so, in the queuing structure we push couples made of the vertex and its parent in the corresponding spanning tree. Since the starting vertex has no parent, we use NULL instead here.

We also create the initially empty set of explored vertices, and the initially empty routing table.

Then, as long as the queuing structure is not empty, we pop a vertex and its parent.

If this vertex is not already explored, we mark it as explored and we update the routing table by associating the vertex with its parent. Finally, we add all unexplored neighbors of the vertex to the queuing structure, with the current vertex as parent.

If the vertex we popped from the queuing structure was already explored, we simply ignore it.

The algorithm finishes when the queuing structure is finally empty. Depending on the choice of the queuing structure: a LIFO or a FIFO, we obtain a DFS or a BFS.

Let’s illustrate this using an example.

Application with DFS

Let’s perform a DFS from v_1. We show the content of the LIFO as we traverse the graph.

The list of explored vertices is on the right. We also show the routing table. 

2_3_DFS_1

We begin by pushing the starting vertex v_1 into the LIFO, with NULL as its parent.

We pop a vertex and its parent from the LIFO, v_1, and NULL. As v_1 is not in the list of explored vertices, we mark it as explored and update the entry corresponding to v_1 in the routing table by setting it to NULL. Then, we push in the LIFO all the neighbors of v_1 that are not in the list of explored vertices, which are v_2 and v_4, with their parent v_1.

2_3_DFS_2

We remove an element from the LIFO, which is v_4, with v_1 as parent, because it’s the last element that was added.  v_4 is not in the list of explored vertices, so we mark it as explored, and update the entry corresponding to v_4 in the routing table by setting it to v_1. Next, we push all its unexplored neighbors into the LIFO. As v_1 has already been explored, we push v_2, v_6 then v_3 in the LIFO, with v_4 as parent.

2_3_DFS_3

The next element to be removed is v_3 and its parent v_4. As v_3 wasn’t previously explored, we add it to the list of explored vertices and update the routing table accordingly. Among the neighbors of v_3, only v_2 hasn’t been explored, so we push v_2 in the LIFO, with v_3 as parent. We remove v_2 and its parent v_3 from the LIFO. v_2 wasn’t previously explored, so we mark it as explored and update the routing table by setting the corresponding entry to v_3. Among the neighbors of v_2, only v_6 hasn’t been explored, so we push v_6 with v_2 as parent in the LIFO.

2_3_DFS_4

The next element to be removed is v_6 and its parent v_2. v_6 wasn’t previously explored, so we mark it and update the routing table. The unexplored neighbors of v_6 are v_5 and v_7, so we push them into the LIFO with v_6 as parent.

2_3_DFS_6

We then remove v_7 with its parent v_6. As v_7 wasn’t previously explored, we mark it as explored and update the routing table. The only neighbor of v_7 is v_6, which was previously explored, so nothing is pushed in the LIFO. The next element that is popped from the LIFO is v_5 and its parent v_6. v_5 wasn’t explored, so we mark it as explored and update the routing table. Here again, the only neighbor of v_5 is v_6, which was already explored, so nothing is pushed in the LIFO.

2_3_DFS_7

Next, we pop v_6 with v_4 as parent. As v_6 has already been explored, nothing happens. We pop v_2 with v_4 as parent, and here again, v_2 has already been explored, so nothing happens. Finally, v_2 with v_1 as parent is popped from the LIFO, but again, v_2 has already been explored, so nothing happens.

The queuing structure is now empty, so the algorithm finishes. Notice that the fact that we’re using a LIFO directly corresponds to the fact that we keep exploring the graph until the search reaches a vertex without unexplored neighbors, in which case we go back to previously explored vertices.

Application with BFS

Let’s now see how we can perform a BFS from v_1 by using a FIFO. We start by pushing v_1 in the FIFO, with NULL as parent. We pop a vertex and its parent from the FIFO, v_1 and NULL. v_1 wasn’t previously explored so we mark it, and update the routing table. Then, we push in the FIFO all unexplored neighbors of v_1, which are v_2 and v_4, with their parent v_1.

2_3_BFS_1

We pop an element from the FIFO, which is v_2 with v_1 as parent, because it’s the first element that was pushed. v_2 wasn’t previously explored, so we add it to the list of explored vertices and update the routing table accordingly. We push all neighbors of v_2 that are not in the list of explored vertices : v_4, v_3 and v_6, with v_2 as parent.

2_3_BFS_2

The next element to be removed from the FIFO is v_4 with v_1 as parent. As v_4 is not in the list of explored vertices, we mark it and update the routing table. Among the neighbors of v_4, only v_3 and v_6 are not in the list of explored vertices, so we push them in the FIFO with v_4 as parent.

Next, we pop the element v_4 with v_2 as parent. v_4 has already been explored, so we move on.

We pop the next element from the FIFO, v_3 with v_2 as parent. v_3 wasn’t explored, so we mark it and update the routing table accordingly. All neighbors of v_3 have been explored, so we continue.

2_3_BFS_3

The next element to be popped from the FIFO is v_6 with v_2 as parent. This vertex wasn’t previously explored, so we mark it and update the routing table. Among the neighbors of v_6, only two neighbors are unexplored: v_7 and v_5, so we push them in the FIFO with v_6 as parent.

We pop the element v_3 with v_4 as parent, but as v_3 was already explored, nothing happens. Similarly, v_6 with v_4 is popped from the FIFO, but as v_6 was already explored, we move on.

2_3_BFS_4

Now, we remove from the FIFO the element v_7 with v_6 as parent. v_7 was not previously explored so we mark it and update the routing table. The only neighbor of v_7 is v_6, which was previously explored, so we continue. Finally, we pop v_5 with v_6 as parent from the FIFO. v_5 is not in the list of explored vertices, so we add it to this list, and update the routing table. Here again, v_5 does not have any unexplored neighbors.

The queuing structure is now empty, so the algorithm finishes. We’ve now successfully traversed the graph using BFS. 


FIFOs and LIFOs in computer science

To appreciate the importance of these two data structures in computer science, we present two examples of real life situations in which they are used.

FIFOs in communication systems

For two people to communicate, they must send messages to each other; and for two people to understand each other, they must send messages to each other in a logical order. You will find it easier to understand the sentence A computer lets you make more mistakes faster than any other invention with the possible exceptions of handguns and Tequila than Make and tequila you than a faster the possible any exceptions handguns of invention computer lets more with other mistakes.

For machines, it’s the same: order is important, and must be taken into account. Some communication models (others are much more complex) use queues for this purpose. Imagine a model in which we have a computer A that writes words in a queue, and a computer B that reads them. If computer A sends the words in order, then B will read them in the same order (because the first element inserted in a queue is also the first to leave it), and communication will be possible.

You may be wondering why go through a FIFO and not send the information directly? The advantage is that computers A and B do not necessarily go at the same speed (quality of the processor, network card…). Thus, if computer A sends messages to computer B very quickly (directly), the latter will miss some of them. Going through a queue allows you to store messages, in order, to avoid these synchronization problems.

LIFOs in programming languages

When an operating system runs a program, it allocates some memory to it so that it can do its calculations correctly. This memory is generally divided into two areas: the heap that stores data, and the heap that allows (among other things) to call functions in programs.

In most programming languages, when a function f(a, b) is called at a code location, the following (simplified) sequence occurs:

  1. The return address is pushed on the stack. This will allow coming back right after f is called once its execution ends.
  2. Argument a is pushed on the stack.
  3. Argument b is pushed on the stack.
  4. The processor is told to process the code of f.
  5. We pop an element from the stack to get b.
  6. We pop an element from the stack to get a.
  7. The code of f is executed.
  8. Once f is over, we pop an element from the stack to get the return address and go back to when f was called.
  9. The processor is told to jump to that address.

But why use a stack instead of variables to pass this information? Well, the processor doesn’t know the details of f! It is possible that f uses another function g for example. If variables were used, the return address of f would be overwritten by the return address of g, and when g was finished, we could never return to the time of the call of f.

How about a FIFO then? Here again, the problem occurs if f calls a function g. As the return address of f is put before that of g in the queue, when it is necessary to return from the call to g, the processor will get instead the return address of f (the oldest in the queue)! We will therefore never execute the f code located after the g call.


To go further

  • Queuing theory gives more results on queues (expected time before being popped, etc.) and has many applications.

Quiz

When removing an element from a FIFO, we get...
A DFS can be implemented using...
We add the elements 10, 25, 52, 40, 20, then 40 to a LIFO (in this order). What is the correct sequence (read from the left to the right) when performing four consecutive removals?