1 of 32

Unit-3 �Non-Linear Data Structure Graph

pradyuman.jadeja@darshan.ac.in

+91 9879461848

Computer Engineering Department

Dr. Pradyumansinh Jadeja

Data Structures (DS)

GTU # 3130702

Darshan Institute of Engineering & Technology, Rajkot

2 of 32

Graphs

What is 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

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

2

3 of 32

Adjacency matrix

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

3

4 of 32

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.

V₁

V₂

V₃

V₄

0	1	1
1	0	0
1	1	1
0	1	0

V₁

V₂

V₃

V₄

A =

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

4

5 of 32

Adjacency matrix

The number of elements in the i^th row whose value is 1 is equal to the out-degree of node V_i
The number of elements in the j^th column whose value is 1 is equal to the in-degree of node V_j
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

V₁

V₂

V₃

V₄

0	1	1
1	0	0
1	1	1
0	1	0

V₁

V₂

V₃

V₄

A =

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

5

6 of 32

Power of Adjacency matrix

Entry of 1 in i^th row and j^th column of A shows existence of an edge (V_i, V_j), that is a path of length 1
Entry in A² shows no of different paths of exactly length 2 from node V_i to V_j
Entry in A³ shows no of different paths of exactly length 3 from node V_i to V_j

0	1	1
1	0	0
1	1	1
0	1	0

A =

A² = A x A =

1	1	0
0	1	1
1	2	1
1	0	0

1	1	1
1	1	0
2	2	1
0	1	1

A³ =

1	2	1
1	1	1
2	3	2
1	1	0

A⁴ =

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

6

7 of 32

Path matrix or reachability matrix

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

7

8 of 32

Adjacency List Representation

0

1

3

2

4

0
1
2
3
4

1

2

3

4

0

3

0

3

4

0

1

2

4

0

2

3

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

8

9 of 32

Graph Traversal

Two Commonly used Traversal Techniques are

Depth First Search (DFS)
Breadth First Search (BFS)

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

9

10 of 32

Depth First Search (DFS)

It is like preorder traversal of tree
Traversal can start from any vertex V_i
V_i is visited and then all vertices adjacent to V_i are traversed recursively using DFS

1

2

3

4

5

6

7

8

DFS (G, 1) is given by

Step 1: Visit (1)

Step 2: DFS (G, 2)

DFS (G, 3)

DFS (G, 4)

DFS (G, 5)

DFS (G, 2):

Step1: Visit(2)

Step 2: DFS (G, 6)

DFS (G, 6):

Step1: Visit(6)

Step 2: DFS (G, 3)

DFS (G, 8)

DFS of given graph starting from node 1 is given by

1

2

6

3

8

7

4

5

✓

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit @ – Non Linear Data Structures (Graph)

10

11 of 32

Depth First Search (DFS)

A

B

C

D

E

F

G

H

A

B

C

D

E

F

R

M

Q

N

P

O

A

B

D

H

E

C

F

G

✓

A

B

D

C

F

E

✓

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

11

12 of 32

Breadth First Search (BFS)

This methods starts from vertex V₀
V₀ is marked as visited. All vertices adjacent to V₀ are visited next
Let vertices adjacent to V₀ are V₁, V₂, V₂, V₄
V₁, V₂, V₃ and V₄ are marked visited
All unvisited vertices adjacent to V₁, V₂, V₃, V₄ 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

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

12

13 of 32

Breadth First Search (BFS)

1

3

4

5

6

7

8

2

A

B

C

D

E

F

G

H

V₀

V₁

V₃

V₂

V₄

V₅

V₆

✓

1

2

3

4

5

6

7

8

|

✓

A

| B C

| D E F G

| H

✓

V₀| V₁V₂ | V₄V₆ V₃ | V₅

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

13

14 of 32

Write DFS & BFS of following Graphs

A

B

C

D

E

F

G

H

A

B

C

D

E

F

R

M

Q

N

P

O

0

1

4

3

5

2

A

B

C

D

E

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

14

15 of 32

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.

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

15

16 of 32

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

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

16

17 of 32

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.

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

17

18 of 32

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)

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

18

19 of 32

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

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

19

20 of 32

Construct Spanning Tree

A

B

C

D

E

F

G

H

A

B

C

D

E

F

G

H

DFS Spanning Tree

BFS Spanning Tree

A

B

C

D

E

F

G

H

A

B

C

D

E

F

A

B

C

D

E

F

A

B

C

D

E

F

DFS Spanning Tree

BFS Spanning Tree

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non-Linear Data Structure (Graph)

20

21 of 32

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

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

21

22 of 32

Prims Algorithm

A

B

C

D

E

4

2

1

7

5

3

6

5

A – B | 4

A – E | 5

A – C | 6

A – D | 6

B – E | 3

B – C | 2

C – E | 5

C – D | 1

D – E | 7

Let X be the set of nodes

explored, initially X = { A }

A

Step 1: Taking minimum Weight edge of all Adjacent edges of X={A}

A

B

4

X = { A , B }

Step 2: Taking minimum weight edge of all Adjacent edges of X = { A , B }

A

B

4

2

C

X = {A ,B,C}

Step 3: Taking minimum weight edge of all Adjacent edges of X = { A , B , C }

A

B

4

2

C

D

1

X = {A,B,C,D}

A

B

4

2

C

D

1

X = {A,B,C,D,E}

Step 4: Taking minimum weight edge of all Adjacent edges of X = {A ,B ,C ,D }

E

3

We obtained minimum spanning tree of cost:

4 + 2 + 1 + 3 = 10

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non-Linear Data Structure (Graph)

22

23 of 32

Kruskal’s Algorithm

A

B

C

D

E

4

2

7

5

3

6

5

Step 1: Taking min edge (C,D)

1

C

D

1

Step 2: Taking next min edge (B,C)

B

C

D

2

1

Step 3: Taking next min edge (B,E)

B

C

D

E

2

3

1

Step 4: Taking next min edge (A,B)

B

C

D

E

2

3

1

A

4

so we obtained minimum

spanning tree of cost:

4 + 2 + 1 + 3 = 10

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

23

24 of 32

Construct Minimum Spanning Tree

0

1

3

4

5

2

3

6

5

3

6

4

1

2

0

1

3

4

5

2

3

4

1

2

3

1

6

4

2

7

5

1

4

1

2

3

2

3

1

4

2

5

1

2

3

7

6

4

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

24

25 of 32

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

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

25

26 of 32

Dijkstra Algorithm – Shortest Path

A

B

C

D

E

F

1

5

2

4

5

7

6

2

A	B	C	D	E	F
0	∞	∞	∞	∞	∞
0	0	0	0	0	0

Distance

Visited

A

B

C

D

E

F

1

5

2

4

5

7

6

2

A	B	C	D	E	F
0			∞	∞	∞
			0	0	0

Distance

Visited

0

1^st Iteration: Select Vertex A with minimum distance

0

∞

1

0

∞

5

1

5

∞

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

26

27 of 32

Dijkstra Algorithm – Shortest Path

A

B

C

D

E

F

1

5

2

4

7

6

2

0

2^nd Iteration: Select Vertex B with minimum distance

1

2

Cost of going to C via B = dist[B] + cost[B][C] = 1 + 1 = 2

Cost of going to D via B = dist[B] + cost[B][D] = 1 + 2 = 3

Cost of going to E via B = dist[B] + cost[B][E] = 1 + 4 = 5

Cost of going to F via B = dist[B] + cost[B][F] = 1 + ∞ = ∞

A	B	C	D	E	F
0	1	5	∞	∞	∞
1	0	0	0	0	0

Distance

Visited

3

5

∞

A	B	C	D	E	F
0	1	2	3	5	∞
			0	0	0

Distance

Visited

1

0

5

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

27

28 of 32

Dijkstra Algorithm – Shortest Path

3^rd Iteration: Select Vertex C via B with minimum distance

A	B	C	D	E	F
0	1	2	3	5	∞
1	1	0	0	0	0

Distance

Visited

A

B

C

D

E

F

1

5

2

4

7

6

2

0

1

3

2

5

∞

Cost of going to D via C = dist[C] + cost[C][D] = 2 + ∞ = ∞

Cost of going to E via C = dist[C] + cost[C][E] = 2 + 5 = 7

Cost of going to F via C = dist[C] + cost[C][F] = 2 + ∞ = ∞

A	B	C	D	E	F
0	1	2	3	5	∞
			0	0	0

Distance

Visited

1

5

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

28

29 of 32

Dijkstra Algorithm – Shortest Path

4^th Iteration: Select Vertex D via path A - B with minimum distance

A	B	C	D	E	F
0	1	2	3	5	∞
1	1	1	0	0	0

Distance

Visited

A

B

C

D

E

F

1

5

2

4

7

6

2

1

3

2

5

9

Cost of going to E via D = dist[D] + cost[D][E] = 3 + 7 = 10

Cost of going to F via D = dist[D] + cost[D][F] = 3 + 6 = 9

A	B	C	D	E	F
0	1	2	3	5	9
			1	0	0

Distance

Visited

1

5

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

29

30 of 32

Dijkstra Algorithm – Shortest Path

4^th Iteration: Select Vertex E via path A – B – E with minimum distance

A	B	C	D	E	F
0	1	2	3	5	9
1	1	1	1	0	0

Distance

Visited

A

B

C

D

E

F

1

5

2

4

7

6

2

1

3

2

5

7

Cost of going to F via E = dist[E] + cost[E][F] = 5 + 2 = 7

A	B	C	D	E	F
0	1	2	3	5	7
			1	1	0

Distance

Visited

1

Shortest Path from A to F is

A 🡪 B 🡪 E 🡪 F = 7

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

30

31 of 32

Shortest Path

Find out shortest path from node 0 to all other nodes using Dijkstra Algorithm

0

1

2

3

4

10

100

30

60

50

10

20

0

1

2

3

4

10

100

30

60

50

10

20

0

10

50

60

30

Dr. Pradyumansinh U. Jadeja

#3130702 (DS) ⬥ Unit 3 – Non Linear Data Structures (Graph)

31

32 of 32

pradyuman.jadeja@darshan.ac.in

+91 9879461848

Computer Engineering Department

Dr. Pradyumansinh Jadeja

Data Structures (DS)

GTU # 3130702

Darshan Institute of Engineering & Technology, Rajkot

Thank

You