Java Reference
In-Depth Information
10
10
7
5
6
8
5
8
10
8
5
5
8
7
7
7
7
12
(a)
(b)
6
6
5
5
7
8
7
5
5
7
7
8
(c)
(d)
F
IGURE
29.5
The trees in (c) and (d) are minimum spanning trees of the graph in (a).
L
ISTING
29.4
Prim's Minimum Spanning Tree Algorithm
Input: A connected undirected weighted G = (V, E) with non-negative weights
Output: MST (a minimum spanning tree)
1 MST minimumSpanningTree() {
2 Let T be a set for the vertices in the spanning tree;
3 Initially, add the starting vertex to T;
4
5
while
(size of T < n) {
6 Find u in T and v in V - T with the smallest weight
7 on the edge (u, v), as shown in Figure 29.6;
8 Add v to T and set parent[v] = u;
9 }
10 }
add initial vertex
more vertices?
find a vertex
add to tree
Vertices already in
the spanning tree
Vertices not currently in
the spanning tree
V
-
T
T
v
u
F
IGURE
29.6
Find a vertex
u
in
T
that connects a vertex
v
in
V - T
with the smallest weight.
The algorithm starts by adding the starting vertex into
T
. It then continuously adds a vertex
(say
v
) from
V - T
into
T
.
v
is the vertex that is adjacent to the vertex in
T
with the smallest
weight on the edge. For example, there are five edges connecting vertices in
T
and
V - T
as
example
Search WWH ::
Custom Search