Java Reference
In-Depth Information
figure 14.17
The graph after all the
vertices whose path
length from the
starting vertex is 1
have been found
1
V
0
V
1
0
V
2
V
3
V
4
1
V
5
V
6
Next, we find each vertex whose shortest path from
S
is exactly 2. We do
so by finding all the vertices adjacent to or (the vertices at distance 1)
whose shortest paths are not already known. This search tells us that the short-
est path to and is 2. Figure 14.18 shows our progress so far.
Finally, by examining the vertices adjacent to the recently evaluated
and ,we find that and have a shortest path of 3 edges. All vertices have
now been calculated. Figure 14.19 shows the final result of the algorithm.
This strategy for searching a graph is called
breadth-first search,
which
operates by processing vertices in layers: Those closest to the start are evalu-
ated first, and those most distant are evaluated last.
V
0
V
5
V
1
V
3
V
1
V
3
V
4
V
6
Breadth-first search
processes vertices
in layers: Those
closest to the start
are evaluated first.
figure 14.18
The graph after all the
vertices whose
shortest path from the
starting vertex is 2
have been found
1
2
V
0
V
1
2
0
V
2
V
3
V
4
1
V
5
V
6
figure 14.19
The final shortest
paths
1
2
V
0
V
1
0
2
3
V
2
V
3
V
4
3
1
V
5
V
6
Search WWH ::
Custom Search