CIT0663 DSA

CHAPTER 8: GRAPH DATA

STRUCTURE
Graph Data Structure

- A graph is a pictorial representation of a set of objects where some

pairs of objects are connected by links.
- The interconnected objects are represented by points termed
as
VERTICES, and the links that connect the vertices are called
EDGES.
- Formally, a graph is a pair of sets (V, E), where V is the set of
vertices
and E is the set of edges, connecting the pairs of vertices. Take a
look
In the above graph:-
at the following graph:
v = {a, b,c, d, e}
E=
{ab,ac,ba,bd,ca,cd,db,d
c,de,ed}
Graph Data Structure

In the above graph:-

v={ ? }
E={ ? }
Graph Data Structure
- Mathematical graphs can be represented in data structure.
- We can represent a graph using an array of vertices and a two-
dimensional array of edges.
Before we proceed further, let's familiarize ourselves with some
important terms:-
a) Adjacency
− Two node or vertices are adjacent if they are
connected
to each other through an edge.
- In the following example, B is adjacent to A, C is
b) Path
adjacent to B, and so on.
− Path represents a sequence of edges between the two
vertices.
- In the following example, ABCD represents a path from
A to D.
Graph Data Structure
(cont..)
c) Vertex
− Each node of the graph is represented as a vertex.
- In the following example, the labeled circle represents
vertices. Thus, A to G are vertices.
- We can represent them using an array as shown in the
following image. Here A can be identified by index 0. B can
be identified using index 1 and so on.
d) Edge
− Edge represents a path between two vertices or a line
between two vertices. In the following example, the lines
from
A to B, B to C, and so on represents edges.
- We can use a two-dimensional array to represent an array
- Here AB can be represented as 1 at row 0, column 1, BC as
1
at row 1, column 2 and so on, keeping other combinations
as 0. [Apply in Adjacaceny Matrix]
GRAPH DATA STRUCTURE
Most popular method

ADJACENCY MATRIX ADJACENCY LIST

 Undirected Graph

Graphical graph view

How to merge / change from Pictorial

Graph view into Computer ?
Adjacency Matrix
- Simple in Mathematical
- M * N  ROW * COLUMN [ ]
- GRAPH  MATRIX
How to represent it??

Undirected Graph

Example:
1  3 } No edge between node

1  2 } Edge between node either

12@21
 j
Adjacency Matrix
i

- It is a matrix A [ n ][ n ]
where  n is number of vertices
n  would be for row & column
- A[i][j] = 1 if i & j are
adjacency
= 0 or otherwise
Question..

ANSWER ??
?
Adjacency List
- Going to have Linked List
- How many Linked List would be there
for each Vertex One Linked would be
maintain.
1, 2, 3, 4, 5
Question..
ANSWER ??
?
 Adjacency List

Linked List

How many Linked List

would be maintain? 5

How many of vertices ?

5

Vertice Linked list would have/

s contain the adjacent node
to node
 GRAPH TRAVERSAL

BFS DFS
BREADTH FIRST DEPTH FIRST
SEARCH SEARCH
[ QUEUE ] [ STACK ]
BREADTH FIRST SEARCH
[BFS]
Breadth First Traversal
Breadth First Search (BFS) algorithm traverses a graph in a
Breadthward motion and uses a queue to remember to get the
next vertex to start a search, when a dead end occurs in any
iteration.
As in the example given above, BFS
algorithm traverses from S to A to B to E to
F first then to C and G lastly to D. It
employs the following rules.

Rule 1: Visit the adjacent unvisited vertex.

Mark it as visited. Display it. Insert it in a
queue.

Rule 2: If no adjacent vertex is found,

remove the first vertex from the queue.

Rule 3: Repeat Rule 1 and Rule 2 until the

queue is empty.
Breadth First Search [BFS]
- Known as Level Order Traversal
- When start traversing can take any node as
- Can consider 0, 1, 2 , ………
ROOT NODE - But, depends on question.
- For example:
2 as Root Node  then start
traversing
from node 2
Breadth First Search [BFS]
Choose 0 as a ROOT NODE
0  will traverse 1st and traverse
all vertices as close as
possible
to the Root Vertex.
03@01
3. Then check 0 adjacency on
1. Insert 0 in
which
Queue
node ? 1 & 3
2. Remove 0 in
(then directly insert node 1 &
Queue and put
3 in
0
Queue).
in Result. Then
print 0 in
QUEUE 0
result. 1 3

RESULT: 0
Breadth First Search [BFS]
5. Node 1 already visited then
remove
in graph.

6. Check Adjacent Vertices of 1

(Unvisited Vertices)  0,2,3,5,6

Node 0 & 3  Visited & In

4. Next element 0 is 1, Queue
remove 1 in Queue and 1 put in Node 2, 5 & 6  Unvisited
result.

QUEUE 0 1 3 2 5 6

7. Delete 3 in Queue then Enter 3 in Result

RESULT: 0 1 3
Breadth First Search [BFS]
8. Node 3 already visited then
remove in graph.

9. Check Adjacent Vertices of 3

(Unvisited Vertices)  0,1,2,4

Node 0 & 1  Visited

Node 2  In Queue,
10. Next element in Queue cannot insert
again
is 2, then remove 2 in Then, insert Node 4 into
Queue and insert 2 in Queue
Results

QUEUE 0 1 3 2 5 6 4

RESULT: 0 1 3 2
Breadth First Search [BFS]
11. Node 2 already visited then
remove in graph.

12. Check Adjacent Vertices 2

(Unvisited Vertices)  1,3,4,5

Node 1 & 3  Visited

Node 4 & 5  In Queue,
13. Next element in Queue cannot insert
is 5, then remove 5 in again
Queue and insert 5 in Then, nothing insert into
Result Queue

QUEUE 0 1 3 2 5 6 4

RESULT: 0 1 3 2 5
Breadth First Search [BFS]
14. Node 5 already visited then
remove in graph.

15. Check Adjacent Vertices 5

(Unvisited Vertices)  1, 2

Node 1 & 2  Visited

16. Next element in Queue
is 6, then remove 6 in
Queue and insert 6 in
Result

QUEUE 0 1 3 2 5 6 4

RESULT: 0 1 3 2 5 6
Breadth First Search [BFS]
17. Node 6 already visited then
remove in graph.

18. Check Adjacent Vertices 6

(Unvisited Vertices)  1, 4

Node 1  Visited
Node 4  In Queue

19. Next element in Queue

is 4, then remove 4 in
Queue and insert 4 in
Result

QUEUE 0 1 3 2 5 6 4

RESULT: 0 1 3 2 5 6 4
EXAMPLE:
EXAMPLE:
DEPTH FIRST SEARCH
[DFS]
Depth First Traversal
Depth First Search (DFS) algorithm traverses a graph in a
Depthward motion and uses a STACK (LIFO) to remember to get
the next vertex to start a search, when a dead end occurs in any
iteration.
As in the example given above, DFS
algorithm traverses from S to A to D to G
to E to B first, then to F and lastly to C. It
employs the following rules.
Step of Depth First
Traversal
1 3
Initialize
the stack.

4
Step of Depth First
Traversal
5 6

7
Depth First Search [DFS]
{1,3}
- Taken any traversing any
node
- Choose 0 as a ROOT NODE
1. Insert 0 into stack [PUSH]
2. Result: 0 will printed
3. Then, find Adjacent Vertices
with 0
1, 3  Choose 1

RESULT: 0
Depth First Search [DFS]
{0,2,3,5,6
1. 1 , 3 } Choose 1 1 }
{1,
then PUSH 1 into stack
3}

2. Result : Will print 1 RESULT: 0 1

Depth First Search [DFS]
1. Now find Adjacent Vertices 1 {0,2,3,5,6
of 3 ?? }
{0,1,2,4}
0, 1  Already visited 2
2,4  Take anyone? 2
2. Push 3 onto stack

{0,1,2,4}

3. Result : Will print 3 RESULT: 0 1 3

Depth First Search [DFS]
1. Now find Adjacent Vertices 1 {0,2,3,5,6
of 2 ?? }
{1,3,4,5}
1, 3  Already visited 2
4,5  Take anyone? 4
3
2. Push 2 onto stack
{0,1,2,4}
4 {1,3,4,
5}
2

3. Result : Will print 2 RESULT: 0 1 3 2

Depth First Search [DFS]
1. Now find Adjacent Vertices 1 {0,2,3,5,6
of 4 ?? }
{2,3,6}
2,3  Already visited 2
4  Push onto stack
3

{0,1,2,4} 4 {1,3,4,
5}
5

{2,3,6}

3. Result : Will print 4 RESULT: 0 1 3 2 4

Depth First Search [DFS]
1. Now find Adjacent Vertices 1 {0,2,3,5,6
of 6 ?? }
{1,4}
1,4  Already visited 2
6  Push onto stack
3
No unvisited adjacent for 6
{0,1,2,4} 4 {1,3,4,
5}
5

{2,3,6} {1,4}

RESULT: 0 1 3 2 4
3. Result : Will print 6
6
Depth First Search [DFS]
- No unvisited adjacent for 6 1 {0,2,3,5,6
- Then, do the Backtracking
}
process
2
Backtracking Process
3
Do the POP to enter the unvisited
Node  5 POP [6]
{0,1,2,4} 4 {1,3,4,
5}
5

{2,3,6} {1,4}

RESULT: 0 1 3 2 4
6
Depth First Search [DFS]
Pop [6]  check element in stack before 6 is
4
POP [ 4 ]
Then check it is have the unvisited
Adjacency Vertices  NO

RESULT: 0 1 3 2 4
6
Depth First Search [DFS]
Pop [4]  check element in stack before 4 is
2
POP [ 2 ]
Then check the unvisited Adjacency Vertices
of 2 is {1,3,4,5}  { 5 }  Unvisited
PUSH [ 5 ]

RESULT: 0 1 3 2 4 6
5
Depth First Search [DFS]
Then check the unvisited Adjacency Vertices of
5
is {1,2 }  Already visited

POP [ 5 ]

RESULT: 0 1 3 2 4 6
5
Depth First Search [DFS]
Then check the unvisited Adjacency Vertices of
5
is {1,2 }  Already visited

POP [ 5 ]

RESULT: 0 1 3 2 4 6
5
Depth First Search [DFS]
Then check the unvisited Adjacency Vertices of
2
is {1,3,4,5 }  Already visited

POP [ 2]

RESULT: 0 1 3 2 4 6
5
Depth First Search [DFS]
Then check the unvisited Adjacency Vertices of
3
is {0,1,2,4 }  Already visited

POP [ 3]

RESULT: 0 1 3 2 4 6
5
Depth First Search [DFS]
Then check the unvisited Adjacency Vertices of
3
is {0,1,2,4 }  Already visited

POP [ 3]

RESULT: 0 1 3 2 4 6
5
Depth First Search [DFS]
Then check the unvisited Adjacency Vertices of
1
is {0,2,3,5,6 }  Already visited

POP [ 1]

RESULT: 0 1 3 2 4 6
5
Depth First Search [DFS]
Then check the unvisited Adjacency Vertices of
0
is { 1,3 }  Already visited

POP [ 0]

RESULT: 0 1 3 2 4 6
5
Depth First Search [DFS]

RESULT: 0 1 3 2 4 6 5
EXAMPLE:
EXAMPLE: