Minimum spanning Tree

and Shortest Path

Algorithm
 GRAPHS(1)

• A graph G consists of 2 set V and E .The set V is a finite , non empty set of
vertices .The set E is a set of pairs vertices; theses pair are called Edge.
V(G) -> Set of Vertices
E(G) -> Set of Edges
G=(V,E) to represent a graph
• Undirected Graph :
The pair of vertices representing an edge is unordered. Thus the pair ( u, v) and
(v ,u) represent the same edge.
U

E1 E2

X
V
E3

E4 E5
Y
 GRAPHS(2)
• Directed graph:
• Each edge is represent by direct pair <U ,V>.
• U is the tail and V is the head of the edges.
• <U,V> and <V, U> are 2 different edges.

1 V(G) = { 1,2,3,4}
E(G) = { {1,2},{1,3},{1,4}
(2,1},{2,3},{2,4}
{3,1},{3,2},{3,4}
2 3 {4,1},{4,2},{4,3}
}

• SELF EDGE: if a graph having edge from a vertices V to

• itself.

V
 GRAPHS(3)
• Complete Graph:
if an undirected graph of n vertices consists of n(n-1)/2 number of edges then it is called
as complete graph.

2
V V
=4(4-1)/2
! 2
=4*3/2
1 5 6 3 12/2=6

V 4 V
3 4
• Sub Graph :
if Sub graph ‘G’ of graph such that the set of vertices and set of edges of G’ are proper
subset of the of edges of G’.

v v
1 1

v v
v
2 3 2
 GRAPHS(4)
• Connected Graph:
An undirected graph is said to be connected if for every pair of vertices Vi & Vj in V(G),
there is edge from Vi to Vj in G.

v
1

v v
2 3

v
4
v
• Unconnected graph: 1
v
4

v
v
2
3
 GRAPHS(5)
• Biconnectivity :
A Connected undirected graph is biconnected if there are no vertices whose removal
disconnects the rest of the graph.
If a graph is not biconnected, the vertices whose removal would disconnect the graph are
known are as articulation points.
v v
B A
1 3
v
AP
5
C D v v
2 4
articult pt Biconnected Graph
F
G
E
 GRAPHS(6)
• Properties of BiConnected Graph:

- There are 2 disjoint path between any 2 vertices.

- There exists simple cycle between 2 vertices.
- There should not be any cut vertex.

1 2 3 4

1 1 0
v 1 0
Representation of Graph:
Adjacency Matrix 1 0 0 1
1
2

v v 1 0 0 1
3
2 3
0 0
v 1 1
4
3 1
1 4 2
0
2 4
1 3 2 3
0
3 4
1 2
0
4 1
2 3 4
0
 GRAPHS(7)
• The degree of a vertex is the number of edge incident to that vertex

- indegree -> the number of edges toward the vertices

- outdegree -> the numder of edges leaving the vertices
• For a Directed graph the row sum is the out degree and the column sum is the indegree
[Adjacency Matrix ]
If the edge of a graph has a WEIGHT assigned to them then it is called weighted graph.
2
A C

5 6 2

B D
3 A B c D

0 1 1 0
A

B 0 0 1 1

0 0 0 0
C
D 0 0 1 0
 Minimum Spanning Tree
• Every node in the network must be included in the spanning
tree.
• The overall edge weight of the spanning tree is minimum
possible that will allow the existence of a path between any 2
node in the tree.
• The minimum spanning tree is a tree because it is acyclic, it is
spanning because it covers every vertex and it is minimum
• The number of edges in the minimum spanning tree is |V| -1
• Two algorithm for MST
• Prim’s Algorithm
• Kruskal’s Algorithm
 Example
2
V1 V2 10
4 3 A Graph G
1 7
V5
V3 2 V4
4
8 6
5 V6 V7

1
2
V1 V2

2 V5
V3 V4
4 6
Minimum Spanning
1
Tree
V6 V7
 Prim’s Algorithm
• Initial configuration of V Known dv pv
table used
V1 0 ∞ 0
• Dv : Is the weight of the V2 0 ∞ 0
shortest arc connecting
V to a known Vertex V3 0 ∞ 0
• Pv Is the last vertex to V4 0 ∞ 0
cause a change in dv
V5 0 ∞ 0
V6 0 ∞ 0
V7 0 ∞ 0
 Prim’s Algorithm .. cont

The table after V1 is The table after V4 is

declared known declared known
V Known dv pv V Known dv pv
V1 1 0 0 V1 1 0 0
V2 0 2 V1 V2 0 2 V1
V3 0 4 V1 V3 0 2 V4
V4 0 1 V1 V4 1 1 V1
V5 0 ∞ 0 V5 0 7 V4
V6 0 ∞ 0 V6 0 8 V4
V7 0 ∞ 0 V7 0 4 V4
 Prim’s Algorithm .. cont
The table after V2 and V3
declared known The table after V7 is
declared known
V Known dv pv V Known dv pv
V1 1 0 0 V1 1 0 0
V2 1 2 V1 V2 1 2 V1
V3 1 2 V4 V3 1 2 V4
V4 1 1 V1 V4 1 1 V1
V5 0 7 V4 V5 0 6 V7
V6 0 5 V3 V6 0 1 V7
V7 0 4 V4 V7 1 4 V4
 Prim’s Algorithm .. cont
The table after V6 and V5
are selected

V Known dv pv
V1 1 0 0
V2 1 2 V1
V3 1 2 V4
V4 1 1 V1
V5 1 6 V7
V6 1 1 V7
V7 1 4 V4
 Prim’s Algorithm .. cont
V1 V2 V1 V2

1
V5 V5
V3 V4 V3 V4

V6 V7 V6 V7

2 2
V1 V2 V1 V2
1 1
V5
2 V5
V3 V4 V3 V4

V6 V7 V6 V7
 2
V1 V2 10
4 3
1 7
V5
V3 2 V4
4
8 6
5 V6 V7

1
 Prim’s Algorithm .. cont

2 2
V1 V2 V1 V2
1 1
2 V5 2
V3 V4 V5
4 V3 V4
4
V6 V7 V6
1 V7

2
V1 V2
1
2 V5
V3 V4
4
6
V6
1 V7
 2
V1 V2 10
4 3
1 7
V5
V3 2 V4
4
8 6
5 V6 V7

1
 Kruskal’s Algorithm
A Second greedy strategy is continually to select the edges in order of smallest
weight and accept an edge if it does not cause a cycle
V1 V2
Edge Weight Action
(V1,V4) 1 Accepted
V5
V3 V4
(V6,V7) 1 Accepted

(V1,V2) 2 Accepted
V6 V7

(V3,V4) 2 Accepted

(V2,V4) 3 Rejected

(V1,V3) 4 Rejected V1
1
V2

(V4,V7) 4 Accepted 1

(V3,V6) 5 Rejected V3 2 V4 V5

4 6
(V5,V7) 6 Accepted
1
V6 V7
Practice problem
 Shortest path Algorithm
➢Obtain the minimum distance between two node
➢There are weighted and un weighted graph
Unweighted shortest path
➢Gives a path in unweighted graph which is equal to number of edges traveled from
source to destination

V2 V3 S.no Path No.of.edges

1 V1-V2-V3-V10 3
V10 2 V1-V4-V5-V6-V10 4
V1 V4 V5 V6
3 V1-V7-V8-V9-V10 4

V7 V8 V9

Out of these the path 1 i.e V1-V2-V3-V10 is

shortest one
 Dijkstra’s shortest path algorithm
Single-source shortest path problem:
Given as input a weighted graph G=(V,E) & a distinguished vertex, s. Find shortest
path from s to every other vertex in G.
Step1:
1
V1 V2
3 10
4 1
V Known Dv Pv
2
2 V5
V3 V4 V1 0 0 0
4
8 6
5
V2 0 ∞ 0
1
V6 V7
V3 0 ∞ 0

V4 0 ∞ 0

V5 0 ∞ 0

V6 0 ∞ 0

V7 0 ∞ 0
Intial configuration of table used in Dijkstra’s algorithm
 Step2: Step3:
V Known Dv Pv V Known Dv Pv

V1 1 0 0 V1 1 0 0

V2 0 2 V1 V2 0 2 V1

V3 0 ∞ 0 V3 0 3 V4

V4 0 1 V1 V4 1 1 V1

∞ V5 0 3 V4
V5 0 0

V6 0 9 V4
V6 0 ∞ 0
V7 0 5 V4
V7 0 ∞ 0

After V1 is declared known After V4 is declared

known
Step 4: Step 5:
V Known Dv Pv V Known Dv Pv

V1 1 0 0 V1 1 0 0

V2 1 2 V1 V2 1 2 V1

V3 0 3 V4 V3 1 3 V4

V4 1 1 V1 V4 1 1 V1

V5 0 3 V4 V5 1 3 V4

V6 0 9 V4 V6 0 8 V3

V7 0 5 V4 V7 0 5 V4

After V2 is declared After V5 & V3 are declared

known known
Step 6:
V Known Dv Pv

V1 1 0 0

V2 1 2 V1 2
V1 V2

V3 1 3 V4 1

2
2 V5
V4 1 1 V1 V3 V4
4
V5 1 3 V4
1
V6 V7
V6 0 6 V7

V7 1 5 V4

After V7 is declared
known