A spanning tree T of an undirected graph is a subgraph that is a tree which includes all of the vertices of G, with no cycles and a minimum amount of edges.
Many pathfinding algorithms build a spanning tree as an intermediary step to finding the minimum spanning tree.
They can be constructed by both graph traversal algorithms taught in 213, breadth first search and depth first search.
Minimum Spanning Tree
The minimum spanning tree is a spanning tree that is minimal by value, usually by the metric of the sum of the weight or width of the vertices of that graph.
This means that generally a minimum spanning tree is only relevant to weighted graphs.
Kruskal’s Algorithm
Maintain a priority queue of the smallest edges. Progressively pop the lowest edges as long as they successfully build a disjoint set. I.e, if the result of a find operation on the two nodes containing the edge is positive (it is already in the built disjoint set), do not add it to the set, pop it off of the pq and keep going. Stop when the number of edges added to the disjoint set is n - 1 edges where n is the amount of vertices.
Prim’s algorithm
Initially builds a spanning tree from one initial vertex. Repeatedly chooses the minimum-weight edge from a vertex in the tree, …
Prim’s algorithm is only maximally efficient when using a heap implementation of a priority queue (as opposed to a sorted array implementation).
Worst case time complexity is:
Where m is the number of edges.
Qs
Why m log m for remove min?
Isn’t m log m always > n a (n)?