31251 Lecture Notes - Lecture 5: Counting Sort, Ackermann Function, Radix Sort
30 Jun 2018
School
Department
Course
Professor
Minimum Spanning Trees
Spanning Trees
A subgraph is a subset of the vertices and edges of a graph that form a graph.
A subgraph is spanning if it includes all the vertices of the original graph.
A spanning subgraph is a spanning tree if it contains no cycles.
A spanning tree is a minimum spanning tree if it has minimum total (edge) weight over all
possible spanning trees of that graph (is it unique?).
In unweighted graphs (or a graph where all edge weights are the same), any spanning tree is
a minimum spanning tree.
We can compute one from a depth-first or breadth-first traversal.
df_spanning_tree(Vertex v, Tree t){
mark v as visited;
for each neighbour u of v{
if (u is unmarked)
add edge vu to t;
dft(u,t);
}
}
Prim’s Algorithm
Given a connected graph G
1 Pick a starting vertex v (however you want), add v to the partially complete tree T.
2 While |T| < n
1 Let E 0 be the set of edges uv where u ∈ T and v ∈ G \ T.
2 Let uv be the edge of smallest weight in n E’.
3 Add uv to the edges of T and v to the vertices of T.
3 Return T.
In other words:
Keep track of which edges and vertices are in the tree.
Pick the next smallest edge that extends the tree, add it.
1 | P a g e
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
A subgraph is a subset of the vertices and edges of a graph that form a graph. A subgraph is spanning if it includes all the vertices of the original graph. A spanning subgraph is a spanning tree if it contains no cycles. In unweighted graphs (or a graph where all edge weights are the same), any spanning tree is a minimum spanning tree. We can compute one from a depth-first or breadth-first traversal. df_spanning_tree(vertex v, tree t){ mark v as visited; for each neighbour u of v{ if (u is unmarked) add edge vu to t; dft(u,t); 1 pick a starting vertex v (however you want), add v to the partially complete tree t. 1 let e 0 be the set of edges uv where u t and v g \ t. 2 let uv be the edge of smallest weight in n e". 3 add uv to the edges of t and v to the vertices of t.
