Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim's and Kruskal Algorithms - Coggle Diagram
Prim's and Kruskal Algorithms
Greedy Techniques
"
on each step, it suggests a “greedy” grab of the best alternative available in the hope that a sequence of locally optimal choices will yield a (globally) optimal solution to the entire problem
"
minimum spanning tree problem
minimum spanning tree problem is the problem of
finding a minimum spanning tree for a given weighted connected graph
A
spanning tree
: connected acyclic subgraph that contains all the vertices of the graph
Prim's Algorithm
The initial subtree in such a sequence consists of a single vertex selected arbitrarily from the set V of the graph’s vertices. On each iteration, the algorithm expands the current tree in the greedy manner by simply attaching to it the nearest vertex not in that tree
Look at
fringe
unseen
For every node:
find a minimum-weight edge e^∗ = (v^∗, u^∗) among all the edges (v, u) such that v is in V_T and u is in V − V_T
Time Efficiency
O(|E| log |V|)
If implemented as adjacency list and min-heap for priority queue
Kruskal Algorithm
Key notes:
It is not difficult to see that a new cycle is created if and only if the new edge connects two vertices already connected by a path, i.e., if and only if the two vertices belong to the same connected component
The algorithm begins by sorting the graph’s edges in nondecreasing order of their weights. Then, starting with the empty subgraph, it scans this sorted list, adding the next edge on the list to the current subgraph if such an inclusion does not create a cycle and simply skipping the edge otherwise.
Time efficiency
O(|E| log |V|)
