Data Structures

II B.Tech I-Sem IT
Unit-IV

DS UNIT-IV 1
Unit-IV Syllabus:

Graphs
 Graph Implementation Methods.
 Graph Traversal Methods
Sorting
 Heap Sort
 External Sorting- Model for external sorting,
 Merge Sort.

UNIT-IV 2
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),
c (a,d),
(b,e),(c,d),(c,e),
(d,e)}
d UNIT-IV
e 3
Definitions and Representation
• An undirected graph G is a pair (V,E), where V is a finite
set of points called vertices and E is a finite set of edges.
• An edge e ∈ E is an unordered pair (u,v), where u,v ∈ V.
• In a directed graph, the edge e is an ordered pair (u,v). An
edge (u,v) is incident from vertex u and is incident to
vertex v.
• A path from a vertex v to a vertex u is a sequence
<v0,v1,v2,…,vk> of vertices where v0 = v, vk = u, and (vi, vi+1)
∈ E for I = 0, 1,…, k-1.
• The length of a path is defined as the number of edges in
the path.
DS UNIT-IV 4
Definitions and Representation
• An undirected graph is connected if every
pair of vertices is connected by a path.
• A forest is an acyclic graph, and a tree is a
connected acyclic graph.
• A graph that has weights associated with
each edge is called a weighted graph.

DS UNIT-IV 5
 Graph Representations

• Adjacency Matrix
• Adjacency Lists

DS UNIT-IV 6
Examples for Adjacency Matrix
0 4
0 2 1 5

1 2 3 6

3 7
0 1 1 1
1 0 1 1 0 0 0 0 0
0 1 1  1

 0 0 1 0 0 0 0
1 1 0 1
  1 0 0 1 0 0 0 0
1 1 1 0  
0 1 1 0 0 0 0 0
0 0 0 0 0 1 0 0
 
0 0 0 0 1 0 1 0
0 0 0 0 0 1 0 1
 
 0
DS UNIT-IV 0 0 0 0 0 1 0 7
Examples for Adjacency Matrix

0
 0 1 0
 
 1 0 1 
1  0 0 0

DS UNIT-IV 8
Examples for Adjacency Lists
0 4
0 2 1 5
3 6
1 2
7
3
0 1 2
0 1 2 3 1 0 3
1 0 2 3 2 0 3
2 0 1 3 3 1 2
3 0 1 2 4 5
5 4 6
6 5 7
DS UNIT-IV 7 6 9
Examples for Adjacency Lists

0
0 1
1 1 0 2
2
2

DS UNIT-IV 10
Definitions and Representation

An undirected graph and its adjacency matrix representation.

An undirected graph and its adjacency list representation.

DS UNIT-IV 11
 Breadth-First Search

• Visit start vertex and put into a FIFO queue.

• Repeatedly remove a vertex from the queue,
visit its unvisited adjacent vertices, put newly
visited vertices into the queue.

DS UNIT-IV 12
Breadth-First Search
// non-recursive, preorder, breadth-first search
void bfs (Node v) {
if (v == null)
return;

enqueue(v);
while (queue is not empty) {
dequeue(v);
if (v has not yet been visited)
mark&visit(v);

for (each w adjacent to v)

if (w has not yet been visited && has not been queued)
enqueue(w);
} // while

} // bfs

DS UNIT-IV 13
BFS: Start with Node 5

5
2
0

1 3
7

6 4

5 1 2 0 4 3 7 6

DS UNIT-IV 14
BFS: Start with Node 5

5
2
0

1 3
7

6 4

DS UNIT-IV 15
BFS: Node one-away

5
2
0

1 3
7

6 4

DS UNIT-IV 16
BFS: Visit 1 and 2

5
2
0

1 3
7

6 4

5 1 2

DS UNIT-IV 17
BFS: Nodes two-away

5
2
0

1 3
7

6 4

5 1 2

DS UNIT-IV 18
BFS: Visit 0 and 4

5
2
0

1 3
7

6 4

5 1 2 0 4

DS UNIT-IV 19
BFS: Nodes three-away

5
2
0

1 3
7

6 4

5 1 2 0 4

DS UNIT-IV 20
BFS: Visit nodes 3 and 7

5
2
0

1 3
7

6 4

5 1 2 0 4 3 7

DS UNIT-IV 21
BFS: Node four-away

5
2
0

1 3
7

6 4

5 1 2 0 4 3 7

DS UNIT-IV 22
BFS: Visit 6

5
2
0

1 3
7

6 4

5 1 2 0 4 3 7 6

DS UNIT-IV 23
 Breadth-First Search Example
2
3
8
1

4
5
9

6
7

Start search at vertexDS1.UNIT-IV 24

 Breadth-First Search Example
2
3
FIFO Queue
8
1 1
4
5
9

6
7

Visit/mark/label start vertex and put in a FIFO queue.25

DS UNIT-IV
 Breadth-First Search Example
2
3
FIFO Queue
8
1 1
4
5
9

6
7

Remove 1 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 26
 Breadth-First Search Example
2
3
FIFO Queue
8 2 4
1

4
5
9

6
7

Remove 1 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 27
 Breadth-First Search Example
2
3
FIFO Queue
8 2 4
1

4
5
9

6
7

Remove 2 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 28
 Breadth-First Search Example
2
3
FIFO Queue
8 4 5 3 6
1

4
5
9

6
7

Remove 2 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 29
 Breadth-First Search Example
2
3
FIFO Queue
8 4 5 3 6
1

4
5
9

6
7

Remove 4 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 30
 Breadth-First Search Example
2
3
FIFO Queue
8 5 3 6
1

4
5
9

6
7

Remove 4 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 31
 Breadth-First Search Example
2
3
FIFO Queue
8 5 3 6
1

4
5
9

6
7

Remove 5 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 32
 Breadth-First Search Example
2
3
FIFO Queue
8 3 6 9 7
1

4
5
9

6
7

Remove 5 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 33
 Breadth-First Search Example
2
3
FIFO Queue
8 3 6 9 7
1

4
5
9

6
7

Remove 3 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 34
 Breadth-First Search Example
2
3
FIFO Queue
8 6 9 7
1

4
5
9

6
7

Remove 3 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 35
 Breadth-First Search Example
2
3
FIFO Queue
8 6 9 7
1

4
5
9

6
7

Remove 6 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 36
 Breadth-First Search Example
2
3
FIFO Queue
8 9 7
1

4
5
9

6
7

Remove 6 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 37
 Breadth-First Search Example
2
3
FIFO Queue
8 9 7
1

4
5
9

6
7

Remove 9 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 38
 Breadth-First Search Example
2
3
FIFO Queue
8 7 8
1

4
5
9

6
7

Remove 9 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 39
 Breadth-First Search Example
2
3
FIFO Queue
8 7 8
1

4
5
9

6
7

Remove 7 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 40
 Breadth-First Search Example
2
3
FIFO Queue
8 8
1

4
5
9

6
7

Remove 7 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 41
 Breadth-First Search Example
2
3
FIFO Queue
8 8
1

4
5
9

6
7

Remove 8 from Q; visit adjacent unvisited vertices;

put in Q.
DS UNIT-IV 42
 Breadth-First Search Example
2
3
FIFO Queue
8
1

4
5
9

6
7

Queue is empty. Search terminates.

DS UNIT-IV 43
 Breadth-First Search Property
• All vertices reachable from the start vertex
(including the start vertex) are visited.

DS UNIT-IV 44
 Depth-First Search
Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree
structure, or graph. One starts at the root (selecting some node as the root in the
graph case) and explores as far as possible along each branch before
backtracking.

•Similar to Depth-first Traversal of a Binary Tree

depth-first-search

mark vertex as visited

for each adjacent vertex
if unvisited
do a depth-first search on adjacent vertex

DS UNIT-IV 45
 Depth-First Search
// recursive, preorder, depth-first search
void dfs (Node v) {
if (v == null)
return;

if (v not yet visited)

visit&mark(v); // visit node before adjacent nodes

for (each w adjacent to v)

if (w has not yet been visited)
dfs(w);
} // dfs
DS UNIT-IV 46
 Depth-First Search
// non-recursive, preorder, depth-first search
void dfs (Node v) {
if (v == null)
return;

push(v);
while (stack is not empty) {
pop(v);
if (v has not yet been visited)
mark&visit(v);

for (each w adjacent to v)

if (w has not yet been visited)
push(w);
} // while
DS UNIT-IV 47
} // dfs
 Example

5
2
0

1 3
7

6 4

Policy: Visit adjacent nodes in increasing index order

DS UNIT-IV 48
DFS: Start with Node 5

5
2
0

1 3
7

6 4

5 1 0 3 2 7 6 4

DS UNIT-IV 49
DFS: Start with Node 5

5
2
0

1 3
7
5
6 4
Push 5

DS UNIT-IV 50
DFS: Start with Node 5

5
2
0

1 3
7

6 4
Pop/Visit/Mark 5

DS UNIT-IV 51
DFS: Start with Node 5

5
2
0

1 3
7 1

4 2
6
Push 2, Push 1

DS UNIT-IV 52
DFS: Start with Node 5

5
2
0

1 3
7

4 2
6
Pop/Visit/Mark 1

5 1

DS UNIT-IV 53
DFS: Start with Node 5

5
2
0 0
2
1 3
7 4

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

DS UNIT-IV 54
DFS: Start with Node 5

5
2
0

2
1 3
7 4

4 2
6
Pop/Visit/Mark 0

5 1 0

DS UNIT-IV 55
DFS: Start with Node 5

5 3
2
0 7
2
1 3
7 4

4 2
6
Push 7, Push 3

5 1 0

DS UNIT-IV 56
DFS: Start with Node 5

5
2
0 7
2
1 3
7 4

4 2
6
Pop/Visit/Mark 3

5 1 0 3

DS UNIT-IV 57
DFS: Start with Node 5

5 2
2
0 7
2
1 3
7 4

4 2
6
Push 2

5 1 0 3

DS UNIT-IV 58
Preorder DFS: Start with Node 5

5
2
0 7
2
1 3
7 4

4 2
6
Pop/Mark/Visit 2

5 1 0 3 2

DS UNIT-IV 59
DFS: Start with Node 5

5
2
0

2
1 3
7 4

4 2
6
Pop/Mark/Visit 7

5 1 0 3 2 7

DS UNIT-IV 60
DFS: Start with Node 5

5
2
0 6
2
1 3
7 4

4 2
6
Push 6

5 1 0 3 2 7

DS UNIT-IV 61
DFS: Start with Node 5

5
2
0

2
1 3
7 4

4 2
6
Pop/Mark/Visit 6

5 1 0 3 2 7 6

DS UNIT-IV 62
DFS: Start with Node 5

5
2
0

1 3
7 4

4 2
6
Pop (don’t visit) 2

5 1 0 3 2 7 6

DS UNIT-IV 63
DFS: Start with Node 5

5
2
0

1 3
7

4 2
6
Pop/Mark/Visit 4

5 1 0 3 2 7 6 4

DS UNIT-IV 64
DFS: Start with Node 5

5
2
0

1 3
7

6 4
Pop (don’t visit) 2

5 1 0 3 2 7 6 4

DS UNIT-IV 65
DFS: Start with Node 5

5
2
0

1 3
7

6 4
Done

5 1 0 3 2 7 6 4

DS UNIT-IV 66
DFS: Start with Node 5
Note: edge (0,3) removed

5
2
0

1 3
7

6 4

5 1 0 7 6 2 4 3

DS UNIT-IV 67
 Depth-First Search

B C

D E F G

DS UNIT-IV 68
 Depth-First Search

v
A

B C

D E F G

A
DS UNIT-IV 69
 Depth-First Search

v
A

B C

D E F G

A
DS UNIT-IV 70
 Depth-First Search

v
A

v
B C

D E F G

A B
DS UNIT-IV 71
 Depth-First Search

v
A

v
B C

D E F G

A B
DS UNIT-IV 72
 Depth-First Search

v
A

v
B C

D E F G

A B
DS UNIT-IV 73
 Depth-First Search

v
A

v
B C

v
D E F G

A B D
DS UNIT-IV 74
 Depth-First Search

v
A

v
B C

v
D E F G

A B D
DS UNIT-IV 75
 Depth-First Search

v
A

v
B C

v
D E F G

A B D
DS UNIT-IV 76
 Depth-First Search

v
A

v
B C

v
D E v F G

A B D E
DS UNIT-IV 77
 Depth-First Search

v
A

v
B C

v
D E v F G

A B D E
DS UNIT-IV 78
 Depth-First Search

v
A

v
B C

v
D E v F G

A B D E
DS UNIT-IV 79
 Depth-First Search

v
A

v
B C

v
D E F G

A B D E
DS UNIT-IV 80
 Depth-First Search

v
A

v
B C

v
D E v F G

A B D E
DS UNIT-IV 81
 Depth-First Search

v
A

v
B C

v
D E v F G

A B D E
DS UNIT-IV 82
 Depth-First Search

v
A

v
B C

v
D E v F G

A B D E
DS UNIT-IV 83
 Depth-First Search

v
A

v
B C

v
D E v F G
v

A B D E F
DS UNIT-IV 84
 Depth-First Search

v
A

v
B C

v
D E v F G
v

A B D E F
DS UNIT-IV 85
 Depth-First Search

v
A

v
B C

v
D E v F G
v

A B D E F
DS UNIT-IV 86
 Depth-First Search

v
A

v v
B C

v
D E v F G
v

A B D E F C
DS UNIT-IV 87
 Depth-First Search

v
A

v v
B C

v
D E v F G
v

A B D E F C
DS UNIT-IV 88
 Depth-First Search

v
A

v v
B C

v
D E v F G
v

A B D E F C
DS UNIT-IV 89
 Depth-First Search

v
A

v v
B C

v
D E v F G
v

A B D E F C
DS UNIT-IV 90
 Depth-First Search

v
A

v v
B C

v
v
D E v F G
v

A B D E F C G
DS UNIT-IV 91
 Depth-First Search

v
A

v v
B C

v
v
D E v F G
v

A B D E F C G
DS UNIT-IV 92
 Depth-First Search

v
A

v v
B C

v
v
D E v F G
v

A B D E F C G
DS UNIT-IV 93
 Depth-First Search

v
A

v v
B C

v
v
D E v F G
v

A B D E F C G
DS UNIT-IV 94
 Depth-First Search

v
A

v v
B C

v
v
D E v F G
v

A B D E F C G
DS UNIT-IV 95
 Depth-First Search

v
A

v v
B C

v
v
D E v F G
v

A B D E F C G
DS UNIT-IV 96
 Depth-First Search

v
A

v v
B C

v
v
D E v F G
v

A B D E F C G
DS UNIT-IV 97
 Depth-First Search

v
A

v v
B C

v
v
D E v F G
v

A B D E F C G
DS UNIT-IV 98
 Depth-First Search

B C

D E F G

A B D E F C G
DS UNIT-IV 99