DOC PREVIEW
Penn CIT 594 - Spanning Trees

This preview shows page 1-2-3-4 out of 13 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Spanning TreesSpanning treesFinding a spanning treeMinimizing costsMinimum-cost spanning treesFinding spanning treesKruskal’s algorithmPrim’s algorithmMazesMazes as spanning treesBuilding a maze IBuilding a maze IIThe EndSpanning Trees2Spanning 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 cyclesA connected,undirected graphFour of the spanning trees of the graph3Finding 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 itAn undirected graphOne possible result of a BFSstarting from topOne possible result of a DFSstarting from top4Minimizing 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 tree5Minimum-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 costA BE DF C161921 113314181065A connected, undirected graphA BE DF C16111865A minimum-cost spanning tree6Finding 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 edges7Kruskal’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 course8Prim’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 algorithm9MazesTypically,Every location in a maze is reachable from the starting locationThere is only one path from start to finishIf the cells are “vertices” and the open doors between cells are “edges,” this describes a spanning treeSince there is exactly one path between any pair of cells, any cells can be used as “start” and “finish”This describes a spanning tree10Mazes as spanning treesThere is exactly one cycle-free path from any node to any other nodeWhile not every maze is a spanning tree, most can be represented as suchThe nodes are “places” within the maze11Building a maze IThis algorithm requires two sets of cellsthe set of cells already in the spanning tree, INthe set of cells adjacent to the cells in the spanning tree (but not in it themselves), called the FRONTIERStart with all walls presentPick any cell and put it into IN (red)• Put all adjacent cells, that aren’t in IN, into FRONTIER (blue)12Building a maze IIRepeatedly do the following:Remove any one cell C from FRONTIER and put it in INErase the wall between C and some one adjacent cell in INAdd 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 cells13The


View Full Document

Penn CIT 594 - Spanning Trees

Documents in this Course
Trees

Trees

17 pages

Searching

Searching

24 pages

Pruning

Pruning

11 pages

Arrays

Arrays

17 pages

Stacks

Stacks

30 pages

Recursion

Recursion

25 pages

Hashing

Hashing

24 pages

Recursion

Recursion

24 pages

Graphs

Graphs

25 pages

Storage

Storage

37 pages

Trees

Trees

21 pages

Arrays

Arrays

24 pages

Hashing

Hashing

24 pages

Recursion

Recursion

25 pages

Graphs

Graphs

23 pages

Graphs

Graphs

25 pages

Stacks

Stacks

25 pages

Recursion

Recursion

25 pages

Quicksort

Quicksort

21 pages

Quicksort

Quicksort

21 pages

Graphs

Graphs

25 pages

Recursion

Recursion

25 pages

Searching

Searching

24 pages

Counting

Counting

20 pages

HTML

HTML

18 pages

Recursion

Recursion

24 pages

Pruning

Pruning

11 pages

Graphs

Graphs

25 pages

Load more
Download Spanning Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Spanning Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Spanning Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?