Graphs - Data Structures and Abstractions with Java - page 734

In Chapter 23, we examined several orders in which we could visit the nodes of a tree. The preor-
der, inorder, and postorder traversals are examples of a depth-first traversal . This kind of traversal
follows a path that descends the levels of a tree as deeply as possible until it reaches a leaf, as
Figure 28-9a shows. More generally, a depth-first traversal of a graph follows a path that goes as
deeply into the graph as possible before following other paths. After visiting a vertex, this traversal
visits the vertex's neighbor, the neighbor's neighbor, and so on.
The level-order traversal of a tree is an example of a breadth-first traversal . It follows a path
that explores an entire level before moving to the next level, as Figure 28-9b shows. In a graph, a
breadth-first traversal visits all neighbors of a node before visiting the neighbors' neighbors.

VideoNote

Graph operations

FIGURE 28-9

The visitation order of two traversals: (a) depth first;
(b) breadth first

(a) (b)

1

1

8 10 2 3 4 5

2 16

6 11

3 15

9 7 8 9 10

7 11 12

6 14 14

4 5 13 12 13 15 16

Breadth-first traversal

Depth-first traversal

Note: Visiting a node in either a tree or a graph is an action that we perform during a tra-
versal. In a tree, “visit a node” means to “process the node's data.” In a graph, “visit a node”
means simply to “mark the node as visited.”

A traversal of a tree visits all of the tree's nodes beginning with the root. However, a graph tra-
versal begins at any vertex—called the origin vertex —and visits only the vertices that it can reach.
Only when a graph is connected can such a traversal visit all the vertices.

Breadth-First Traversal
28.12

Given an origin vertex, a breadth-first traversal visits the origin and the origin's neighbors. It then
considers each of these neighbors and visits their neighbors. The traversal uses a queue to hold the
visited vertices. When we remove a vertex from this queue, we visit and enqueue the vertex's
unvisited neighbors. The traversal order is then the order in which vertices are added to the queue.
We can retain this traversal order in a second queue.
The following algorithm performs a breadth-first traversal of a nonempty graph beginning at a
given vertex.
Algorithm getBreadthFirstTraversal(originVertex)
traversalOrder = a new queue for the resulting traversal order
vertexQueue = a new queue to hold vertices as they are visited