Queuing structures for graph traversals

Reading time20 min

In brief

Article summary

In this article, you will learn how about some common queuing structures, and how they can be used to shape the behavior of a traversal algorithm. You will learn about LIFO (Last-In First-Out) and FIFO (First-In First-Out), which respectively define a DFS and a BFS.

Main takeaways

  • Queuing structures are data structures in which data enters/exits in a specific order.

  • Some common structures are stacks and queues.

  • They can be used to shape the behavior of a traversal.

  • DFS and BFS can be seen as a unique algorithm, parametrized with either a stack or a queue.

  • Such data structures find applications in numerous situations in computer science.

Article contents

1 — Video

Please check the video below. You can also read the transcripts if you prefer.

Important

There are some “codes” that appear in this video. Please keep in mind that these “codes” are what we call pseudo-codes, i.e., they are not written in a real programming language. Their purpose is just to describe the algorithms, not to be interpretable per se. You will thus need a bit of work to make them fully-functional Python codes if you wish to.

Information

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 the priority between documents.

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 examine 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.

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.

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$.

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. Vertex $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.

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. Vertex $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.

The next element to be removed is $v_6$ and its parent $v_2$. Vertex $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.

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$. Vertex $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.

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. Vertex $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$.

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. Vertex $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.

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. Vertex $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. Vertex $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.

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.

Now, we remove from the FIFO the element $v_7$ with $v_6$ as parent. Vertex $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. Vertex $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.

Concluding words

So, that’s how you can use queuing structures to implement DFS and BFS.

Thanks for watching! I hope you enjoyed learning about queuing structures. That’s the end of this week’s lessons. Next week, we’ll see how to deal with weighted graphs.

To go further

2 — 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.

2.1 — 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.

2.2 — 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 stack 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:

  • The return address is pushed on the stack. This will allow coming back right after f is called once its execution ends.
  • Argument a is pushed on the stack.
  • Argument b is pushed on the stack.
  • The processor is told to process the code of f.
  • We pop an element from the stack to get b.
  • We pop an element from the stack to get a.
  • The code of f is executed.
  • Once f is over, we pop an element from the stack to get the return address and go back to when f was called.
  • 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 code of f located after the g call.

To go beyond

  • Queuing theory.

    Gives more results on queues (expected time before being popped, etc.) and has many applications.