Graphs - DAA
Graphs - DAA
Graphs - DAA
Consider the above weighted graph and solve using all pair shortest path
(Floyd Warshall’s Algorithm)
MINIMUM
SPANNING
TREE
▪ An undirected graph is a graph in which the edges do not point in any direction (ie. the edges
are bidirectional).
▪ A connected graph/Directed graph is a graph in which there is always a path from a vertex to
any other vertex.
SPANNING TREE
▪ A spanning tree is a sub-graph of an undirected connected graph, which includes all the
vertices of the graph with a minimum possible number of edges. If a vertex is missed, then it
is not a spanning tree.
▪ The edges may or may not have weights assigned to them.
▪ The total number of spanning trees with n vertices that can be created from a complete graph
is equal to n(n-2).
▪ If we have n = 4, the maximum number of possible spanning trees is equal to 4 4-2 = 16 . Thus, 16
spanning trees can be formed from a complete graph with 4 vertices.
Spanning Tree Applications
• Computer Network Routing Protocol
• Cluster Analysis
• Civil Network Planning
▪ Let the original graph be:
▪ Some of the possible spanning trees that can be created from the above graph are:
▪ A minimum spanning tree is a spanning tree in which the sum of the weight of the edges is as
minimum as possible.
Applications:
• To find paths in the map
• To design networks like telecommunication networks, water supply networks, and electrical
grids.
▪ The initial graph is:
▪ The possible spanning trees from the above graph are:
▪ The minimum spanning tree from the above spanning trees is:
Find the minimum cost spanning Tree
• Kruskal’s Algorithm is a famous greedy algorithm.
• It is used for finding the Minimum Spanning Tree (MST) of a given graph.
• To apply Kruskal’s algorithm, the given graph must be weighted, connected and undirected.
[no cycles]
1 2 3
Sort all the edges from low weight - Take the edge with the lowest Keep adding edges until all the
to high weight. weight and use it to connect the vertices are connected and a
vertices of graph. Minimum Spanning Tree (MST) is
- If adding an edge creates a cycle, obtained.
then reject that edge and go for
the next least weight edge
PROBLEMS ON KRUSKAL’S ALGORITHM
▪ Construct the minimum spanning tree (MST) for the given graph using Kruskal’s Algorithm-
To construct MST using Kruskal’s Algorithm,
• Simply draw all the vertices on the paper.
• Connect these vertices using edges with minimum weights such that no cycle gets formed
Since all the vertices have been connected /
included in the MST, so we stop.
Weight of the MST
= Sum of all edge weights
= 10 + 25 + 22 + 12 + 16 + 14
= 99 units
▪ Prim's algorithm is a minimum spanning tree algorithm that takes a graph as input and finds
the subset of the edges of that graph which form a tree that includes every vertex
• It has the minimum sum of weights among all the trees that can be formed from the graph
HOW PRIM'S ALGORITHM WORKS
It falls under a class of algorithms called greedy algorithms that find the local optimum in the
hopes of finding a global optimum. We start from one vertex and keep adding edges with the
lowest weight until we reach our goal.
The steps for implementing Prim's algorithm are as follows:
1. Initialize the minimum spanning tree with a vertex chosen at random.
2. Find all the edges that connect the tree to new vertices, find the minimum and add it to the
tree
3. Keep repeating step 2 until we get a minimum spanning tree
EXAMPLE OF PRIM'S ALGORITHM
▪ Transitive Closure it the reachability matrix
to reach from vertex u to vertex v of a
graph. One graph is given, we must find a
vertex v which is reachable from another
vertex u, for all vertex pairs (u, v).
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 1
THANK YOU