CSC263H1 Lecture Notes - Lecture 10: Minimum Spanning Tree, Priority Queue, Spanning Tree
18 Oct 2017
School
Department
Course
Professor
Document Summary
Csc 263 lecture summary for week 10 winter 2017. Input: connected, undirected, weighted graph g=(v,e) with weights w(e) for each edge e in e. Output: find a spanning tree of g with smallest total weight. Connected, acyclic subgraph of g -- subset of edges that is connected (at least one path between any two vertices) and acyclic (no simple cycle). If g not connected, generalize to minimum spanning forest. Algorithm idea 1: start with t = e; remove edges until mst remains. A: edges with largest weight whose endpoints are already connected -- in other words, the edge belongs to some cycle. Fact: every tree on n vertices contains exactly n-1 edges. Fact: the maximum number of edges for an undirected graph on n vertices is (n choose 2) = n(n-1)/2. So the algorithm may have to remove omega(n^2) many edges to reach a spanning tree.
