Spanning TreesSpanning treesFinding a spanning treeMinimizing costsMinimum-cost spanning treesKruskal’s algorithmPrim’s algorithmMazesMazes as spanning treesBuilding a maze IBuilding a maze IIThe EndSpanning Trees2Spanning treesSuppose you have a connected undirected graphConnected: every node is reachable from every other nodeUndirected: edges do not have an associated direction...then a spanning tree of the graph is a connected subgraph in which there are no cyclesA connected,undirected graphFour of the spanning trees of the graph3Finding a spanning treeTo 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 itAn undirected graphOne possible result of a BFSstarting from topOne possible result of a DFSstarting from top4Minimizing costsSuppose you want to supply a set of houses (say, in a new subdivision) with:electric powerwatersewage linestelephone linesTo 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 apartTo reduce costs even further, you could connect the houses with a minimum-cost spanning tree5Minimum-cost spanning treesSuppose you have a connected undirected graph with a weight (or cost) associated with each edgeThe cost of a spanning tree would be the sum of the costs of its edgesA minimum-cost spanning tree is a spanning tree that has the lowest costA BE DF C161921 113314181065A connected, undirected graphA BE DF C16111865A minimum-cost spanning tree6Kruskal’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 edgesEfficient testing for a cycle requires a fairly complex algorithm (UNION-FIND) which we don’t cover in this course7Prim’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 queueTesting for a cycle is automaticHence, Prim’s algorithm is far simpler to implement than Kruskal’s algorithm8MazesTypically,Every location in a maze is reachable from the starting locationThere is only one path from start to finishIf the cells are “vertices” and the open doors between cells are “edges,” this describes a spanning treeSince there is exactly one path between any pair of cells, any cells can be used as “start” and “finish”This describes a spanning tree9Mazes as spanning treesThere is exactly one cycle-free path from any node to any other nodeWhile not every maze is a spanning tree, most can be represented as suchThe nodes are “places” within the maze10Building a maze IThis algorithm requires two sets of cellsthe set of cells already in the spanning tree, INthe set of cells adjacent to the cells in the spanning tree (but not in it themselves), called the FRONTIERStart with all walls presentPick any cell and put it into IN (red)• Put all adjacent cells, that aren’t in IN, into FRONTIER (blue)11Building a maze IIRepeatedly do the following:Remove any one cell C from FRONTIER and put it in INErase the wall between C and some one adjacent cell in INAdd to FRONTIER all the cells adjacent to C that aren’t in IN (or in FRONTIER already) • Continue until there are no more cells in FRONTIER• When the maze is complete (or at any time), choose the start and finish cells12The
View Full Document