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
12@21
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.
03@01
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:
