Java Reference
In-Depth Information
shown in Figure 29.6, and (
u
,
v
) is the one with the smallest weight. Consider the graph in
Figure 29.7. The algorithm adds the vertices to
T
in this order:
1. Add vertex
0
to
T
.
2. Add vertex
5
to
T
, since
Edge(5, 0, 5)
has the smallest weight among all edges inci-
dent to a vertex in
T
, as shown in Figure 29.7a. The arrow line from
0
to
5
indicates that
0
is the parent of
5
.
3. Add vertex
1
to
T
, since
Edge(1, 0, 6)
has the smallest weight among all edges inci-
dent to a vertex in
T
, as shown in Figure 29.7b.
4. Add vertex
6
to
T
, since
Edge(6, 1, 7)
has the smallest weight among all edges inci-
dent to a vertex in
T
, as shown in Figure 29.7c.
1
10
2
1
10
2
T
6
6
7
5
7
5
8
8
0
0
8
10
8
10
6
3
6
3
5
5
7
7
8
7
7
8
T
5
12
5
12
4
4
(a)
(b)
1
10
2
1
10
2
T
T
6
6
7
5
7
5
8
8
0
0
8
10
8
10
6
3
6
3
5
5
7
7
8
7
7
8
5
12
5
12
4
4
(c)
(d)
1
10
2
1
10
2
T
T
6
6
7
5
7
5
8
8
0
0
8
10
8
10
6
3
6
3
5
5
7
7
8
7
7
8
5
12
5
12
4
4
(e)
(f)
F
IGURE
29.7
The adjacent vertices with the smallest weight are added successively to
T
.
Search WWH ::
Custom Search