Spanning tree and minimum spanning tree
A spanning tree in a connected graph is a subgraph consisting of all the vertices and some edges. So, a subgraph is a tree; it is a connected graph with no loops or cycles. Figure 5 shows an example of a spanning tree in a graph:
Figure 5. A spanning tree of a graph (shown in red)
A tree has minimum number of edges required to keep the vertices connected. Removing any edge from a tree will disconnect the graph. This can be useful in a map of roads that connect different places and has a minimal number of roads. With this motivation, we would really be interested in a spanning tree that has a minimum total length ...
Get Java 9 Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
