MIT Art Design and Technology University

MIT School of Computing, Pune

21BTCS402-Advanced Data Structures & Algorithms

Class - S.Y. (SEM-II)

Unit - 2 GRAPHS

AY 2023-2024 SEM-II
Lecture 1
 Unit II- Syllabus
• Unit II Graphs
• Basic Concepts
• Storage representation, Adjacency matrix, adjacency list, adjacency
multi list, inverse adjacency list.
• Traversals-depth first and breadth first, Introduction to Greedy Strategy, Minimum
spanning Tree, Greedy algorithms for computing minimum spanning tree- Prim’s
and Kruskal’s Algorithms
• Dijkstra's Single Source shortest path, Topological ordering.
• Case study- Data structure used in Webgraph and Google map
Course Objectives:

• 1. To suggest an appropriate non-linear data structures and algorithm for

graphical solutions
• of the problems.
• 2. To understand the various searching and indexing techniques.
• 3. To suggest appropriate data structure and algorithm for graphical
solutions of the
• problems.
• 4. To learn various file operations relevant to different types of files.
• 5. To develop the logical skills and use of appropriate data structures in
different domains
Contents
◻ Basic concepts
◻ Operations on Graph
◻ Graph Storage Structures
◻ Traversals
⬜ Depth First Search
⬜ Breadth First Search
◻ Graph Algorithms
◻ Graph as ADT
◻ Minimum Spanning Trees
⬜ Kruskal’s and Prims algorithm
◻ Algorithms for shortest path
◻ topological sorting.
◻ Data structure used in Webgraph and Google map
5
 Basic concepts
◻ A graph is collection of nodes called Vertices and collection of
segments called Lines.
◻ Graph G={V,E}
◻ Graphs
⬜ Directed Graph- Each Line has a direction [ARC]
⬜ Undirected Graph- No direction on any line[edges]
◻ Path is a sequence of vertices in which each vertex is adjacent
to next one.
◻ Adjacent vertices if there is a path of length 1 connecting
them.

6
 Continued….
◻ Cycle is a path consisting of at least 3 vertices that starts and ends with the same
vertex.
◻ Loop is special case of cycle in which a single arc begins and ends with the same
vertex.
◻ 2 vertices are said to be connected if there is path between them.
◻ Graph is said to be connected when there is path from any vertex to every other
vertex.
⬜ Strongly connected
⬜ Weakly connected
⬜ Disjoint Graph
◻ Degree of a vertex
7
 Undirected Graph Directed Graph
(the edges are bidirectional) (the edges point in a direction)

Cycle in Graphs Loop in Graphs

8
 A
Weakly Connected Graphs

B E G

C D H I

• A directed graph in which it is possible to reach any node starting from any other node by
traversing edges in some direction.
• The nodes cannot be visited by a single path.
• All components/nodes are connected by some path, ignoring direction.
• A directed graph is weakly connected if the graph is not strongly connected, but the
underlying undirected graph (i.e., considering all edges as undirected) is connected.

9
 A Strongly Connected Graphs

B E G

C D H I

• A directed graph in which, for every vertex v in the graph, there is a path from v to every

other vertex.

• The nodes can be visited by a single path.

10
 A
Disjoint Graphs

B E G

C D H I

Two subgraphs are edge disjoint if they share no edges, and vertex disjoint if they share
no vertices.
12
 Complete Graph (Fully connected Graph)

A complete graph is a graph in which each pair of graph vertices is connected by an edge.

The complete graph with n graph vertices is denoted as Kn and has

n(n-1)/2 (the triangular numbers) undirected edges

13
 Degree of vertex and graph

The degree of a vertex in a graph is its number of incident edges.

The maximum degree of a graph G is the maximum of the degrees of its vertices, denoted as ∆(G)

The minimum degree of G is the minimum of its vertex degrees; denoted as δ(G)

The total degree is the sum of the degrees of all vertices.

The degree sequence is the collection of degrees of all vertices, in sorted order from largest to
smallest.

In a directed graph, one may distinguish the in-degree (number of incoming edges) and out-degree
(number of outgoing edges)

14
 Operations on Graphs
Primitive graph operations
1. Insert a vertex
2. Delete a vertex
3. Add an edge
4. Delete an edge The graph ADT
5. Find a vertex
6. Traverse a graph

15
Continued..
1. Insert Vertex:
⬜ adds new vertex to graph
⬜ When it is inserted it is disjoint

A C A C

Insert Vertex

B B D

16
Continued..
2. Delete Vertex:
⬜ Removes vertex from graph
⬜ When it is removed all connecting edges are also removed

A C A C

Delete Vertex

B D B

D
17
Continued..
3. Add Edge:
⬜ adds edge connects vertex to a destination vertex

A C A C

Add Edge

B D B D

18
Continued..
4. Delete Edge:
⬜ Delete edge from graph

A C A C

Delete Edge

B D B D

19
Continued..
5.Find Vertex
⬜ Traverse Graph looking for a specified vertex.

A C A C

Find Vertex

B D B D

20
Lecture 2
 Storage Structure of a Graph
22

◻ Adjacency-list representation of a graph G = ( V, E ) consists

of an array ADJ of |V | lists, one for each vertex in V. For each u
∈ V , ADJ [ u ] points to all its adjacent vertices.

1 2 5
1 2 2 1 5 3 4
3 3 2 4
5 4 4 2 5 3
5
4 1 2

Linked Representation
 Adjacency-list representation for a directed graph.
23

1 2 5
1 2 2 5 3 4
3 3 4
5 4 4 5
5
5
 Adjacency lists
24

◻ Advantage:
⬜ Saves space for sparse graphs. Most graphs are sparse.
⬜ Traverse all the edges that start at v, in θ(degree(v))
◻ Disadvantage:
⬜ Check for existence of an edge (v, u) in worst case time
θ(degree(v))
 Adjacency-matrix-representation
(sequential representation)
25
Matrix representation of a graph G = ( V, E ) is a
| V | x | V | matrix A = ( aij ) such that -

aij = 1 if (i, j ) ∈ E &

0 otherwise

1 2 3 4 5
1 2

1 0 1 0 0 1
3 2 1 0 1 1 1
3 0 1 0 1 0
5 4 4 0 1 1 0 1
5 1 1 0 1 0

We arbitrarily uniquely assign the numbers 1, 2, . . . , | V | to each vertex. 25

 Adjacency Matrix Representation for a
Directed Graph
26

1 2 3 4 5
1 2

1 0 1 0 0 1
2 0 0 1 1 1
3
3 0 0 0 1 0
5 4 0 0 0 0 1
4
5 0 0 0 0 0
 Adjacency Matrix Representation
27

◻ Advantage:
⬜ Saves space for Dense graphs.
⬜ Check for existence of an edge in θ(1)
◻ Disadvantage:
⬜ Traverse all the edges that start at v, in θ(|V|)
28
29
 Adjacency Matrix Representation for weighted graph
WEIGHTED graph is a TRIPLE (V, E, W)
30

A[i][ j] = {weight if the edge <i, j> exists

0 if there exists no edge <i, j>}
 Adjacency Matrix Representation for weighted graph
31

A[i][ j] = {weight if the edge <i, j> exists

0 if there exists no edge <i, j>}
 Adjacency List for weighted graph
Struct GraphNode class GraphNode {
{ public:
int vertex; int vertex;
int weight; int weight;
GraphNode* next; GraphNode* next;
} OR GraphNode() {
vertex = weight = 0;
next = null;
}
};

V W 32
Lecture 3
 Adjacency Multilist
◻ An edge in an undirected graph is represented by two nodes in adjacency list
representation.
◻ For some applications, edge processing is done only once; this means we need to find other entries and
mark them as processed – time consuming
◻ Solution - Adjacency Multilists
⬜ lists in which nodes are shared among several lists.
one(an
bit edge
mark is shared
field by two different paths)
that indicates
whether
⬜ Node or not: the edge has been
Structure
examined.

Processed vertex1 vertex2 path1 path2

34
35
Example for Adjacency Multlists
(1,0)
0 N1 0 1 N2 N4 edge (0,1)
1 (2,0)
2 N2 0 2 N3 N4 edge (0,2)
(3,0)
3 0 3 N5
N3 (2,1)
edge (0,3)
0 N4 1 2 N5 N6 edge (1,2)
N1 N2 (3,1)
1 N3
2 N5 1 3 N6 edge (1,3)
N4 (3,2)
N5 3 N6 N6 2 3 edge (2,3)
six edges
Lists: vertex 0: N1 → N2 → N3, vertex 1: N1 → N4 → N5
vertex 2: N2 → N4 → N6, vertex 3: N3 → N5 → N6 36
Example for Adjacency Multlists

Vertex 1: N1 → N2 → N3
Vertex 2: N1 → N4 → N5
Vertex 3: N2 → N5
Vertex 4: N3 → N5 37
Generate Adjacency Multi-list

38
 Inverse Adjacency lists
39

◻ An inverse adjacency list is a set of lists that contains one list for each vertex.
◻ Each list contains a node per vertex adjacent to the vertex it represents (i.e.
consider in-degree for a vertex)
 Sequential Vs Linked representation
Linked Representation Sequential Representation
Adjacency List representation Adjacency matrix representation
Has an advantage of space complexity. Requires an n x n matrix with n vertices,
regardless of the number of edges.
Needs more memory asymptotically.
Suitable for sparse graphs. If the graph is sparse, many of the entries are null.
The number of edges |E| is much lesser than V. Suitable for dense graph.
Provides a compact way to represent the graph. |E| is closer to V

40
 Sequential Vs Linked representation
Linked Representation Sequential Representation
Does not provide direct access; Provides direct access, it is suitable for many
Cannot quickly determine whether an edge applications.
between any two vertices is incident or not.
Check for existence of an edge (v, u) in worst case Check for existence of an edge in θ(1)
time θ(degree(v))

Traverse all the edges that start at v, in Traverse all the edges that start at v, in θ(|V|)
θ(degree(v))

41
 Traversing Graphs
(Processing a graph)

• Traversal strategies - provide an efficient way to “visit” each vertex and edge
exactly once.
• Traversals are classified by the order in which the vertices are visited.
• Traversal of a graph can be commonly used to search a vertex or an edge
through the graph; hence, it is also called a search technique.
• Two techniques –
• Depth First Search (DFS)
• Breadth First Search (BFS)

42
 Depth First Search
• Strategy : From the currently visited vertex in the graph, keep searching/visiting
deeper.
• i.e. all the vertices are visited by processing a vertex and its descendents before
processing its adjacent vertices.
• Execution:
• First, push the first vertex say A into the stack.
• Loop
• Pop the stack
• Process/visit the vertex i.e. print the vertex
• Push all the adjacent vertices of A into the stack
• End Loop // When the stack is empty
• Traversal is complete.
43
Graph Traversal [DFS]

1 A A X HP E Y M J G

3 6

2 X H Y
5

E 8
7
9 G P 4 M J

P Y
H E E M J
A X G G G G G 44
 Graph Traversal [DFS]

1 A AXHPEYMJG

3 6

2 X H Y
5

E 8
7
9 G P 4 M J

P Y
H E E M M J
A X G G G G G G45 G
 Depth First Search
• Non-Recursive pseudo code-

46
 Depth First Search

1, 2, 4, 8, 5, 6, 3, 7 OR

1, 3, 7, 8, 6, 5, 2, 4
47
 Depth-First Search Example
2
3
48
8
1

4
5
9
10

6
7 11

Start search at vertex 1. Start vertex 4

412357698
OUTPUT - 1 2 3 5 7 6 4 9 8
48
 Time Complexity - DFS
49

• O(V + E) time is required by the DFS for adjacency list representation

• O(V2) for adjacency matrix representation.

DFS is more faster than BFS.

 Breadth First Search
• Strategy : From the currently visited vertex in the graph, keep searching/visiting its
breadth.
• i.e. all the vertices are visited by processing a vertex and its adjacent vertices.
• Execution:
• First, Enqueue the first vertex say A into the queue.
• Loop
• Dequeue
• Process/visit the vertex i.e. print the vertex
• Enqueue all the adjacent vertices of A into the queue
• End Loop // When the Queue is Not empty
• Traversal is complete.

50
Graph Traversing
[BFS]
1 A
A X GHPE M YJ
4 8

2 X H Y
6

E 9
7
3 G P 5 M J

A X G H H P P E M Y J

Queue Empty
51
Breadth First Search
Non-Recursive pseudo code

52
 Breadth-First Search Example
53

Start search at vertex 1.

Output - 1 2 4 5 3 7 6 8 9

…………
 Breadth-First Search Example
54

2
3
8
1

4
5
9
10

6
7 11

Start search at vertex 1.

Output – 1 2 4 3 5 6 7 9 8
 Time Complexity - BFS
55

• Each visited vertex is put on (and so removed from) the queue exactly
once.
• When a vertex is removed from the queue, we examine its adjacent
vertices.
• O(vertex degree) time is required by the BFS for adjacency list representation

• O(V2) for adjacency matrix representation.

BFS takes up a lot of space.

 DFS and BFS
56

• DFS stores only one adjacent ◻BFS stores all adjacent

vertex pointer. vertex pointers.
• Faster ◻Slower
• Uses backtracking
◻No backtracking
• Time complexity –
◻Time complexity –
• O(V2) for matrix
O(V2) for matrix
• O(V + E) for List
O(vertex degree) for
List
Applications—Communication Network

2
3
8
1 10

4
5
9
11

6
7

◻ Vertex = city, edge = communication link.

57
Driving Distance/Time Map
2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
11
5 6

6 7
7

◻ Vertex = city,
◻ edge weight = driving distance/time.
58
Street Map

2
3
8
1 10

4
5
9
11

6
7

◻ Some streets are one way.

59
 Spanning Tree
◻ A Tree is a connected graph with no cycles.
◻ Spanning Tree of a graph is a sub graph that contains all the
vertices and it is a Tree.
◻ Graph may have many Spanning Trees.

Graph A Some Spanning Trees from Graph A

or or or

60
Complete Graph All 16 of its Spanning Trees

61
 Minimum Spanning Trees

The Minimum Spanning Tree for a given graph is the Spanning

Tree of minimum cost for that graph.

Complete Graph Minimum Spanning Tree

7
2
2
5 3 3
4
1 1

Application –
Finding the least amount of wire needed to connect a group of computers, houses, or cities.
62
 Greedy Strategy

◻ An algorithmic paradigm that follows the problem solving approach of making the locally
optimal choice at each stage with the hope of finding a global optimum (best solution).
• Add largest value or smallest value as per the application.
◻ Simple, easy to implement, and runs fast.
◻ Sometimes may not provide the best solution.

Largest root to leaf sum

63
 Greedy Strategy properties

◻ Greedy choice property

◻ A global optimum can be arrived at by selecting a local optimum.
◻ Optimal substructure
◻ An optimal solution to the problem contains an optimal solution to sub problems.
• Applications
• Huffman coding
• Prim’s spanning tree

64
Lecture 5
Algorithms for Minimum Spanning Tree

• Kruskal's Algorithm - J.B. Kruskal

• Prim's Algorithm - R.C. Prim

66
 Graph G(V,E)
Kruskal’s Algorithm to
G' = (V', E’)

Sort edges in ascending order → Keep adding minimum weight edges with no cycle
till all vertices are Processed (i.e # of edges in MST is less than # of vertices.

Algorithm -
Arrange the edges in an increasing order of their weights
1. V' = V and E' = ø, |V| = n and | E' | = 0 //same vertices; zero edges
2. While ( |E'| < (V-1) ) do
Begin
Find edge <u,v> of minimum length.
If <u,v> does not create a cycle in G' then
add <u,v> to G'
else
discard <u,v>
End
Stop
67
68
Kruskal’s Algorithm
EDGE WEIGHT
<1, 2> 11
<2, 3> 20
<4, 5> 33
<6, 7> 33
<1, 4> 40
<2, 5> 40
<4, 7> 40
<3, 5> 50
<2, 4> 61
<5, 7> 72
<3, 6> 80
Step 1 – Sort the edges <5, 6> 81

Initially, connected components are {1} {2} {3} {4} {5} {6} {7}
69
Kruskal’s Algorithm
EDGE WT
<1, 2> 11
<2, 3> 20
<4, 5> 33
<6, 7> 33
<1, 4> 40
<2, 5> 40
<4, 7> 40
<3, 5> 50
<2, 4> 61
<5, 7> 72
<3, 6> 80
<5, 6> 81

Cost = 0
Cost = cost + weight of added edge 70
 Kruskal’s Algorithm - MST

Kruskal’s use Union-Find

algorithm to find smallest
edge & add it to MST
(incremental connection).

This minimum spanning tree has the cost as 177

71
Kruskal’s Algorithm -Example
 4 1
Complete Graph A B A D

4 4
B C B D

10 2
4
B C B J C E
4
2 1 1 5
C F D H
A 4 E
1 F
6 2
D 2 3 D J E G
10 5 3 5
G
F G F I
5 6 3
4 3 4
I G I G J
H
3 2 3
2 J H J I J

73
 Sort Edges
1 1
(in reality they are placed in a priority queue - not A D C F
sorted - but sorting them makes the algorithm
easier to visualize) 2 2
C E E G

4 2 3
B C H J F G
4
2 1 3 3
G I I J
A 4 E
1 F
4 4
D 2 3 A B B D
10 5
G 4 4
B C G J
5 6 3
4 5 5
I F I D H
H
2 3 6 10
J D J B J

74
 1 1
Add Edge
A D C F
2 2
C E E G
2 3
B 4 C H J F G
4 3
2 1 3
G I I J
A 4 E
1 F 4
4
D 2 3 A B B D
10 4
G 5 4
B C G J
5 6 3
5 5
4
I F I D H
H
6 10
2 3
J D J B J

75
 1 1
Add Edge
A D C F

2 2
C E E G

2 3
B 4 C H J F G
4
2 1 3 3
G I I J
A 4 E
1 F
4 4
D 2 3 A B B D
10
G 5 4 4
B C G J
5 6 3
4 5 5
I F I D H
H
3 6 10
2 J D J B J

76
 1 1
Add Edge
A D C F

2 2
C E E G

2 3
B 4 C H J F G
4 3
2 1 3
G I I J
A 4 E
1 F 4
4
D 2 3 A B B D
10 4
G 5 4
B C G J
5 6 3
4 5 5
I F I D H
H
3 6 10
2 J D J B J

77
 1 1
Add Edge
A D C F

2 2
C E E G

2 3
B 4 C H J F G
4
2 1 3 3
G I I J
A 4 E
1 F
4 4
D 2 3 A B B D
10
G 5 4 4
B C G J
5 6 3
4 5 5
I F I D H
H
3 6 10
2 J D J B J

78
 1 1
Add Edge
A D C F

2 2
C E E G

2 3
B 4 C H J F G
4 3
2 1 3
G I I J
A 1 4 E F 4
4
D 2 3 A B B D
10 5 4 4
G
B C G J
5 6 3
5 5
4
I F I D H
H
6 10
3
2 J D J B J

79
 1 1
Cycle
A D C F
Don’t Add Edge
2 2
C E E G
2 3
B 4 C H J F G
4 3 3
2 1
G I I J
A 4 E
1 F 4 4
D 2 3 A B B D
10
G 5 4 4
B C G J
5 6 3
4
5 5
I F I D H
H
3
6 10
2 J D J B J

80
 1 1
Add Edge
A D C F
2 2
C E E G

4 2 3
B C H J F G
4
2 3 3
1
G I I J
A 1 4 E F 4
4
D 2 3 A B B D
10 4
G 5 4
3 B C G J
5 6
5 5
4
I F I D H
H
6 10
3
2 J D J B J

81
 1 1
Add Edge A D C F

2 2
C E E G

2 3
B 4 C H J F G
4
2 1 3 3
G I I J
A 4 E
1 F
4 4
D 2 3 A B B D
10
G 5 4 4
B C G J
5 6 3
4 5 5
I F I D H
H
3 6 10
2 J D J B J

82
 1 1
Add Edge
A D C F
2 2
C E E G
2 3
B 4 C H J F G
4
2 1 3 3
G I I J
A 4 E
1 F
4 4
D 2 3 A B B D
10
G 5 4 4
B C G J
5 6 3
4 5 5
I F I D H
H
3 6 10
J D J B J
2
83
 1 1
Cycle
A D C F
Don’t Add Edge
2 2
C E E G

2 3
4
4 B C H J F G
2 1 3 3
G I I J
A 4 E
1 F 4
4
D 2 3 A B B D
10 4
G 5 4
B C G J
5 6 3
4 5 5
I F I D H
H
3 6 10
2 J D J B J

84
 1 1
Add Edge
A D C F
2 2
C E E G

4 2 3
4 B C H J F G
2 1 3 3
G I I J
A 4 E
1 F
4 4
D 2 3 A B B D
10 4
G 5 4
3 B C G J
5 6
4 5 5
I F I D H
H
3 6 10
J D J B J
2
85
 Minimum Spanning Tree Complete Graph

Cost = 22
4
4 B C
4 B C 4
2 1
2 1
A 4 E
A 1 F
1 E F
D 2 3
D 2
10
G 5
G
3 5 6 3
4
I I
H H
3 3
J 2 J
2
86
 Graph G(V,E)
Prims Algorithm to
G' = (V', E’)

• Starts with empty subtree.

• At each stage, maintain two sets of vertices <u,v>.
• The first vertex is already included in the MST, the other vertex not yet included.
• If first vertex is u then,
• Pick a vertex v which is not there in MST and has minimum key value.
• Repeat above steps till MST doesn’t include all vertices.

Prim's is better for more dense graphs.

Prim's is faster than Kruskal's in the case of complex graphs.
87
 Graph G(V,E)
Prims Algorithm to
G' = (V', E’)

Algorithm –
1. V' = ø and E' = ø
2. Let u ϵ V, i is start vertex
3. V' = V' U { u }
4. While ( V' ≠ V ) do
Begin
Find edge <u, v> ϵ E of minimum length
such that u ϵ V' and v ϵ V – V'
V' = V' U { v }
E' = E' U {u, v}
End
Stop

88
Prim’s Algorithm

Cost = 0
Cost = cost + weight of added edge

89
90
Prim’s Algorithm

Cost = 177

91
Prim’s Algorithm-Example
 Complete Graph
Start vertex - A

4
B C
4
2 1
A 4 E
1 F

D 2 3
10 5
G
5 6 3
4
I
H
2 3
J

93
 Old Graph
New Graph

Possibilities
Selection

4 4
B C 4 B C
4
2 1 2 1
A 4 E
1 F A 4 E
1 F
D 2 3 2
10 D 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J
94
Possibilities from added edge <A,D>

4 B 4 C
B C 4
4 2
2 1 1
A 4 E A 1 4 E
1 F F

D 2 3 D 2 3
10 10
G 5 G 5
5 6 3 5 6 3
4 4
I I
H H
3
J 2 3
2 J
95
Possibilities from added edge <A,D> and <A,B> New Graph

4
4
B C 4 B C
4
2 1 2 1
A 4 E A 4 E
1 F 1 F

D 2 3 2
D 3
10 10
G 5 5
G
5 6 3
5 6 3
4
I 4
H I
H
2 3
J 3
2 J
96
Possibilities from added edge <A,D> <A,B> and New Graph
<B,C>

4 4
4 B C 4 B C
2 1 2 1
A 1 4 E A 4
F 1 E F
D 2 3 2
10 D 3
5 10
G 5
G
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J
97
Possibilities from added edge <A,D> <A,B> <B,C> New Graph
and <C,F>

4
B C 4
4 4 B C
2 1 2 1
A 4 E
1 F A 4 E
1 F
D 2
3 2
10 D 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J
98
Possibilities from added edge <A,D> <A,B> <B,C>
<C,F> and <C,E> New Graph

4 4
4 B C B C
4
2 1 2 1
A 4 E A 4
1 F 1 E F
D 2 2
3 D
10 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J 3
2 J
99
Possibilities from added edge <A,D> <A,B> <B,C>
<C,F> <C,E> and <E,G> New Graph

4 4
4 B C B C
4
2 1 2 1
A 1 4 E A 4
F 1 E F
D 2 3 2
D 3
10
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J
100
Possibilities from added edge <A,D> <A,B> <B,C>
<C,F> <C,E> <E,G> and <G,I> New Graph

4 4
4 B C
4 B C
2 1 2 1
A 4 E
1 F A 4 E
1 F
D 2
3 D 2 3
10
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J 3
2 J
101
Possibilities from added edge <A,D> <A,B> <B,C>
<C,F> <C,E> <E,G> <G,I> and <I,J> New Graph

4
4 B C 4
4 B C
2 1
2 1
A 4 E
1 F A 4
1 E F
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J 3
2 J
102
 Complete Graph Minimum Spanning Tree

B 4 C 4
4 4 B C
2 1
2 1
A 4 E
1 F A E F
1
D 2 3
10 D 2
G 5
G
5 6 3
3
4
I
H I
3 H
2 J 3
2 J
103
 Prim’s and Kruskal’s Example
• Prim’s
◻ Termination – All
vertices are included in
MST

Cost = 37

◻ Kruskal’s
◻ Termination – #edges in
MST < #vertices

Cost = 37
104
 Time Complexity
• Prim’s:-
For implementation O(n2) - Dense graph

• Kruskal’s:-
For sorting edges O(E log E)
For merging of components O(log V)
Overall O(E log E) + O(log V) i.e. O(E log V)

MST Application – Network design so that only the minimum number of packets need to be relayed across the
network and multiple copies of the same packet don't arrive via different paths.
105
 Shortest Path Algorithm
• Objective
• Find the shortest path between any two vertices in the graph. OR
• Find the shortest path from given starting vertex to every other vertex .
• The shortest path between two given vertices is the path having minimum length.
• Greedy Algorithm - Dijkstra’s algorithm (Edger W. Dijkstra)
• For any graph G=(V,E,w);
• Distance hold the length of the shortest distance.
• Path hold the shortest path between the source and each of the vertices.

106
 Single Source Shortest Path Algorithm

• For a weighted graph G = (V, E, w); the single-source shortest paths problem is to find
the shortest paths from a vertex v ∈ V to all other vertices in V.
• Dijkstra's algorithm is similar to Prim's algorithm. It maintains a set of adjacent nodes
for which the shortest paths are known.
• For any edge <u,v>;

dist[v] = min{ dist[v], dist[u] + weight(u, v) }

107
Dijkstra's Shortest Path Algorithm

108
Dijkstra's Shortest Path Algorithm

109
 Dijkstra's Shortest Path Algorithm

Minimum weight is 2 i.e. vertex

C

Dist(B)
= min(4, <ACB>)
= min(4, <2+1>)
= min(4, 3)
=3
110
111
112
 Dijkstra's Shortest Path Algorithm

Shortest Path -

A C B D E Z

Start vertex – a
Destination vertex - z

113
114
115
 Dijkstra's Shortest Path Algorithm

Start vertex – A
Destination vertex - H

Path
 Dijkstra's Shortest Path Algorithm

Path

A C D E G F H

Cost -
11
Dijkstra's Shortest Path Algorithm

(Alternate selection)
 Dijkstra's Shortest Path Algorithm

Path

ACDEGFH

Cost -
11
 Dijkstra’s shortest Path

Start vertex – a
Destination vertex - d

A to every other vertex

120
Start vertex – a
Destination vertex - d

A to every other vertex

121
 Dijkstra's Shortest Path Algorithm

• Find shortest path from s to t.

2 24 3
9
s
18
14
2 6
6
30 4 19
11
15 5
5
6
20 16

7 t
44
 Dijkstra's Shortest Path Algorithm
S={ }
PQ = { s, 2, 3, 4, 5, 6, 7, t }

∞ ∞
2 24 3
0 9
s
18
14 ∞ 2 6
6
∞
30 ∞ 4 19
11
15 5
5
6
20 16

7 t
44
∞ ∞
 Dijkstra's Shortest Path Algorithm
S={ }
delmin PQ = { s, 2, 3, 4, 5, 6, 7, t } ∞
∞
2 24 3
0 9
s
18
14 ∞
2 6
6 ∞
30 ∞ 4 19
11
15 5
5
6
20 16

7 t
44
∞ ∞
 Dijkstra's Shortest Path Algorithm
S={s}
decrease key PQ = { 2, 3, 4, 5, 6, 7, t }
∞
∞ 9
X
2 24 3
0 9
s
18
14 X
∞ 14
2 6
6 ∞
30 ∞ 4 19
11
5
15 5
6
20 16

7 t
44
∞ 15
X ∞
 Dijkstra's Shortest Path Algorithm
S={s}
PQ = { 2, 3, 4, 5, 6, 7, t }

delmin
∞
X 9 ∞
2 24 3
0 9
s
18
14 ∞
X 14
2 6
6
∞
4
30 ∞ 11 19
15 5
5
6
20 16

7 t
44
∞
X 15 ∞
 Dijkstra's Shortest Path Algorithm
S = { s, 2 }
PQ = { 3, 4, 5, 6, 7, t }

∞ 9
X ∞
2 24 3
0 9
s
18
14 ∞
X 14
2 6
6
∞
4
30 ∞ 11 19
15 5
5
6
20 16

7 t
44
∞
X 15 ∞
 Dijkstra's Shortest Path Algorithm
S = { s, 2 } decrease key
PQ = { 3, 4, 5, 6, 7, t }
X∞ 33
∞ 9
X
2 24 3
0 9
s
18
14 X
∞ 14
2 6
6 ∞
30 ∞ 4 19
11
15 5
5
6
20 16

7 t
44
∞ 15
X ∞
 Dijkstra's Shortest Path Algorithm
S = { s, 2 }
PQ = { 3, 4, 5, 6, 7, t }

∞ 9
X ∞ 33
X

2 24 3
0 9
delmin
s
18
14 X
∞ 14
2 6
6
∞
4
30 ∞ 11 19
15 5
5
6
20 16

7 t
44
∞ 15
X ∞
 Dijkstra's Shortest Path Algorithm
S = { s, 2, 6 }
PQ = { 3, 4, 5, 7, t }
32
X∞ 33
X
∞ 9
X
2 24 3
0 9
s
18
14 X
∞ 14
2 6
6
44 ∞
30 X
∞ 4 19
11
15 5
5
6
20 16

7 t
44
∞ 15
X ∞
 Dijkstra's Shortest Path Algorithm
S = { s, 2, 6 }
PQ = { 3, 4, 5, 7, t }
32
X∞ 33
X
∞ 9
X
2 24 3
0 9
s
18
14 X
∞ 14
2 6
6
44 ∞
30 X
∞ 4 19
11
15 5
5
6
20 16

7 t
44
∞ 15
X delmin ∞
 Dijkstra's Shortest Path Algorithm
S = { s, 2, 6, 7 }
32
PQ = { 3, 4, 5, t }
X∞ 33
X
∞ 9
X
2 24 3
0 9
s
18
14 X
∞ 14
2 6
6
X 35
44 ∞
30 X
∞ 4 19
11
15 5
5
6
20 16

7 t
44
∞ 15
X ∞
59 X
 Dijkstra's Shortest Path Algorithm delmin
S = { s, 2, 6, 7 }
PQ = { 3, 4, 5, t }
32
X∞ 33
X
∞ 9
X
2 24 3
0 9
s
18
14 X
∞ 14
2 6
6
X 35
44 ∞
30 X
∞ 4 19
11
15 5
5
6
20 16

7 t
44
∞ 15
X ∞
59 X
 Dijkstra's Shortest Path Algorithm
S = { s, 2, 3, 6, 7 }
PQ = { 4, 5, t }
32
X∞ 33
X
∞ 9
X
2 24 3
0 9
s
18
14 X
∞ 14
2 6
6
X 34
X 35
44 ∞
30 X
∞ 4 19
11
15 5
5
6
20 16

7 t
44
∞ 15
X 51 59
X X∞
 Dijkstra's Shortest Path Algorithm
S = { s, 2, 3, 6, 7 }
PQ = { 4, 5, t }
32
X∞ 33
X
∞ 9
X
2 24 3
0 9
s
18
14 X
∞ 14
2 6
6
X 34
X 35
44 ∞
30 X
∞ 4 19
11
15 5
5
6
20 delmin 16

7 t
44
∞ 15
X 51 59
X X∞
 Dijkstra's Shortest Path Algorithm
S = { s, 2, 3, 5, 6, 7 }
PQ = { 4, t }
32
X∞ 33
X
∞ 9
X
2 24 3
0 9
s
18
14 X
∞ 14
2 6
6 ∞
45 X
X 34
X 35
44
30 X
∞ 4 19
11
15 5
5
6
20 16

7 t
44
∞ 15
X 50 51
X 59 ∞
X X
 Dijkstra's Shortest Path Algorithm
S = { s, 2, 3, 5, 6, 7 }
PQ = { 4, t }
32
X∞ 33
X
∞ 9
X
2 24 3
0 9
s
18
14 X
∞ 14
2 6
6 ∞
45 X
X 34
X 35
44
30 X
∞ 4 19
11
15 5 delmin
5
6
20 16

7 t
44
∞ 15
X 50 51
X 59 ∞
X X
 Dijkstra's Shortest Path Algorithm
S = { s, 2, 3, 4, 5, 6, 7 }
PQ = { t }
32
X∞ 33
X
∞ 9
X
2 24 3
0 9
s
18
14 X
∞ 14
2 6
6 ∞
45 X
X 34
X 35
44
30 X
∞ 4 19
11
15 5
5
6
20 16

7 t
44
∞ 15
X 50 51
X 59 ∞
X X
 Dijkstra's Shortest Path Algorithm
S = { s, 2, 3, 4, 5, 6, 7 }
PQ = { t }
32
X∞ 33
X
∞ 9
X
2 24 3
0 9
s
18
14 X
∞ 14
2 6
6 ∞
45 X
X 34
X 35
44
30 X
∞ 4 19
11
15 5
5
6
20 16

7 t
44
∞ 15
X delmin 50 51
X 59 ∞
X X
 Dijkstra's Shortest Path Algorithm
S = { s, 2, 3, 4, 5, 6, 7, t }
PQ = { }
32
X∞ 33
X
∞ 9
X
2 24 3
0 9
s
18
14 X
∞ 14
2 6
6 ∞
45 X
X 34
X 35
44
30 X
∞ 4 19
11
15 5
5
6
20 16

7 t
44
∞ 15
X 50 51
X 59 ∞
X X
 Dijkstra's Shortest Path Algorithm
S = { s, 2, 3, 4, 5, 6, 7, t }
PQ = { }
32
X∞ 33
X
∞ 9
X
2 24 3
0 9
s
18
14 X
∞ 14
2 6
6 ∞
45 X
X 34
X 35
44
30 X
∞ 4 19
11
15 5
5
6
20 16

7 t
44
∞ 15
X 50 51
X 59 ∞
X X
 Time Complexity

• Dijkstra’s:-
For adjacency matrix implementation O(n 2)

For adjacency list – O(E log V)

142
 Topological Sorting/Ordering
• For any directed acyclic graph (DAG) G(V,E)- topological sorting is linear ordering of all its vertices
such that if G contains an edge <u,v> then u appears before v in the ordering.

ABCDE

ACBDE

Ordering can be viewed as list of vertices along a horizontal line so that all directed edges go from left to right.
143
Lecture 9
Topological Sorting

• Applications-
Planning of sequence/task,
Task scheduling,
Project deadlines,
Pre-requisite problems (University courses),
Build projects (Dependant libraries)

145
 Topological Sorting
• Topological sort is not unique.
• Following are all topological sort of the graph below:

s1 = {a, b, c, d, e, f, g, h, i}
s2 = {a, c, b, f, e, d, h, g, i}
s3 = {a, b, d, c, e, g, f, h, i}
s4 = {a, c, f, b, e, h, d, g, i}
etc.

• The Source Removal Topological sort algorithm is:

– Pick a source a [vertex with in-degree zero], output it.
– Remove a and all edges out of a.
– Repeat until graph is empty.
146
 Topological Sorting
• Topological-sort(G)
1. Call DFS(G)
2. As each vertex is finished (i.e. no more adjacent or unvisited vertex), add it onto the front of topological
sorted list.

Adjacency List

147
 Topological Sorting
1. Call DFS (G)
2. As each vertex is finished add it onto the front of topological sorted list.

DFS a b d g i c f h e
Adjacency List
Vertex i is finished; as no further adjacent & unvisited
f vertices
h
i Vertex g, d are also finished.
g Vertex h, f, c are finished.
d Vertex e is finished.
b Vertex b, a are finished.
c
e Topological Order
a a b e c f h148d g i
Topological Sorting

Adjacency List

Topological Order a b e c f h d g i

149
 Topological Ordering - complexity

• O(V + E) for DFS and O(1) time for adding vertex to the list

• O(V + E) for Topological ordering

V are the vertices

E are the edges
Same as DFS

150
Case study- Data structure used in Webgraph and Google map

• Google Maps essentially uses two Graph algorithms – Dijkstra’s

algorithm and A* algorithm, to calculate the shortest distance from
point A ( Source) to point B ( destination).
• A graph data structure is essentially a collection of nodes that are
defined by edges and vertices.
• Dijkstra’s algorithm is one of the greedy algorithms used to optimize
and find the shortest path between nodes in a graph. Dijkstra’s
algorithm is an effective algorithm proposed by Edsger.W. Dijkstra in
the year 1956 and published three years later.
Case study- Data structure used in Web-graph
and Google map

• A* graph algorithm is one of the best graph traversal and path search
algorithms, formulated especially for weighted graphs.
• This algorithm is more preferred due to its completeness, optimality, and
optimal efficiency. A* algorithm is similar to Dijkstra’s algorithm and uses a
heuristic function to navigate a better and more efficient path.
• Unlike Dijkstra’s, the A* algorithm focuses on only the destination nodes and not
the others; thus, this algorithm proves to be more proficient. It also takes
parameters such as time requirement, distance, etc., optimizing and choosing
the better nodes.
• So now, Google Maps also uses this algorithm to calculate the shortest path,
owing to its high accuracy and ability to deal with huge chunks of data and
mammoth graphs.
 Revision
• Graphs
- Directed, weighted, dense, sparse
• Storage representation
- Adjacency matrix
- Adjacency list, adjacency multi list, inverse adjacency list.
• Traversals-
- Depth first search (Stack)
- Breadth first search (Queue)
• Greedy Strategy
- Minimum spanning Tree
- Prim’s Algorithm (start vertex and then keep adding minimum value edge)
- Kruskal’s Algorithms – on sorted edges
- Dikjtra's Single Source shortest path
• Topological ordering.

153
 Quiz
What is the number of edges present in a complete graph having n vertices?

a) (n*(n+1))/2
b) (n*(n-1))/2
c) n
d) Information given is insufficient

Dijkstra’s Algorithm will work for both negative and positive weights?

a) True
b) False

What would be the DFS traversal of the given Graph?

a) ADEBC
b) AEDCB
c) EDCBA
d) ACEDB
 Quiz
Which of the following is/are the operations performed by kruskal’s algorithm?
i) sort the edges of G in increasing order by length
ii) keep a subgraph S of G initially empty
iii) builds a tree one vertex at a time

A) i, and ii only
B) ii and iii only
C) i and iii only
D) All i, ii and iii

Rather than build a subgraph one edge at a time …………………………. builds a tree one vertex at a time.

A) Kruskal’s algorithm
B) Prim’s algorithm
C) Dijkstra algorithm
D) topological order
 Quiz
……………… is known as a greedy algorithm, because it chooses at each step the cheapest edge to add to
subgraph S.
A) Kruskal’s algorithm
B) Prim’s algorithm
C) Dijkstra algorithm
D) Bellman ford algorithm

Dijkstra’s Algorithm is also called the …………………. shortest path problem.

A) multiple source
B) single source
C) single destination
D) multiple destination

In …………… input is a directed acyclic graph (DAG)G=(V,E).

A) Graph transpose problem

B) Strongly connected components problem
C) Topological sort problem
D) Euler path problem
 Quiz
What are the appropriate data structures for following algorithms?
1. Breadth First Search Prim’s can use Priority Q for holding
2. Depth First Search vertices not included in MST
3. Prim’s Minimum Spanning Tree
4. Kruskal’s Minimum Spanning Tree
Kruskal’s use Union-Find algorithm to
find smallest edge & add it to
A) Stack, Queue, Priority Queue, Union-Find
MST(incremental connection).
B) Queue, Stack, Priority Queue, Union-Find
C) Stack, Queue, Union-Find, Priority Queue
D) Priority Queue, Queue, Stack, Union-Find

The Breadth First Search algorithm has been implemented using the queue data structure. One possible
order of visiting the nodes of the following graph is
a) MNOPQR
b) NQMPOR
c) QMNPRO
d) QMNPOR