7 Graph Search

7.1 Learning Objectives

Understand which element a queue, a stack, and a priority queue take out first, and use them in Python.
Understand the breadth-first search algorithm and find the order in which it visits the vertices.
Understand the depth-first search algorithm and find the order in which it visits the vertices.

7.2 Queue, Stack, and Priority Queue

There are three common data structures used in searching algorithms: queue, stack, and priority queue.

A queue is a first-in-first-out (FIFO) data structure. Adding one vertex to the queue is called enqueue, and popping one vertex out is called dequeue. A queue first dequeues the vertex that was enqueued earliest.
A stack is a last-in-first-out (LIFO) data structure. Adding one vertex to the stack is called push, and popping one vertex out is called pop. A stack first pops the vertex that was pushed most recently.
A priority queue is a data structure that stores elements with a key. Adding one element to the priority queue is called insert, and popping one element out is called extract. A priority queue first extracts the element with the smallest or largest key.

See Figure 7.1 for an illustration of these three data structures.

Code

import matplotlib.patches as mpatches
import matplotlib.pyplot as plt

added = [5, 2, 7, 3]  # the numbers, in the order they are added
gap = 0.15  # gap between boxes, and between boxes and walls
length = len(added) + (len(added) - 1) * gap  # length of a line of boxes
middle = length / 2  # the queue and the priority queue are centered on the stack
arrow = dict(arrowstyle="-|>", color="black", mutation_scale=12, shrinkA=0, shrinkB=0)
wall = dict(color="black", linewidth=1.2)
label_style = dict(va="center", fontsize=11)
title_style = dict(ha="center", va="center", fontsize=12)


def draw_box(ax, x, y, number, gray):
    """Draw a unit box with the number and its lower-left corner at (x, y)."""
    ax.add_patch(
        mpatches.Rectangle(
            (x, y),
            1,
            1,
            facecolor="lightgray" if gray else "white",
            edgecolor="black",
            linewidth=1,
        )
    )
    ax.text(x + 0.5, y + 0.5, str(number), ha="center", va="center", fontsize=12)


def draw_arrow(ax, tail, head):
    """Draw an arrow from tail to head."""
    ax.annotate("", xy=head, xytext=tail, arrowprops=arrow)


# Computer Modern fonts, as in LaTeX. The last setting avoids a warning about cmr10.
latex_style = {
    "font.family": "cmr10",
    "mathtext.fontset": "cm",
    "axes.formatter.use_mathtext": True,
}
with plt.rc_context(latex_style):
    fig, ax = plt.subplots(figsize=(6.5, 2.7))

    # Queue: a number enters at the right end and leaves at the left end
    x0, y0 = 1.7, middle - 0.5
    for j, number in enumerate(added):
        draw_box(ax, x0 + j * (1 + gap), y0, number, gray=(j == 0))
    left, right = x0 - gap - 0.25, x0 + length + gap + 0.25  # ends of the walls
    for y in (y0 - gap, y0 + 1 + gap):
        ax.plot([left, right], [y, y], **wall)
    draw_arrow(ax, (left - 0.3, middle), (left - 1.6, middle))
    ax.text(left - 0.95, middle + 0.4, "dequeue", ha="center", **label_style)
    draw_arrow(ax, (right + 1.6, middle), (right + 0.3, middle))
    ax.text(right + 0.95, middle + 0.4, "enqueue", ha="center", **label_style)
    ax.text(x0 + length / 2, -0.75, "Queue", **title_style)

    # Stack: a number enters and leaves at the top
    x0 = right + 3.2
    for j, number in enumerate(added):
        draw_box(ax, x0, j * (1 + gap), number, gray=(j == len(added) - 1))
    left, right, top = x0 - gap, x0 + 1 + gap, length + 0.25  # walls
    ax.plot([left, left, right, right], [top, -gap, -gap, top], **wall)
    draw_arrow(ax, (x0 + 0.27, top + 1.2), (x0 + 0.27, top + 0.15))
    ax.text(x0 + 0.1, top + 0.7, "push", ha="right", **label_style)
    draw_arrow(ax, (x0 + 0.73, top + 0.15), (x0 + 0.73, top + 1.2))
    ax.text(x0 + 0.9, top + 0.7, "pop", ha="left", **label_style)
    ax.text(x0 + 0.5, -0.75, "Stack", **title_style)

    # Priority queue: the numbers are in no particular order, and the smallest leaves
    step = 1 + 3 * gap  # distance between neighboring boxes
    size = 1 + step  # width and height of the 2 x 2 grid of boxes
    x0, y0 = x0 + 3.6, middle - size / 2
    for j, number in enumerate(added):
        row, col = divmod(j, 2)  # filled row by row from the top left
        x, y = x0 + col * step, y0 + (1 - row) * step
        draw_box(ax, x, y, number, gray=(number == min(added)))
    pad = 0.3  # gap between the grid and the wall
    ax.add_patch(
        mpatches.FancyBboxPatch(
            (x0 - pad, y0 - pad),
            size + 2 * pad,
            size + 2 * pad,
            boxstyle="round,pad=0,rounding_size=0.4",
            facecolor="none",
            edgecolor="black",
            linewidth=1.2,
        )
    )
    top = y0 + size + pad  # top of the wall
    draw_arrow(ax, (x0 + 0.5, top + 1.15), (x0 + 0.5, top + 0.1))
    ax.text(x0 + 0.33, top + 0.65, "insert", ha="right", **label_style)
    x = x0 + step + 0.5  # above the smallest number, 2, at the top right
    draw_arrow(ax, (x, y0 + size), (x, top + 1.15))
    ax.text(x + 0.17, top + 0.65, "extract", ha="left", **label_style)
    ax.text(x0 + size / 2, -0.75, "Priority queue", **title_style)

    ax.set(xlim=(-0.75, x0 + size + 1.3), ylim=(-1.15, length + 1.7), aspect="equal")
    ax.axis("off")
    fig.subplots_adjust(left=0, right=1, top=1, bottom=0)
    plt.show()

Three diagrams side by side, labeled Queue, Stack, and Priority queue. In the queue, four boxes with 5, 2, 7, and 3 from left to right lie between two horizontal lines that are open at both ends, and the box with 5 is gray. An arrow labeled enqueue points into the right end, and an arrow labeled dequeue points out of the left end. In the stack, four boxes with 5, 2, 7, and 3 from bottom to top lie in a container that is open at the top, and the box with 3 is gray. Above the opening, an arrow labeled push points down, and an arrow labeled pop points up. In the priority queue, four boxes lie in a rounded rectangle, with 5 and 2 in the top row and 7 and 3 in the bottom row, and the box with 2 is gray. An arrow labeled insert points down into the rectangle, and an arrow labeled extract points up from the box with 2 out of the rectangle. — Figure 7.1: Queue, stack, and priority queue after the numbers 5, 2, 7, and 3 are added in this order. The number in the gray box is taken out next: the number added first from the queue, the number added last from the stack, and the smallest number from the priority queue, which uses each number as its key.

In Python, these data structures are available as queue.Queue, queue.LifoQueue, and queue.PriorityQueue.

Example 7.1 (Queue, stack, and priority queue in Python) The three classes have the same methods: put adds an element, and get takes one out. The following code adds the numbers 5, 2, 7, and 3 in this order to a queue, as in Figure 7.1, and then takes all of them out.

from queue import Queue

queue = Queue()
queue.put(5)
queue.put(2)
queue.put(7)
queue.put(3)
print(queue.get())
print(queue.get())
print(queue.get())
print(queue.get())

The queue takes the numbers out in the order they were added. The same code with a stack takes them out in the reverse order.

from queue import LifoQueue

stack = LifoQueue()
stack.put(5)
stack.put(2)
stack.put(7)
stack.put(3)
print(stack.get())
print(stack.get())
print(stack.get())
print(stack.get())

With a priority queue, each number is used as its own key, so the numbers are taken out in increasing order.

from queue import PriorityQueue

priority_queue = PriorityQueue()
priority_queue.put(5)
priority_queue.put(2)
priority_queue.put(7)
priority_queue.put(3)
print(priority_queue.get())
print(priority_queue.get())
print(priority_queue.get())
print(priority_queue.get())

In each case, the first one taken out corresponds to the gray box in Figure 7.1.

The queue module and other Python containers

The queue module is designed for passing data between threads, so its classes use a lock in every put and get. We use them because the three classes have the same methods. Programs with a single thread usually use collections.deque as a queue, a list as a stack, and the heapq module for a priority queue, which are faster. Note also that an empty Queue is not false in an if or while condition: while queue: never stops, so write while not queue.empty():.

7.3 Breadth-First Search

Algorithm 1 shows breadth-first search from a start vertex s in a directed graph G = (V, E), where \mathcal{S}(v) is the set of successors of v (Chapter 6). For an undirected graph, replace \mathcal{S}(v) with the set \mathcal{N}(v) of neighbors of v.

\begin{algorithm} \caption{Breadth-First Search} \begin{algorithmic} \Require graph $G = (V, E)$, start vertex $s \in V$ \State Create a queue $Q$ \ForAll{$v \in V$} \State $\text{visited}[v] \gets \text{false}$ \EndFor \State $\text{visited}[s] \gets \text{true}$ \State $Q.\text{enqueue}(s)$ \While{$Q$ is not empty} \State $v \gets Q.\text{dequeue}()$ \State visit $v$ \ForAll{$u \in \mathcal{S}(v)$} \If{not $\text{visited}[u]$} \State $\text{visited}[u] \gets \text{true}$ \State $Q.\text{enqueue}(u)$ \EndIf \EndFor \EndWhile \end{algorithmic} \end{algorithm}

Example 7.2 (Breadth-first search) Consider the undirected graph in Figure 7.2. We apply Algorithm 1 with start vertex v_1, and we process the neighbors of each vertex in increasing order of their subscripts.

Code

import networkx as nx


def draw_graph(G, pos, width, height):
    """Draw the graph G with the vertices at the positions pos.

    A vertex "v1" is labeled $v_1$, and a directed edge is drawn as an arrow.
    """
    labels = {v: rf"$v_{v[1:]}$" if v.startswith("v") else rf"${v}$" for v in G}
    arrows = {"arrowstyle": "-|>", "arrowsize": 12} if G.is_directed() else {}
    with plt.rc_context(latex_style):
        fig, ax = plt.subplots(figsize=(width, height))
        nx.draw_networkx(
            G,
            pos,
            labels=labels,
            node_color="white",
            edgecolors="black",
            linewidths=1.0,
            node_size=450,
            font_size=12,
            font_family="cmr10",
            width=1.0,
            ax=ax,
            **arrows,
        )
        ax.set_aspect("equal")
        ax.margins(0.12)
        ax.axis("off")
        plt.show()


G = nx.Graph()
G.add_edges_from([("v1", "v2"), ("v1", "v3"), ("v2", "v4"), ("v3", "v4"), ("v3", "v5")])
pos = {"v1": (1, 2), "v2": (0, 1), "v3": (2, 1), "v4": (1, 0), "v5": (3, 0)}
draw_graph(G, pos, 3.6, 2.4)

An undirected graph with five vertices drawn as circles labeled v1 to v5. v1 is at the top, v2 and v3 are below it on the left and right, v4 is below between v2 and v3, and v5 is at the lower right. The edges are v1–v2, v1–v3, v2–v4, v3–v4, and v3–v5. — Figure 7.2: An undirected graph with five vertices.

Table 7.1 shows the queue Q after each vertex v is dequeued and its neighbors are processed. The vertex at the left end of Q is dequeued next.

Table 7.1: The queue Q in breadth-first search from v_1. The first row shows Q before the while loop.

Dequeued (v)	Enqueued	Q
–	v_1	(v_1)
v_1	v_2, v_3	(v_2, v_3)
v_2	v_4	(v_3, v_4)
v_3	v_5	(v_4, v_5)
v_4	–	(v_5)
v_5	–	( )

The vertices are visited in the order v_1, v_2, v_3, v_4, v_5.

7.3.1 Python Implementation

The function bfs() follows Algorithm 1. The graph is given as a dictionary graph, where graph[v] is the list of the successors of v, or of the neighbors of v for an undirected graph. The vertices in graph[v] are processed in the order of the list. The set visited contains the vertices v with \text{visited}[v] = \text{true}.

from queue import Queue


def bfs(graph, s):
    """Breadth-first search from s. Print each vertex it visits."""
    visited = {s}
    queue = Queue()
    queue.put(s)

    while not queue.empty():
        v = queue.get()
        print(v)  # visit v

        for u in graph[v]:
            if u not in visited:
                visited.add(u)
                queue.put(u)

The following code applies bfs() to the graph in Figure 7.2. The vertices are printed in the order found in Example 7.2.

graph = {
    "v1": ["v2", "v3"],
    "v2": ["v1", "v4"],
    "v3": ["v1", "v4", "v5"],
    "v4": ["v2", "v3"],
    "v5": ["v3"],
}
bfs(graph, "v1")

v1
v2
v3
v4
v5

7.4 Depth-First Search

Algorithm 2 shows depth-first search. It uses a stack L instead of a queue, and it marks a vertex as visited when the vertex is popped from L, not when it is pushed. As in Algorithm 1, replace \mathcal{S}(v) with \mathcal{N}(v) for an undirected graph.

\begin{algorithm} \caption{Depth-First Search} \begin{algorithmic} \Require graph $G = (V, E)$, start vertex $s \in V$ \State Create a stack $L$ \ForAll{$v \in V$} \State $\text{visited}[v] \gets \text{false}$ \EndFor \State $L.\text{push}(s)$ \While{$L$ is not empty} \State $v \gets L.\text{pop}()$ \If{not $\text{visited}[v]$} \State $\text{visited}[v] \gets \text{true}$ \State visit $v$ \ForAll{$u \in \mathcal{S}(v)$} \If{not $\text{visited}[u]$} \State $L.\text{push}(u)$ \EndIf \EndFor \EndIf \EndWhile \end{algorithmic} \end{algorithm}

Example 7.3 (Depth-first search) We apply Algorithm 2 to the graph in Figure 7.2 with start vertex v_1, and we process the neighbors of each vertex in increasing order of their subscripts as in Example 7.2. Table 7.2 shows the stack L after each vertex v is popped. The vertex at the right end of L is popped next.

Table 7.2: The stack L in depth-first search from v_1. The first row shows L before the while loop.

Popped (v)	Pushed	L
–	v_1	(v_1)
v_1	v_2, v_3	(v_2, v_3)
v_3	v_4, v_5	(v_2, v_4, v_5)
v_5	–	(v_2, v_4)
v_4	v_2	(v_2, v_2)
v_2	–	(v_2)
v_2 (skipped)	–	( )

The vertices are visited in the order v_1, v_3, v_5, v_4, v_2.

Note that v_2 is pushed twice, when v_1 is visited and when v_4 is visited, because \text{visited}[v_2] is still false when v_4 is visited. When v_2 is popped the second time, it has already been visited and is skipped.

7.4.1 Python Implementation

The function dfs() follows Algorithm 2, with graph and visited as in bfs().

from queue import LifoQueue


def dfs(graph, s):
    """Depth-first search from s. Print each vertex it visits."""
    visited = set()
    stack = LifoQueue()
    stack.put(s)

    while not stack.empty():
        v = stack.get()
        if v in visited:
            continue
        visited.add(v)
        print(v)  # visit v

        for u in graph[v]:
            if u not in visited:
                stack.put(u)

The following code applies dfs() to the same graph. The vertices are printed in the order found in Example 7.3.

dfs(graph, "v1")

v1
v3
v5
v4
v2

7.5 Summary

A queue takes out the element added first, a stack takes out the element added last, and a priority queue takes out the element with the smallest or largest key.
Breadth-first search uses a queue and explores the vertices closer to the start vertex first.
Depth-first search uses a stack, goes as far as it can, and then goes back.
Besides using a queue or a stack, breadth-first search and depth-first search differ in when a vertex is marked as visited: when it is added or when it is taken out.

7.6 Exercises

Exercise 7.1 (Visiting order by hand) Consider the directed graph in Figure 7.3. Process the successors of each vertex in increasing order of their subscripts.

Code

G = nx.DiGraph()
G.add_edges_from([
    ("v1", "v2"), ("v1", "v3"), ("v2", "v5"), ("v3", "v2"),
    ("v3", "v4"), ("v4", "v5"), ("v4", "v6"), ("v5", "v6"),
])
pos = {
    "v1": (0, 1), "v2": (1, 2), "v3": (1, 0),
    "v5": (2, 2), "v4": (2, 0), "v6": (3, 1),
}
draw_graph(G, pos, 3.6, 2.4)

A directed graph with six vertices drawn as circles labeled v1 to v6. v1 is at the left, v2 and v5 are in the top row, v3 and v4 are in the bottom row, and v6 is at the right. The edges are v1 to v2, v1 to v3, v2 to v5, v3 to v2, v3 to v4, v4 to v5, v4 to v6, and v5 to v6. — Figure 7.3: A directed graph with six vertices.

Apply Algorithm 1 with start vertex v_1. Show the queue Q as in Table 7.1, and give the order in which the vertices are visited.
Apply Algorithm 2 with start vertex v_1. Show the stack L as in Table 7.2, and give the order in which the vertices are visited. Which vertex is pushed more than once?
Check your answers with bfs() and dfs().