Data Structures (DS)

GTU # 3130702

Unit-3
Non-Linear Data
Structure (Graph)
Graphs
What is Graph? G = ( V, E ) . . . . . . . . . Tree is a Subset of Graph….
Representation of Graph
Matrix representation of Graph
Linked List representation of Graph

Elementary Graph Operations

Breadth First Search (BFS)
Depth First Search (DFS)
Spanning Trees
Minimal Spanning Trees
Shortest Path
Adjacency matrix
A diagrammatic representation of graph may have limited usefulness. However such a
representation is not feasible when no. of nodes and edges in graph is large.
It is easy to store and manipulate matrices and hence graph is represented by them in the
computer.
Let G = ( V, E ) be a simple diagraph in which V = { v1,v2,…,Vn} and the nodes are assume to be
ordered from V1 to Vn.
An n x n matrix A is called Adjacency Matrix of the graph G whose elements are aij , given by
Adjacency matrix
An element of the adjacency matrix is either 0 or 1
Any matrix whose elements are either 0 or 1 is called bit matrix or Boolean matrix
For a given graph G =m (V, E), an adjacency matrix depends upon the ordering of the elements
of V
For different ordering of the elements of V we get different adjacency matrices.

V1 V4 V1 V2 V3 V4
V1 0 1 0 1
A = V2 1 0 0 0
V3 1 1 0 1
V4 0 1 0 0
V2 V3
Adjacency matrix
V1 V4 V1 V2 V3 V4
V1 0 1 0 1
A= V2 1 0 0 0
V3 1 1 0 1
V4 0 1 0 0
V2 V3

The number of elements in the ith row whose value is 1 is equal to the out-degree of node Vi
The number of elements in the jth column whose value is 1 is equal to the in-degree of node Vj
For a NULL graph which consist of only n nodes but no edges, the adjacency matrix has all its
elements 0. i.e. the adjacency matrix is the NULL matrix
Power of Adjacency matrix
0 1 0 1 1 1 0 1
V1 V4 1 0 0 0 1 1 0 0
A= A3 =
1 1 0 1 2 2 0 1
0 1 0 0 0 1 0 1

1 1 0 0 1 2 0 1
V2 V3 0 1 0 1 1 1 0 1
2
A =AxA= 1 2 0 1 A4 =
2 3 0 2
1 0 0 0 1 1 0 0

Entry of 1 in ith row and jth column of A shows existence of an edge (Vi, Vj), that is a path of
length 1
Entry in A2 shows no of different paths of exactly length 2 from node Vi to Vj
Entry in A3 shows no of different paths of exactly length 3 from node Vi to Vj
Path matrix or reachability matrix
Adjacency List Representation
0

1 4
2
3

0 1 2 3 4
1 0 3
2 0 3 4
3 0 1 2 4
4 0 2 3
Graph Traversal
Two Commonly used Traversal Techniques are
Depth First Search (DFS) 28

Breadth First Search (BFS)

23 32

22 26 30 34

27 31 36
Depth First Search (DFS)
It is like preorder traversal of tree
Traversal can start from any vertex Vi
Vi is visited and then all vertices adjacent to Vi are traversed recursively using DFS

DFS (G, 1) is given by

✓
Step 1: Visit (1)
1
Step 2: DFS (G, 2) DFS (G, 2):
✓ 2 5 DFS (G, 3) Step1: Visit(2)
✓ DFS (G, 4) Step 2: DFS (G, 6)
✓ ✓
3 4 DFS (G, 5) DFS (G, 6):
Step1: Visit(6)
Step 2: DFS (G, 3)
DFS (G, 8)
✓ 6 ✓ 7
✓ DFS of given graph starting from node 1 is given by

8 1 2 6 3 8 7 4 5
Depth First Search (DFS)
✓ A
✓ B C✓
M N O
✓ D ✓ E F ✓ G ✓
R
Q P
H
✓
ABDHECFG
✓ A
✓
✓ B ✓ C E A B D C F E
✓ D F✓
Breadth First Search (BFS)
This methods starts from vertex V0
V0 is marked as visited. All vertices adjacent to V0 are visited next
Let vertices adjacent to V0 are V1, V2, V2, V4
V1, V2, V3 and V4 are marked visited
All unvisited vertices adjacent to V1, V2, V3, V4 are visited next
The method continuous until all vertices are visited
The algorithm for BFS has to maintain a list of vertices which have been visited but not
explored for adjacent vertices
The vertices which have been visited but not explored for adjacent vertices can be stored in
queue
Breadth First Search (BFS)
✓ ✓ A
✓ 1 ✓
2 5 ✓ B ✓ C
✓ ✓
✓
3 4 ✓ D ✓ E F✓ G

6 ✓ 7 ✓
H✓
✓ 8 1 |2 3 4 5| 6 7| 8 A|BC |DEFG |H
V4
V1

V2
V0 V6

V3 V 0| V 1 V 2 | V 4 V 6 V 3 | V 5
V5
Write DFS & BFS of following Graphs

A
B C
M N O
D E F G
R
Q P
H

A A
0 1
B C E B E
5 2
D F
4 3 C D
Procedure : DFS (vertex V)
This procedure traverse the graph G in DFS manner.
V is a starting vertex to be explored.
Visited[] is an array which tells you whether particular vertex is visited or not.
W is a adjacent node of vertex V.
S is a Stack, PUSH and POP are functions to insert and remove from stack respectively.
Procedure : DFS (vertex V)
1. [Initialize TOP and Visited]
visited[] 🡪 0
TOP 🡪 0
2. [Push vertex into stack]
PUSH (V)
3. [Repeat while stack is not Empty]
Repeat Step 3 while stack is not empty
v 🡪 POP()
if visited[v] is 0
then visited [v] 🡪 1
for all W adjacent to v
if visited [w] is 0
then PUSH (W)
end for
end if
Procedure : BFS (vertex V)
This procedure traverse the graph G in BFS manner
V is a starting vertex to be explored
Q is a queue
visited[] is an array which tells you whether particular vertex is visited or not
W is a adjacent node f vertex V.
Procedure : BFS (vertex V)
1. [Initialize Queue & Visited]
visited[] 🡪 0
F 🡪 R 🡪 0
2. [Marks visited of V as 1]
visited[v] 🡪 1
3. [Add vertex v to Q]
InsertQueue(V)
4. [Repeat while Q is not Empty]
Repeat while Q is not empty
v 🡪 RemoveFromQueue()
For all vertices W adjacent to v
If visited[w] is 0
Then visited[w] 🡪 1
InsertQueue(w)
Spanning Tree
A Spanning tree of a graph is an undirected tree consisting of only those edges necessary to
connect all the nodes in the original graph
A spanning tree has the properties that
For any pair of nodes there exists only one path between them
Insertion of any edge to a spanning tree forms a unique cycle

The particular Spanning for a graph depends on the criteria used to generate it
If DFS search is use, those edges traversed by the algorithm forms the edges of tree, referred to
as Depth First Spanning Tree
If BFS Search is used, the spanning tree is formed from those edges traversed during the
search, producing Breadth First Spanning tree
Construct Spanning Tree
A A A
B C B C B C

D E F G D E F G D E F G

H H H
DFS Spanning Tree BFS Spanning Tree

A A A
B C E B C E B C E
D F D F D F
DFS Spanning Tree BFS Spanning Tree
Minimum Cost Spanning Tree
The cost of a spanning tree of a weighted undirected graph is the sum of the costs(weights) of
the edges in the spanning tree
A minimum cost spanning tree is a spanning tree of least cost
Two techniques for Constructing minimum cost spanning tree
Prim’s Algorithm
Kruskal’s Algorithm
Prims Algorithm
Step 1: Taking minimum Weight edge Step 3: Taking minimum weight edge of
A of all Adjacent edges of X={A} all Adjacent edges of X = { A , B , C }
4 5
6 6 4 A
B E 4 A
3 B X={A,B}
B X = {A,B,C,D}
5 7 Step 2: Taking minimum weight edge
2 2
of all Adjacent edges of X = { A , B } 1
C D C D
1 4 A
Step 4: Taking minimum weight edge of
A–B|4 A–D|6 C–E|5 B all Adjacent edges of X = {A ,B ,C ,D }
A–E|5 B–E|3 C–D|1 2 X = {A ,B,C}
A–C|6 B–C|2 D–E|7 4 A
C
Let X be the set of nodes 3
We obtained minimum spanning
B E
explored, initially X = { A } X = {A,B,C,D,E}
tree of cost: 2
A 4 + 2 + 1 + 3 = 10 C D
1
Kruskal’s Algorithm
Step 2: Taking next min edge (B,C) Step 4: Taking next min edge (A,B)
A
4 5
6 6
B A
4
B 3
E
2
5 7 C D B E
2 1 3

C D 2
1
C D
Step 3: Taking next min edge (B,E) 1
Step 1: Taking min edge (C,D)

B E so we obtained minimum
3 spanning tree of cost:
C D 4 + 2 + 1 + 3 = 10
1 2
C D
1
Construct Minimum Spanning Tree
0 0
3 6 3
1 1
1 5 5 3 1 3
2 2
3 6 4 2 3 4 2

6
4 5 4 5

1 1
4
1 2 2 1 2 2
2 3 2
3 4 5 3 4 5
3 2 2
1 4
3 1 3
6 7 6 7
Shortest Path Algorithm
Let G = (V,E) be a simple diagraph with n vertices
The problem is to find out shortest distance from a vertex to all other vertices of a graph
Dijkstra Algorithm – it is also called Single Source Shortest Path Algorithm
Dijkstra Algorithm – Shortest Path
2
1 B D A B C D E F
6

0 A 1
4 7 F Distance 0 ∞ ∞ ∞∞∞
Visited 0 0 0 0 0 0
5 2
C 5
E

1st Iteration: Select Vertex A with minimum distance

1 ∞
2
1 B D ∞
6
4 F A B C D E F
0 A 1 7
Distance 0 1 ∞
∞ 5 ∞∞∞
5 2
C E Visited 1 0 0 0 0 0
5 5 ∞
Dijkstra Algorithm – Shortest Path
2nd Iteration: Select Vertex B with minimum distance

Cost of going to C via B = dist[B] + cost[B][C] = 1 + 1 = 2 A B C D E F

Cost of going to D via B = dist[B] + cost[B][D] = 1 + 2 = 3 Distance 0 1 5 ∞ ∞ ∞
Cost of going to E via B = dist[B] + cost[B][E] = 1 + 4 = 5 Visited 1 0 0 0 0 0
Cost of going to F via B = dist[B] + cost[B][F] = 1 + ∞ = ∞

1 3
2
B D
6
1
4 ∞
0 A 1 7 F A B C D E F
5
5
2 Distance 0 1 2 3 5 ∞
C E Visited 1 1 0 0 0 0
2 5
Dijkstra Algorithm – Shortest Path
3rd Iteration: Select Vertex C via B with minimum distance

Cost of going to D via C = dist[C] + cost[C][D] = 2 + ∞ = ∞ A B C D E F

Cost of going to E via C = dist[C] + cost[C][E] = 2 + 5 = 7 Distance 0 1 2 3 5 ∞
Cost of going to F via C = dist[C] + cost[C][F] = 2 + ∞ = ∞ Visited 1 1 0 0 0 0

1 3
2
B D
6
1
4
0 A 1 7 F A B C D E F
5
2 ∞ Distance 0 1 2 3 5 ∞
5
C E Visited 1 1 1 0 0 0
2 5
Dijkstra Algorithm – Shortest Path
4th Iteration: Select Vertex D via path A - B with minimum distance
Cost of going to E via D = dist[D] + cost[D][E] = 3 + 7 = 10 A B C D E F
Cost of going to F via D = dist[D] + cost[D][F] = 3 + 6 = 9 0 1 2 3 5 ∞
Distance
Visited 1 1 1 0 0 0

1 3
2
B D
6
1
4
A 1 7 F
5 A B C D E F
9
2
5 Distance 0 1 2 3 5 9
C E
2 5
Visited 1 1 1 1 0 0
Dijkstra Algorithm – Shortest Path
4th Iteration: Select Vertex E via path A – B – E with minimum distance
Cost of going to F via E = dist[E] + cost[E][F] = 5 + 2 = 7 A B C D E F
Distance 0 1 2 3 5 9
Visited 1 1 1 1 0 0

1 3
2
B D
6
1
4
A B C D E F
A 1 7 F 7
5 Distance 0 1 2 3 5 7
2
Visited 1 1 1 1 1 0
C E
2 5
Shortest Path from A to F is
A🡪B🡪E🡪F=7
Shortest Path
Find out shortest path from node 0 to all other nodes using Dijkstra Algorithm

0 100 0 100
10 10 60
10
30 4 30 4
1 1

60 60
50 10 50 10

2 3 2 3
20 50 20 30
Data Structures (DS)
GTU # 3130702

Thank
You