Unit 5: Non Linear DS_Graph

UNIT 5
NON-LINEAR DATA STRUCTURES – GRAPH (4 HOURS)

DR. NEEPA SHAH 1

SYLLABUS CONTENT

 Introduction to Graph
 Introduction Graph Terminologies
 Graph Representation
 Type of graphs
 Graph traversal: Depth first search(DFS) & Breadth First search(BFS)
 Minimum Spanning Tree: Prim’s & Kruskal’s
 Shortest Path Algorithm

DR. NEEPA SHAH 2

Dr. Neepa Shah 1

Unit 5: Non Linear DS_Graph

GRAPH APPLICATIONS

 Mapping (GIS)
 Transportation
 Electrical Engineering
 Computer Networks

DR. NEEPA SHAH 3

WHAT IS A GRAPH?

 A graph G = (V, E) is composed of:

V: set of vertices
E: set of edges connecting the vertices in V
 An edge e = (u,v) is a pair of vertices
 Example:

a b V= {a,b,c,d,e}

E= {(a,b),(a,c),(a,d),
(b,e),(c,d),(c,e),
c (d,e)}

d e
DR. NEEPA SHAH 4

Dr. Neepa Shah 2

Unit 5: Non Linear DS_Graph

GRAPH CONCEPTS

 Vertices / Nodes
 Edges / Arcs
 Directed Edge and Undirected Edge
 Directed Graph / Digraph, Undirected Graph, Mixed Graph

DR. NEEPA SHAH 5

GRAPH CONCEPTS CONTD.

 End vertices (end-points): Origin, Destination

 Outgoing and Incoming Edge
 Degree of a vertex
 In-degree and out-degree

DR. NEEPA SHAH 6

Dr. Neepa Shah 3

Unit 5: Non Linear DS_Graph

EXAMPLES

3
0 0 in:1, out: 1

3 1 2 3
1 in: 1, out: 2
3G1
3

2 in: 1, out: 0

DR. NEEPA SHAH 7

TERMINOLOGY: PATH

3 2

3 3
 Path: sequence of vertices v1,v2,...vk
such that consecutive vertices vi and
vi+1 are adjacent. a b a b

c c

d e d e
abedc bedc

DR. NEEPA SHAH 8

Dr. Neepa Shah 4

Unit 5: Non Linear DS_Graph

TERMINOLOGY: PATH CONTD.

a b

 Simple path: no repeated vertices c

bec

 Cycle: simple path, except that the d e

last vertex is the same as the first
vertex a b

acda
c

d e

DR. NEEPA SHAH 9

SUBGRAPHS EXAMPLES

0
0 0 1 2 0

1 2
1 2 3 1 2
3
G1 3

(i) (ii) (iii) (iv)

(a) Some of the subgraph of G1

DR. NEEPA SHAH 10

Dr. Neepa Shah 5

Unit 5: Non Linear DS_Graph

CONNECTIVITY

 Let n = #vertices, and m = #edges

 A complete graph: one in which all pairs of vertices are adjacent
 How many total edges in a complete graph?
 Each of the n vertices is incident to n-1 edges, however, we would have counted each edge
twice! Therefore, intuitively, m = n(n -1)/2.
 Therefore, if a graph is not complete, m < n(n -1)/2

n=5
m = (5  ) = 

DR. NEEPA SHAH 11

TYPES OF GRAPHS

 Regular graph: ‘k’-regular graph -> If all the graph nodes have the same degree
value, then the graph is called a regular graph. (same number of neighbors)

 Complete graph: for all the vertices of the graph, there exists an edge between every
pair of the vertices.

DR. NEEPA SHAH 12

Dr. Neepa Shah 6

Unit 5: Non Linear DS_Graph

TYPES OF GRAPHS CONTD.

 Cycle graph: the degree of all the

vertices of the cycle graph is 2.
 Weighted graph
 Cyclic graph: has at least one cycle
 Acyclic graph

DR. NEEPA SHAH 13

ADT FOR GRAPH

 Create()
 InsertVertex (graph, v)
 InsertEdge (graph, v1,v2)
 DeleteVertex (graph, v)
 DeleteEdge (graph, v1, v2)
 IsEmpty (graph)

DR. NEEPA SHAH 14

Dr. Neepa Shah 7

Unit 5: Non Linear DS_Graph

DATA STRUCTURES FOR GRAPHS

 Adjacency List
 Adjacency Matrix

DR. NEEPA SHAH 15

ADJACENCY MATRIX REPRESENTATION

 In this representation, each graph of n nodes is represented by an n x n matrix A, that is, a two-
dimensional array A
 The nodes are (re)-labeled 1,2,…,n
 A[i][j] = 1 if (i,j) is an edge
 A[i][j] = 0 if (i,j) is not an edge

DR. NEEPA SHAH 16

Dr. Neepa Shah 8

Unit 5: Non Linear DS_Graph

EXAMPLE OF ADJACENCY MATRIX

1
0
0 1 0 1 0
0 0 1 0 0
A= 0 0 1 0 0 2
1 0 0 0 0
0 0 0 1 0 4

DR. NEEPA SHAH 17

PROS AND CONS OF ADJACENCY MATRICES

 Pros:
 Simple to implement
 Easy and fast to tell if a pair (i,j) is an edge: simply check if A[i][j] is 1 or 0
 Cons:
 No matter how few edges the graph has, the matrix takes O(n 2) in memory

DR. NEEPA SHAH 18

Dr. Neepa Shah 9

Unit 5: Non Linear DS_Graph

ADJACENCY LISTS REPRESENTATION

 A graph of n nodes is represented by a one-dimensional array L of linked lists, where

 L[i] is the linked list containing all the nodes adjacent from node i.
 The nodes in the list L[i] are in no particular order

DR. NEEPA SHAH 19

EXAMPLE OF LINKED REPRESENTATION

0 1
L[0]: empty
L[1]: empty 3
2
L[2]: 0, 1, 4, 5
L[3]: 0, 1, 4, 5 5
4
L[4]: 0, 1
L[5]: 0, 1

DR. NEEPA SHAH 20

Dr. Neepa Shah 10

Unit 5: Non Linear DS_Graph

EXAMPLE OF LINKED REPRESENTATION

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

DR. NEEPA SHAH 21

PROS AND CONS OF ADJACENCY LISTS

 Pros:
 Saves on space (memory): the representation takes as many memory words as there are nodes and
edge.
 Cons:
 It can take up to O(n) time to determine if a pair of nodes (i,j) is an edge: one would have to search
the linked list L[i], which takes time proportional to the length of L[i].

DR. NEEPA SHAH 22

Dr. Neepa Shah 11

Unit 5: Non Linear DS_Graph

EXAMPLE

DR. NEEPA SHAH 23

EXAMPLE: SOLUTION

DR. NEEPA SHAH 24

Dr. Neepa Shah 12

Unit 5: Non Linear DS_Graph

EXERCISE

DR. NEEPA SHAH 26

EXERCISE CONTD.

DR. NEEPA SHAH 27

Dr. Neepa Shah 13

Unit 5: Non Linear DS_Graph

GRAPH TRAVERSAL

 Problem: Search for a certain node or traverse all nodes in the graph
 Depth First Search
 Once a possible path is found, continue the search until the end of the path
 Breadth First Search
 Start several paths at a time, and advance in each one step at a time

DR. NEEPA SHAH 31

GRAPH TRAVERSAL CONTD.

 In both DFS and BFS, the nodes of the undirected graph are visited in a
systematic manner so that every node is visited exactly one.
 Both BFS and DFS give rise to a tree:
 When a node x is visited, it is labeled as visited, and it is added to the tree
 If the traversal got to node x from node y, y is viewed as the parent of x, and x a child
of y

DR. NEEPA SHAH 32

Dr. Neepa Shah 14

Unit 5: Non Linear DS_Graph

DEPTH-FIRST TRAVERSAL IDEA

 In this method, After visiting a vertex v, which is adjacent to w1, w2, w3,
...; Next we visit one of v's adjacent vertices, w1 say. Next, we visit all
vertices adjacent to w1 before coming back to w2, etc.

 Must keep track of vertices already visited to avoid cycles.

 The method can be implemented using recursion or stack.

DR. NEEPA SHAH 33

DEPTH-FIRST SEARCH PROCEDURE

1. Select an unvisited node x, visit it, and treat as the current node
2. Find an unvisited neighbor of the current node, visit it, and make it the new
current node;
3. If the current node has no unvisited neighbors, backtrack to its parent, and
make that parent the new current node;
4. Repeat steps 3 and 4 until no more nodes can be visited.

DR. NEEPA SHAH 34

Dr. Neepa Shah 15

Unit 5: Non Linear DS_Graph

EXAMPLE

5 2
0

1 3
7

4
6

Policy: Visit adjacent nodes in increasing index order

DR. NEEPA SHAH 35

DFS: Start with Node 5

5 2
0

1 3
7

4
6

5 1 0 3 2 7 6 4
DR. NEEPA SHAH 36

Dr. Neepa Shah 16

Unit 5: Non Linear DS_Graph

DFS: Contd.

5 2
0

1 3
7
5
4
6
Push 5

DR. NEEPA SHAH 37

DFS: Contd.

5 2
0

1 3
7

4
6
Pop/Visit/Mark 5

5
DR. NEEPA SHAH 38

Dr. Neepa Shah 17

Unit 5: Non Linear DS_Graph

DFS: Contd.

5 2
0

1 3
7 1
2
4
6
Push 2, Push 1

5
DR. NEEPA SHAH 39

DFS: Contd.

5 2
0

1 3
7
2
4
6
Pop/Visit/Mark 1

5 1
DR. NEEPA SHAH 40

Dr. Neepa Shah 18

Unit 5: Non Linear DS_Graph

DFS: Contd.

5 2
0 0
2
1 3
7 4
2
4
6
Push 4, Push 2, Push 0

5 1
DR. NEEPA SHAH 41

DFS: Contd.

5 2
0

2
1 3
7 4
2
4
6
Pop/Visit/Mark 0

5 1 0
DR. NEEPA SHAH 42

Dr. Neepa Shah 19

Unit 5: Non Linear DS_Graph

DFS: Contd.

5 3
2
0 7
2
1 3
7 4
2
4
6
Push 7, Push 3

5 1 0
DR. NEEPA SHAH 43

DFS: Contd.

5 2
0 7
2
1 3
7 4
2
4
6
Pop/Visit/Mark 3

5 1 0 3
DR. NEEPA SHAH 44

Dr. Neepa Shah 20

Unit 5: Non Linear DS_Graph

DFS: Contd.

5 2
2
0 7
2
1 3
7 4
2
4
6
Push 2

5 1 0 3
DR. NEEPA SHAH 45

DFS: Contd.

5 2
0 7
2
1 3
7 4
2
4
6
Pop/Mark/Visit 2

5 1 0 3 2
DR. NEEPA SHAH 46

Dr. Neepa Shah 21

Unit 5: Non Linear DS_Graph

DFS: Contd.

5 2
0

2
1 3
7 4
2
4
6
Pop/Mark/Visit 7

5 1 0 3 2 7
DR. NEEPA SHAH 47

DFS: Contd.

5 2
0 6
2
1 3
7 4
2
4
6
Push 6

5 1 0 3 2 7
DR. NEEPA SHAH 48

Dr. Neepa Shah 22

Unit 5: Non Linear DS_Graph

DFS: Contd.

5 2
0

2
1 3
7 4
2
4
6
Pop/Mark/Visit 6

5 1 0 3 2 7 6
DR. NEEPA SHAH 49

DFS: Contd.

5 2
0

1 3
7 4
2
4
6
Pop (don’t visit) 2

5 1 0 3 2 7 6
DR. NEEPA SHAH 50

Dr. Neepa Shah 23

Unit 5: Non Linear DS_Graph

DFS: Contd.

5 2
0

1 3
7
2
4
6
Pop/Mark/Visit 4

5 1 0 3 2 7 6 4
DR. NEEPA SHAH 51

DFS: Contd.

5 2
0

1 3
7

4
6
Pop (don’t visit) 2

5 1 0 3 2 7 6 4
DR. NEEPA SHAH 52

Dr. Neepa Shah 24

Unit 5: Non Linear DS_Graph

DFS: Contd.

5 2
0

1 3
7

4
6
Done

5 1 0 3 2 7 6 4
DR. NEEPA SHAH 53

DFS: Contd. Edge (0,3) removed

5 2
0

1 3
7

4
6

5 1 0 7 6 2 4 3
DR. NEEPA SHAH 54

Dr. Neepa Shah 25

Unit 5: Non Linear DS_Graph

EXAMPLE

Order of
Traversal A B C F E G D H I Stack
DR. NEEPA SHAH 55

ILLUSTRATION OF DFS
0 1
0
2
1
9 4
4
10 5 7
2
11 8
5 9
6
7 11
6 Graph G
8 10

DFS Tree
DR. NEEPA SHAH 56

Dr. Neepa Shah 26

Unit 5: Non Linear DS_Graph

IMPLEMENTATION OF DFS

 The last node visited is the first node from which to proceed.
 Also, the backtracking proceeds on the basis of "last visited, first to backtrack
too".
 This suggests that a stack is the proper data structure to remember the current
node and how to backtrack.

DR. NEEPA SHAH 57

DFS ALGORITHM

DFS(input: Graph G)
Stack S;
int x, t;
while (G has an unvisited node x)
visit(x); push(x, S);
while (S is not empty)
t = peek(S);
if (t has an unvisited neighbor y)
visit(y); push(y,S);
else
pop(S);
DR. NEEPA SHAH 58

Dr. Neepa Shah 27

Unit 5: Non Linear DS_Graph

EXERCISE

DR. NEEPA SHAH 59

EXERCISE CONTD.

https://visualgo.net/en/dfsbfs

DR. NEEPA SHAH 60

Dr. Neepa Shah 28

Unit 5: Non Linear DS_Graph

EXERCISE CONTD.

DR. NEEPA SHAH 61

BREADTH-FIRST TRAVERSAL ALGORITHM

 In this method, After visiting a vertex v, we must visit all its adjacent
vertices w1, w2, w3, ..., before going down next level to visit vertices
adjacent to w1 etc.
 The method can be implemented using a queue.
 A boolean array is used to ensure that a vertex is enqueued only once.

DR. NEEPA SHAH 62

Dr. Neepa Shah 29

Unit 5: Non Linear DS_Graph

BREADTH-FIRST SEARCH PROCEDURE

1. Select an unvisited node x, visit it, let it be the root in a BFS tree being
formed. Its level is called the current level.
2. From each node z in the current level, in the order in which the level
nodes were visited, visit all the unvisited neighbors of z. The newly
visited nodes from this level form a new level that becomes the next
current level.
3. Repeat step 2 until no more nodes can be visited.
4. If there are still unvisited nodes, repeat from Step 1.

DR. NEEPA SHAH 63

BFS - A Graphical Representation

0 0 1

A B C D A B C D

E F G H E F G H

a) I J K L I J K L b)

M N O P M N O P

0 1 2 0 1 2 3

A B C D A B C D

E F G H E F G H
c) d)
I J K L
I J K L

M N O P
M N O P 64

DR. NEEPA SHAH

Dr. Neepa Shah 30

Unit 5: Non Linear DS_Graph

BFS - A Graphical Representation Contd.

BFS CONTD.

0 1 2 3 0 1 2 3

A B C D A B C D

E F G H E F G H

4 4
I J K L I J K L

M N O P M N O P 5

DR. NEEPA SHAH

65

BFS: Start with Node 5

5 2
0

1 3
7

4
6

5 1 2 0 4 3 7 6
DR. NEEPA SHAH 66

Dr. Neepa Shah 31

Unit 5: Non Linear DS_Graph

BFS: Contd.

5 2
0

1 3
7

4
6

5
DR. NEEPA SHAH 67

BFS: Contd.

5 2
0

1 3
7

4
6

5
DR. NEEPA SHAH 68

Dr. Neepa Shah 32

Unit 5: Non Linear DS_Graph

BFS:Visit 1 and 2

5 2
0

1 3
7

4
6

5 1 2
DR. NEEPA SHAH 69

BFS: Nodes two-away

5 2
0

1 3
7

4
6

5 1 2
DR. NEEPA SHAH 70

Dr. Neepa Shah 33

Unit 5: Non Linear DS_Graph

BFS:Visit 0 and 4

5 2
0

1 3
7

4
6

5 1 2 0 4
DR. NEEPA SHAH 71

BFS: Contd.

5 2
0

1 3
7

4
6

5 1 2 0 4
DR. NEEPA SHAH 72

Dr. Neepa Shah 34

Unit 5: Non Linear DS_Graph

BFS:Visit nodes 3 and 7

5 2
0

1 3
7

4
6

5 1 2 0 4 3 7
DR. NEEPA SHAH 73

BFS: Contd.

5 2
0

1 3
7

4
6

5 1 2 0 4 3 7
DR. NEEPA SHAH 74

Dr. Neepa Shah 35

Unit 5: Non Linear DS_Graph

BFS:Visit 6

5 2
0

1 3
7

4
6

5 1 2 0 4 3 7 6
DR. NEEPA SHAH 75

ILLUSTRATION OF BFS

0 1
0
2 4 2
1
9 4
5 9 10
10 5 7

11 8
6 7 8 11
6
BFS Tree Graph G

DR. NEEPA SHAH 76

Dr. Neepa Shah 36

Unit 5: Non Linear DS_Graph

IMPLEMENTATION OF BFS

 The first node visited in each level is the first node from which to
proceed to visit new nodes.
 This suggests that a queue is the proper data structure to remember the
order of the steps.

DR. NEEPA SHAH 77

BFS ALGORITHM

BFS(input: graph G)
Queue Q;
int x, z, y;
while (G has an unvisited node x)
visit(x); Enqueue(x,Q);
while (Q is not empty)
z = Dequeue(Q);
for all (unvisited neighbor y of z)
visit(y); Enqueue(y,Q);
DR. NEEPA SHAH 78

Dr. Neepa Shah 37

Unit 5: Non Linear DS_Graph

EXAMPLE: WITH U AS THE START NODE

DR. NEEPA SHAH 79

EXERCISE

DR. NEEPA SHAH 80

Dr. Neepa Shah 38

Unit 5: Non Linear DS_Graph

EXAMPLES:TRAVERSAL (BOTH)

DR. NEEPA SHAH 81

SOLUTION TREE

DR. NEEPA SHAH 82

Dr. Neepa Shah 39

Unit 5: Non Linear DS_Graph

SOLUTION TREE CONTD.

DR. NEEPA SHAH 83

MINIMUM SPANNING TREE

DR. NEEPA SHAH 84

Dr. Neepa Shah 40

Unit 5: Non Linear DS_Graph

SPANNING TREES
A spanning tree of a graph is just a subgraph that contains all the vertices and is
a tree.
A graph may have many spanning trees.

Graph A Some Spanning Trees from Graph A

o o o
r r r

DR. NEEPA SHAH 85

MINIMUM SPANNING TREE

The Minimum Spanning Tree for a given graph is the Spanning Tree of minimum
cost for that graph.

Complete Graph Minimum Spanning Tree

2 2
5 3 3

1 1

DR. NEEPA SHAH 86

Dr. Neepa Shah 41

Unit 5: Non Linear DS_Graph

MINIMUM SPANNING TREE: EXAMPLE

An undirected graph and its minimum spanning tree.

DR. NEEPA SHAH 87

APPLICATIONS OF MST

 Find the least expensive way to connect a set of cities, terminals, computers, etc.

88 NEEPA SHAH
DR.

Dr. Neepa Shah 42

Unit 5: Non Linear DS_Graph

EXAMPLE

 Problem
 A town has a set of houses and a set of roads
8 7
 A road connects 2 and only 2 houses b c d
4 9
 A road connecting houses u and v has a repair cost w(u, v) 2
a 11 i 4 14 e
7 6
 Goal: Repair enough (and no more) roads such that: 8 10
 Everyone stays connected h g f
1 2
 i.e., can reach every house from all other houses
 Total repair cost is minimum

89 NEEPA SHAH
DR.

ALGORITHMS FOR OBTAINING THE MST

 Kruskal's Algorithm

 Prim's Algorithm

DR. NEEPA SHAH 90

Dr. Neepa Shah 43

Unit 5: Non Linear DS_Graph

KRUSKAL'S ALGORITHM

 This algorithm creates a forest of trees. Initially the forest consists of n single
node trees (and no edges). At each step, we add one edge (the cheapest one) so
that it joins two trees together. If it were to form a cycle, it would simply link
two nodes that were already part of a single connected tree, so that this edge
would not be needed.

DR. NEEPA SHAH 91

KRUSKAL’S ALGORITHM CONTD.

 Step 1: Choose the arc of least weight.

 Step 2: Choose from those arcs remaining the arc of least
weight which does not form a cycle with already chosen
arcs. (If there are several such arcs, choose one arbitrarily.)
 Step 3: Repeat Step 2 until n – 1 arcs have been chosen.

DR. NEEPA SHAH 92

Dr. Neepa Shah 44

Unit 5: Non Linear DS_Graph

Complete Graph

B 4 C
4
2 1

A 4 E
1 F

D 2 3
10
G 5

5 6 3

4
I
H

2 3
J
DR. NEEPA SHAH 93

A 4 B A 1 D

B 4 C B 4 D

B 4 C B 10 J C 2 E
4
2 1
C 1 F D 5 H
A 4 E
1 F

2 D 6 J E 2 G
D 3
10
G 5
F 3 G F 5 I
5 6 3

4
I G 3 I G 4 J
H

2 3
J H 2 J I 3 J
DR. NEEPA SHAH 94

Dr. Neepa Shah 45

Unit 5: Non Linear DS_Graph

Sort Edges A 1 D C 1 F
(in reality they are placed in a priority
queue) 2 2
C E E G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J
DR. NEEPA SHAH 95

Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J
DR. NEEPA SHAH 96

Dr. Neepa Shah 46

Unit 5: Non Linear DS_Graph

Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J
DR. NEEPA SHAH 97

Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J
DR. NEEPA SHAH 98

Dr. Neepa Shah 47

Unit 5: Non Linear DS_Graph

Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J
DR. NEEPA SHAH 99

Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J
DR. NEEPA SHAH 100

Dr. Neepa Shah 48

Unit 5: Non Linear DS_Graph

Cycle A 1 D C 1 F
Don’t Add Edge
C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J
DR. NEEPA SHAH 101

Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J
DR. NEEPA SHAH 102

Dr. Neepa Shah 49

Unit 5: Non Linear DS_Graph

Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J
DR. NEEPA SHAH 103

Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J
DR. NEEPA SHAH 104

Dr. Neepa Shah 50

Unit 5: Non Linear DS_Graph

Cycle A 1 D C 1 F
Don’t Add Edge
C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J
DR. NEEPA SHAH 105

Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J
DR. NEEPA SHAH 106

Dr. Neepa Shah 51

Unit 5: Non Linear DS_Graph

Minimum Spanning Tree Complete Graph

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

D 2 2
D 3
10
G G 5

3 5 6 3

4
I I
H H
2 3 3
J 2 J
DR. NEEPA SHAH 107

PRIM'S ALGORITHM

 This algorithm starts with one node. It then, one by one,

adds a node that is unconnected to the new graph to the
new graph, each time selecting the node whose connecting
edge has the smallest weight out of the available nodes’
connecting edges.

DR. NEEPA SHAH 108

Dr. Neepa Shah 52

Unit 5: Non Linear DS_Graph

PRIM’S ALGORITHM CONTD.

 Step 1: Select any node to be the first node of T.

 Step 2: Consider the arcs which connect nodes in T to
nodes outside T. Pick the one with minimum weight. Add this
arc and the extra node to T. (If there are two or more arcs
of minimum weight, choose any one of them.)
 Step 3: Repeat Step 2 until T contains every node of the
graph.

DR. NEEPA SHAH 109

Complete Graph

B 4 C
4
2 1

A 4 E
1 F

D 2 3
10
G 5

5 6 3

4
I
H

2 3
J
DR. NEEPA SHAH 110

Dr. Neepa Shah 53

Unit 5: Non Linear DS_Graph

Old Graph New Graph

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
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
2 3
DR. NEEPA SHAH
J 111

Old Graph New Graph

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
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
2 3
DR. NEEPA SHAH
J 112

Dr. Neepa Shah 54

Unit 5: Non Linear DS_Graph

Old Graph New Graph

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
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
2 3
DR. NEEPA SHAH
J 113

Old Graph New Graph

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
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
2 3
DR. NEEPA SHAH
J 114

Dr. Neepa Shah 55

Unit 5: Non Linear DS_Graph

Old Graph New Graph

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
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
2 3
DR. NEEPA SHAH
J 115

Old Graph New Graph

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
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
2 3
DR. NEEPA SHAH
J 116

Dr. Neepa Shah 56

Unit 5: Non Linear DS_Graph

Old Graph New Graph

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
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
2 3
DR. NEEPA SHAH
J 117

Old Graph New Graph

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
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
2 3
DR. NEEPA SHAH
J 118

Dr. Neepa Shah 57

Unit 5: Non Linear DS_Graph

Old Graph New Graph

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
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
2 3
DR. NEEPA SHAH
J 119

Old Graph New Graph

B 4 C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
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
2 3
DR. NEEPA SHAH
J 120

Dr. Neepa Shah 58

Unit 5: Non Linear DS_Graph

Complete Graph Minimum Spanning Tree

B 4 C
4 B 4 C
2 1 4
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
2 3
DR. NEEPA SHAH
J 121

EXAMPLE: KRUSKAL

Dr. Neepa Shah 59

Unit 5: Non Linear DS_Graph

STAGES OF MST CONSTRUCTION

STAGES

Dr. Neepa Shah 60

Unit 5: Non Linear DS_Graph

SOLVING KRUSKAL ALGORITHM: 1

DR. NEEPA SHAH 125

SOLVING KRUSKAL ALGORITHM: 1: SOLUTION

DR. NEEPA SHAH 126

Dr. Neepa Shah 61

Unit 5: Non Linear DS_Graph

SOLVING KRUSKAL ALGORITHM: 2

Kruskal Algorithm a
6 4
 A={ }, Make each element its own set.
5 9
{a} {b} {c} {d} {e} {f} {g} {h} b c d
 Sort edges.
14
 Look at smallest edge first: {c} and {f} not in same 2
set, add it to A, union together. 10
e f g
 {a} {b} {c f} {d} {e} {g} {h}; A = {(c f)}
15
 {a} {b} {c f} {d} {e h} {g}; A = {(c f), (e h)} 3
8
 {a c f} {b} {d} {e h} {g} h
 {a b c f} {d} {e h} {g}
 {a b c e f h} {d} {g}
 {a b c d e f h} {g}
 {a b c d e f h} {g}

DR. NEEPA SHAH 127

SOLVING KRUSKAL ALGORITHM: 2: SOLUTION

a
6 4
5 9
b c d
 Do add the last one:
14
 Had {a b c d e f h g} 2
10
e f g
15
3 8
h

DR. NEEPA SHAH 128

Dr. Neepa Shah 62

Unit 5: Non Linear DS_Graph

KRUSKAL’S ALGORITHM: EXAMPLES

B
1
A
1 C
2
5 2
2 D 4
1 2
E 3
G
1 2
F

DR. NEEPA SHAH 129

PRIM’S EXAMPLE

Example:
Example: Graph givenGraph
earlier.given earlier.
 ) (e,0)
Q={ (e,0) (a,Q={ (b, (a, 
) (c, ) (b, 
) (d, ) (c, 
) (f, ) (d, 
) (g, ) (f, 
) (h, ) } ) (h,  ) }
) (g,

inf inf
a a
6 64 4
inf inf inf infinf inf
5 b 5 9 9
b c dc d

14 14
2 2
10 10 inf inf
e e f fg g
0/nil 0/nil 15 15
3 3 inf inf
8 8
h h

inf inf

Extract min,Extract min,

vertex e. vertexneighbor
Update e. Update neighbor
if in if in Q <and
Q and weight weight < key.
key.

DR. NEEPA SHAH 130

Dr. Neepa Shah 63

Unit 5: Non Linear DS_Graph

PRIM’S EXAMPLE
inf
a
6 4
14/e inf inf
5 9
b c d

14
2
10 inf
e f g
0/nil 15
3 inf
8
h

3/e
Q={ (a,  ) (b,14) (c,  ) (d,  ) (f,  ) (g,  ) (h,3) }

Extract min, vertex h. Update neighbor if in Q and weight < key

DR. NEEPA SHAH 131

PRIM’S ALGORITHM

inf
a
6 4
10/h inf inf
5 9
b c d

14
2
10 inf
e f g
0/nil 15
3 8/h
h 8

3/e

Q={ (a,  ) (b,10) (c,  ) (d,  ) (f,8) (g,  ) }

Extract min, vertex f. Update neighbor if in Q and weight < key

DR. NEEPA SHAH 132

Dr. Neepa Shah 64

Unit 5: Non Linear DS_Graph

PRIM’S ALGORITHM

inf
a
6 4
10/h 2/f inf
5 9
b c d

14
2
10 15/f
e f g
0/nil 15
3 8/h
h 8

3/e
Q={ (a,  ) (b,10) (c, 2) (d,  ) (g,15) }

Extract min, vertex c. Update neighbor if in Q and weight < key

DR. NEEPA SHAH 133

PRIM’S ALGORITHM

4/c
a
6 4
5/c 2/f 9/c
5 9
b c d

14
2
10 15/f
e f g
0/nil 15
3 8/h
h 8

3/e
Q={ (a,4) (b,5) (d,9) (g,15) }

Extract min, vertex a. No keys are smaller than edges from a (4>2 on edge ac, 6>5 on edge ab) so nothing
done.

Q={ (b,5) (d,9) (g,15) }

Extract min, vertex b.

Same case, no keys are smaller than edges, so nothing is done.

Same for extracting d and g, and we are done.

DR. NEEPA SHAH 134

Dr. Neepa Shah 65

Unit 5: Non Linear DS_Graph

PRIM’S ALGORITHM

4/c
a
6 4
5/c 2/f 9/c
5 9
b c d

14
2
10 15/f
e f g
0/nil 15
3 8/h
8
h

3/e

DR. NEEPA SHAH 135

PRIM EXERCISE

DR. NEEPA SHAH 136

Dr. Neepa Shah 66

Unit 5: Non Linear DS_Graph

EXERCISE

DR. NEEPA SHAH 138

DIFFERENCES

Dr. Neepa Shah 67

Unit 5: Non Linear DS_Graph

MINIMUM SPANNING TREES: EXERCISES

B
1
A
1 C
2
5 2
2 D
4
1 2
E 3 G
1 2
F

3
10
F C
A 4
4
3
8
6
5
4
B D
4
H 1
2
3
G 3
E
8 7
DR. NEEPA SHAH 140

MINIMUM SPANNING TREES: EXERCISES CONTD.

DR. NEEPA SHAH

142

Dr. Neepa Shah 68

Unit 5: Non Linear DS_Graph

DIJKSTRA EXAMPLE

DIJKSTRA EXAMPLE CONTD.

Dr. Neepa Shah 69

Unit 5: Non Linear DS_Graph

DIJKSTRA EXAMPLE CONTD.

DIJKSTRA EXAMPLE CONTD.

Dr. Neepa Shah 70

Unit 5: Non Linear DS_Graph

DIJKSTRA EXAMPLE CONTD.

DIJKSTRA EXAMPLE CONTD.

Dr. Neepa Shah 71

Unit 5: Non Linear DS_Graph

DIJKSTRA EXAMPLE CONTD.

DIJKSTRA EXAMPLE CONTD.

Dr. Neepa Shah 72

Unit 5: Non Linear DS_Graph

DIJKSTRA EXAMPLE CONTD.

DIJKSTRA EXAMPLE CONTD.

Dr. Neepa Shah 73

Unit 5: Non Linear DS_Graph

DIJKSTRA EXAMPLE CONTD.

DR. NEEPA SHAH 154

DIJKSTRA EXAMPLE CONTD.

DR. NEEPA SHAH 155

Dr. Neepa Shah 74

Unit 5: Non Linear DS_Graph

DIJKSTRA EXAMPLE CONTD.

DR. NEEPA SHAH 156

SINGLE SOURCE SHORTEST PATH (DIJKSTRA'S ALGORITHM) CONTD.

Distance(source) = 0
0  Distance (all vertices but source) = 
2
A B

4 1 3 10

2 2
 C D E

5 8  4 6
Relax A B C D E F G

1
A 0 ∞ ∞ ∞ ∞ ∞ ∞
F G

 

Pick vertex in List with minimum distance.

157

DR. NEEPA SHAH

Dr. Neepa Shah 75

Unit 5: Non Linear DS_Graph

SINGLE SOURCE SHORTEST PATH (DIJKSTRA'S ALGORITHM) CONTD.

0 2 Relax A B C D E F G

A
2
B
A 0 ∞ ∞ ∞ ∞ ∞ ∞
D 2 ∞ 1 ∞ ∞ ∞
4 1 3 10 B 2 3 3 9 5
E 3 3 9 5
2 2
3 C D E 3 C 3 9 5
G 8 5
5 8 1 4 6 F 6

1
F G

6 5

DR. NEEPA SHAH 158

EXERCISE: MST, SSSP

1 c
a
1
3 2

s 4 1
4
6
1
b d
3

DR. NEEPA SHAH 159

Dr. Neepa Shah 76

Unit 5: Non Linear DS_Graph

EXERCISE: MST, SSSP CONTD.

 MST and Dijkstra (Shortest path A to H)

 MST and Dijkstra (Shortest path A to D)
 MST and Dijkstra (Shortest path A to D)

DR. NEEPA SHAH 160

EXERCISE: MST, SSSP CONTD.

15
t a 6
9
14
3 4 e
10 13 c
s 11
20 5
17 2 7 g
b 8
u f 22
1 12
16
v
DR. NEEPA SHAH 162

Dr. Neepa Shah 77