IntroductionSpanning TreesComputing a Spanning TreeCreating a Random MazeMinimum Weight Spanning TreesLecture Notes onSpanning Trees15-122: Principles of Imperative ComputationFrank PfenningLecture 24November 18, 20101 IntroductionIn this lecture we introduce graphs. Graphs provide a uniform model formany structures, for example, maps with distances or Facebook relation-ships. Algorithms on graphs are therefore important to many applications.They will be a central subject in the algorithms courses later in the curricu-lum; here we only provide a very small sample of graph algorithms.2 Spanning TreesWe start with undirected graphs which consist of a set V of vertices (alsocalled nodes) and a set E of edges, each connecting two different vertices.A graph is connected if we can reach any vertex from any other vertexby following edges in either direction. In a directed graph edges provide aconnection from one node to another, but not necessarily in the oppositedirection. More mathematically, we say that the edge relation between ver-tices is symmetric for undirected graphs. In this lecture we only discussundirected graphs, although directed graphs also play an important role inmany applications.The following is a simple example of a connected, undirected graphLECTURE NOTES NOVEMBER 18, 2010Spanning Trees L24.2with 5 vertices (A, B, C, D, E) and 6 edges (AB, BC, CD, AE, BE, CE).D"E"C"B"A"In this lecture we are particularly interested in the problem of computinga spanning tree for a connected graph. What is a tree here? They are abit different than the binary search trees we considered early. One simpledefinition is that a tree is a connected graph with no cycles, where a cycle let’syou go from a node to itself without repeating an edge. A spanning tree fora connected graph G is a tree containing all the vertices of G. Below aretwo examples of spanning trees for our original example graph.D"E"C"B"A"D"E"C"B"A"When dealing with a new kind of data structure, it is a good strategy totry to think of as many different characterization as we can. This is some-what similar to the problem of coming up with good representations of thedata; different ones may be appropriate for different purposes. Here aresome alternative characterizations the class came up with:1. Connected graph with no cycle (original).2. Connected graph where no two neighbors are otherwise connected.Neighbors are vertices connected directly by an edge, otherwise con-nected means connected without the connecting edge.LECTURE NOTES NOVEMBER 18, 2010Spanning Trees L24.33. Two trees connected by a single edge. This is a recursive characteriza-tion. The based case is a single node, with the empty tree (no vertices)as a possible special case.4. A connected graph with exactly n − 1 edges, where n is the numberof vertices.5. A graph with exactly one path between any two distinct vertices,where a path is a sequence of distinct vertices where each is connectedto the next by an edge.When considering the asymptotic complexity it is often useful to cate-gorize graphs as dense or sparse. Dense graphs have a lot of edges comparedto the number of vertices. Writing n = |V | for the number of vertices (whichwill be our notation in the rest of the lecture) know there can be at mostn ∗ (n − 1)/2: every node is connected to any other node (n ∗ (n − 1)), but inan undirected way (n ∗(n− 1)/2). If we write e for the number of edges, wehave e = O(n2). By comparison, a tree is sparse because e = n − 1 = O(n).3 Computing a Spanning TreeThere are many algorithms to compute a spanning tree for a connectedgraph. The first is an example of a vertex-centric algorithm.1. Pick an arbitrary node and mark it as being in the tree.2. Repeat until all nodes are marked as in the tree:(a) Pick an arbitrary node u in the tree with an edge e to a node wnot in the tree. Add e to the spanning tree and mark w as in thetree.We iterate n − 1 times in Step 2, because there are n−1 vertices that have tobe added to the tree. The efficiency of the algorithm is determined by howefficiently we can find a qualifying w.The second algorithm is edge-centric.1. Start with the collection of singleton trees, each with exactly one node.2. As long as we have more than one tree, connect two trees togetherwith an edge in the graph.LECTURE NOTES NOVEMBER 18, 2010Spanning Trees L24.4This second algorithm also performs n steps, because it has to add n − 1edges to the trees until we have a spanning tree. Its efficiency is determinedby how quickly we can tell if an edge would connect two trees or wouldconnect two nodes already in the same tree, a question we come back to inthe next lecture.Let’s try this algorithm on our first graph, considering edges in thelisted order: (AB, BC, CD, AE, BE, CE).D"E"C"B"A" D"E"C"B"A" D"E"C"B"A" D"E"C"B"A"D"E"C"B"A" D"E"C"B"A"The first graph is the given graph, the completley disconnected graph is thestarting point for this algorithm. At the bottom right we have computed thespanning tree, which we know because we have added n − 1 = 4 edges. Ifwe tried to continue, the next edge BE could not be added because it doesnot connect two trees, and neither can CE. The spanning tree is complete.4 Creating a Random MazeWe can use the algorithm to compute a spanning tree for creating a randommaze. We start with the graph where the vertices are the cells and theedges represent the neighbors we can move to in the maze. In the graph,all potential neighbors are connected. A spanning tree will be defined by asubset of the edges in which all cells in the maze are still connected by some(unique) path. Because a spanning tree connects all cells, we can arbitrarilydecide on the starting point and end point after we have computed it.LECTURE NOTES NOVEMBER 18, 2010Spanning Trees L24.5How would we ensure that the maze is random? The idea is to gener-ate a random permutation (see Exercise 1) of the edges and then considerthe edges in the fixed order. Each edge is either added (if it connects twodisconnected parts of the maze) or not (if the two vertices are already con-nected).5 Minimum Weight Spanning TreesIn many applications of graphs, there is some measure associated with theedges. For example, when the vertices are locations then the edge weightscould be distances. We might then be interested in not any spanning tree,but one whose total edge weight is minimal among all the possible span-ning trees, a so-called minimum weight spanning tree (MST). An