Java Reference
In-Depth Information
Mark
originVertex
as visited
traversalOrder.enqueue(originVertex)
vertexQueue.enqueue(originVertex)
while
(!vertexQueue.isEmpty())
{
frontVertex = vertexQueue.dequeue()
while
(frontVertex
has a neighbor
)
{
nextNeighbor =
next neighbor of
frontVertex
if
(nextNeighbor
is not visited
)
{
Mark
nextNeighbor
as visited
traversalOrder.enqueue(nextNeighbor)
vertexQueue.enqueue(nextNeighbor)
}
}
}
return
traversalOrder
Figure 28-10 traces this algorithm for a directed graph.
Note:
Breadth-first traversal
A breadth-first traversal visits a vertex and then each of the vertex's neighbors before advanc-
ing. The order in which these neighbors are visited is not specified and can depend on the
graph's implementation.
Question 6
In what order does a breadth-first traversal visit the vertices in the graph shown in
Figure 28-10 when you begin at vertex
E
and visit neighbors in alphabetic order?
FIGURE 28-10
A trace of a breadth-first traversal beginning at vertex
A
of a
directed graph
frontVertex nextNeighbor
Visited vertex
vertexQueue traversalOrder
(front to back)
(front to back)
A
A
A
A
D
G
A
empty
B
B
B
AB
D
D
BD
ABD
E
E
BDE
ABDE
B
E
H
B
DE
D
E
G
G
EG
ABDEG
E
G
C
F
I
F
F
GF
ABDEGF
H
H
GFH
ABDEGFH
G
FH
F
H
C
C
HC
ABDEGFHC
H
C
I
I
CI
ABDEGFHCI
C
I
I
empty
