Wallaga University
College of Natural and Computational Science
Department of Mathematics
Graph Theory and Algorithm
Presentation Topic :
Algorithms to Determining Minimum Spanning Tree
With Examples
By: Dugassa Bekele
January 16, 2025
Preminary Concepts
Undirected graph: A graph with edges that do not have an associated direction.
Tree: tree is a connected acyclic graph.
Spanning Tree: is a tree that contains every vertices of a connected graph.
If graph G is connected graph with n vertices and e edges ,then
the spanning tree of graph G must have:
n-1 edges and the number of edges deleted from the graph to
obtain the spanning tree is equal to e-n+1.
Cont..
Weighted Graph: A graph with weight(values) associated with each edges.
Minimum spanning Tree: The minimum spanning tree of weighted, connected,
undirected graph G is a graph T consists of all vertices of graph G together with
enough edges of such that:
I. T is connected
II. T is acyclic
III. T has Minimal weight
Example: Consider the graph given below:
Algorithms to determine Minimum Spanning Trees
• There are basic algorithms for finding minimum-
weighted spanning tree such as:
Kruskal’s Algorithm
Prim’s Algorithm
Reverse-Deletion Algorithm
Kruskal’s Algorithm: Start with no vertices or edges in the spanning
tree, and repeatedly add the smallest weight edge that does not
create a cycle.
In this algorithm ,we provide the spanning tree to consists of edge
only.
Cont…
Algorithm Of Kruskal’s
1: Input : A connected weighted graph G // G = (V, E,w)
2: Output :A minimum spanning tree T // MST T of G
3: T ← Ø
4: Q ←sorted edges in non-decreasing weights of E
5: while Q = Ø do \\continue until all edges are checked
6: pick an edge (u, v) from Q
7: if (u, v) does not make a cycle with vertices in T then
8: add (u, v) to T
9: end if
10: end while
Thus, finding an edge of smallest weighted can be done just by sorting the edges.
Cont…
Example of Kruskal’s Algorithm
Consider the undirected weighted graph given
below:
None of the edges are highlighted
Cont…
1. AD and CE are the
smallest edges , with
length 5, and AD has
been arbitrary chosen
and it highlighted
2. CE is now the smallest
edge that does not
form a cycle with length
5, and it is highlighted
as second edge
Cont…
3. The next smallest edge is DF
with length 6 and it is highlighted.
4. The next smallest edges are
AB and BE with the same length 7
and AB is chosen arbitrary and it
is highlighted.
Here the edge BD has been
highlighted by red, b/c if it were
chosen it would form a cycle
(ABD)
Cont…
5. The process continues
highlighted the next smallest edge
BE with length 7.Here many more
edges are highlighted in red at this
stage: BC b/c it forms a cycle BCE, DE
it forms a cycle DEBA, and FE b/c it
forms a cycle FEBAD.
6. Finally, the process finishes with
the edge EG of length 9, and it
highlighted.
Thus, the minimum spanning tree is
obtained with edges highlighted in
green and it has weight 39.
Prim’s Algorithm
Prim’s Algorithm: start with any one vertex in
the spanning tree, and rapidly add the
smallest weight edge, and the vertex it leads
to, for which the vertex is not already in the
spanning tree.
In this algorithm, we consists of both vertices
and edges.
Cont…
Algorithm Of Prim’s
1: Input : G(V, E, w)
2: Output : MST T (V, ET ) of G
3: VT ← {s} // s is the vertex selected
4: T ← Ø
5: while VT = V do // continue until all vertices are visited
6: select the edge (u, v) with minimal weight such that u ∈ T
and v ∈ G \ T
7: VT ← VT ∪ {v}
8: ET ← ET ∪ {(u, v)}
9: end while
Cont..
Example Of Prim’s Algorithm
This our original weighted graph given.
Cont…
Cont…
Cont…
Reverse-Deletion Algorithm
Reverse-Deletion Algorithm: we can start with all edges of the
graph and delete edges that will never be included in the MST
until we have a connected graph that has the tree property.
I t is acyclic or has n − 1 edges.
We delete edges in the order of decreasing weights as long as
removal of a such edge does not disconnect the graph since
any bridge of the graph should be contained in the MST.
Cont…
Reverse-Delete Algorithm
1: Input: An undirected weighted graph G = (V, E, w)
2: Output: An MST T of G
3: Sort edges of G in non-decreasing order into Q
4: Let T = G
5: Repeat
6: Dequeue the first edge (u, v) from Q
7: Remove (u, v) from T
8: If such removal leaves T disconnected then
9: Join (u, v) to T
10: Until Q = Ø
Cont…
Example Of Reverse-Delete
Cont…
.
THANK YOU FOR ATTENTION!
