INB221 Lecture Notes - Binary Logarithm, Adjacency List, Prims
4 Jul 2013
School
Department
Course
Professor
Document Summary
A spanning tree is a special kind of subgraph, where it"s fully connected but there"s no cycles of edges. If you have n vertices, a spanning tree has exactly n-1 edges. There can be a number of spanning trees for any connected graph. But you don"t want any spanning tree, you want to minimize the costs wherever possible. To keep the costs down further, you can use a minimum-cost spanning tree. Place each vertex in its own cluster or set. If e connected two vertices in different clusters, then e is added to the minimum spanning tree and the two clusters connected by e are merged into a single cluster. If e connects two vertices which are already in the same cluster, ignore it. If the edge connects two vertices in its own cluster, that means there"s already a connection, so if there"s another edge there"s a cycle between the two vertices.
