3.4 Spanning Trees

Spanning trees

• Suppose you have a connected undirected graph
• Connected: every node is reachable from every other node
• Undirected: edges do not have an associated direction
• ...then a spanning tree of the graph is a connected subgraph in which there are no cycles

2

Finding a spanning tree

• To find a spanning tree of a graph,
• pick an initial node and call it part of the spanning tree
• do a search from the initial node:
• each time you find a node that is not in the spanning tree, add to the spanning tree both the new node and the edge you followed to get to it

3

Minimizing costs

• Suppose you want to supply a set of houses (say, in a new subdivision) with:
• electric power
• water
• sewage lines
• telephone lines
• To keep costs down, you could connect these houses with a spanning tree (of, for example, power lines)
• However, the houses are not all equal distances apart
• To reduce costs even further, you could connect the houses with a minimum-cost spanning tree

4

Minimum-cost spanning trees

• Suppose you have a connected undirected graph with a weight (or cost) associated with each edge
• The cost of a spanning tree would be the sum of the costs of its edges
• A minimum-cost spanning tree is a spanning tree that has the lowest cost

5

Finding spanning trees

• There are two basic algorithms for finding minimum-cost spanning trees, and both are greedy algorithms�
• Kruskal’s algorithm: Start with no nodes or edges in the spanning tree, and repeatedly add the cheapest edge that does not create a cycle
• Here, we consider the spanning tree to consist of edges only�
• Prim’s algorithm: Start with any one node in the spanning tree, and repeatedly add the cheapest edge, and the node it leads to, for which the node is not already in the spanning tree.
• Here, we consider the spanning tree to consist of both nodes and edges

6

Kruskal’s algorithm

• T = empty spanning tree;�E = set of edges;�N = number of nodes in graph;
• while T has fewer than N - 1 edges {
• remove an edge (v, w) of lowest cost from E
• if adding (v, w) to T would create a cycle
• then discard (v, w)
• else add (v, w) to T
• }
• Finding an edge of lowest cost can be done just by sorting the edges
• Efficient testing for a cycle requires a fairly complex algorithm (UNION-FIND) which we don’t cover in this course

7

Prim’s algorithm

• T = a spanning tree containing a single node s;�E = set of edges adjacent to s;�while T does not contain all the nodes {
• remove an edge (v, w) of lowest cost from E
• if w is already in T then discard edge (v, w)
• else {
• add edge (v, w) and node w to T
• add to E the edges adjacent to w
• }
• }
• An edge of lowest cost can be found with a priority queue
• Testing for a cycle is automatic
• Hence, Prim’s algorithm is far simpler to implement than Kruskal’s algorithm

8