Graph

Module 5
 Definition

Types of Graph

Representation Methods

• Adjacency Matrix
Introduction • Adjacency List

Traversal Methods

• Breadth First Search (BFS)

• Depth First Search (DFS)

Application

• Topological Sorting
 Definition of
Graph
A graph (denoted as
G=(V,E)) consists of a
non-empty set of vertices or
nodes V and a set of edges
E.
Let us consider, a Graph is
G=(V,E) where V={a,b,c,d}
and
E={{a,b},{a,c},{b,c},{c,d}}
 Terminologies
• Degree of a Vertex
• The degree of a vertex V of a graph G (denoted by deg (V)) is the
number of edges incident with the vertex V.
• Even and Odd Vertex
• If the degree of a vertex is even, the vertex is called an even vertex and
if the degree of a vertex is odd, the vertex is called an odd vertex.
• Degree of a Graph
• The degree of a graph is the largest vertex degree of that graph. For the
above graph the degree of the graph is 3.
 •
Types of Graph
 Types of Graph
• Multi-Graph: If in a graph multiple edges
between the same set of vertices are allowed, it is
called Multigraph. In other words, it is a graph
having at least one loop or multiple edges.
 Types of Graph
• Directed and Undirected Graph:
A graph G=(V,E) is called a directed graph if the
edge set is made of ordered vertex pair and a
graph is called undirected if the edge set is made
of unordered vertex pair.
 Types of Graph
• Connected and Disconnected Graph:
A graph is connected if any two vertices of the
graph are connected by a path; while a graph is
disconnected if at least two vertices of the graph
are not connected by a path. If a graph G is
disconnected, then every maximal connected
subgraph of G is called a connected component
of the graph G.
 Types of Graph
• Regular Graph: A graph is regular if all the
vertices of the graph have the same degree. In a
regular graph G of degree r, the degree of each
vertex of G is r.
 Types of Graph
•
 Types of Graph
•
 Types of Graph
•
 Types of Graph
•
 Types of Graph
• Planar graph − A graph G is called a planar graph
if it can be drawn in a plane without any edges
crossed. If we draw graph in the plane without
edge crossing, it is called embedding the graph in
the plane.
 Types of Graph
• Non-planar graph − A graph is non-planar if it
cannot be drawn in a plane without graph edges
crossing.
 Representation of Graph
There are mainly two ways to represent a graph −
• Adjacency Matrix
• Adjacency List
 Adjacency Matrix
•
Adjacency Matrix of Undirected Graph
a b c d

a 0 1 1 0

b 1 0 1 0

c 1 1 0 1

d 0 0 1 0
Adjacency Matrix for Directed Graph
a b c d

a 0 1 1 0

b 0 0 1 0

c 0 0 0 1

d 0 0 0 0
 Adjacency List
•
Adjacency List of Undirected Graph
 Graph Traversal Method (BFS)

Breadth-first search (BFS) is a graph search algorithm that begins at the root node and
explores all the neighboring nodes. Then for each of those nearest nodes, the algorithm
explores their unexplored neighbour nodes, and so on, until it finds the goal.

we need to track the neighbours of the node and guarantee that every node in the graph is
processed, and no node is processed more than once. This is accomplished by using a queue
Step 1: SET STATUS = 1 (ready state ) for each node in G
Step 2: Enqueue the starting node A and set its STATUS =
2( waiting state)
Step 3: Repeat step 3 and 4 until queue is empty
BFS
Step 4: Dequeue a node N. process it and set its
STATUS =3 (Processed state)
Methodology
Step 5: Enqueue all the neighbors of N that are in the
ready state ( whose STATUS = 1) and set their
STATUS = 2 (waiting state)
[END OFLOOP]
Step 6: EXIT
 Example
FRONT = 0 QUEUE = A
REAR = 0 ORG = \0
 Example
FRONT = 1 QUEUE = A B C D
REAR = 3 ORG = \0 A A A
 Example
FRONT = 1 QUEUE = A B C D
REAR = 3 ORG = \0 A A A
 Example
FRONT = 3 QUEUE = A B C D E
G
REAR = 5 ORG = \0 A A A B
C
 Example
FRONT = 4 QUEUE = A B C D E
G
REAR = 5 ORG = \0 A A A B
C
 Example
FRONT = 5 QUEUE = A B C D E
G F
REAR = 6 ORG = \0 A A A B
C E
 As I is
destination
STOP

Example
FRONT = QUEUE = A B C D E G F
6 H I
REAR = 9 ORG = \0 A A A B C E
G G
 Example
FRONT = 6 QUEUE = A B C D E G F
H I
REAR = 9 ORG = \0 A A A B C EG
G
A🡪C🡪G🡪I
 BFS Application

Finding the shortest path

Finding all connected
in a weighted directed or
nodes.
undirected graph.
 Graph Traversal Method (DFS)

The depth-first search algorithm progresses by expanding the starting node of G and then
going deeper and deeper until the goal node is found, or until a node that has no children is
encountered.

When a dead-end is reached, the algorithm backtracks, returning to the most recent node
that has not been completely explored. This is accomplished by using a stack.
Step 1: SET STATUS = 1 (ready state ) for each node in G

Step 2: Push the starting node A on to the stack and set its
STATUS = 2 ( waiting state)
Step 3: Repeat step 4 and 5 until stack is empty DFS
Step 4: Pop the top node N. process it and set its STATUS =3
(Processed state) Methodology
Step 5: Push on the stack all the neighbors of N that are in the
ready state ( whose STATUS = 1) and set their STATUS
= 2 (waiting state)
[END OFLOOP]

Step 6: EXIT
Example
 Example
STACK H

PRINT
 Example
STACK E I

PRINT H
 Example
STACK E F

PRINT H I
 Example
STACK E C

PRINT H I F
 Example
STACK E B G

PRINT H I F C
 Example
STACK E B

PRINT H I F C G
 Example
STACK E

PRINT H I F C G B
 Example
STACK

PRINT H I F C G B E
 STOP

Example
FINAL PRINT H, I , F, C, G, B, E
 BFS Application

Finding whether the

Computing path
graph is connected or
between any two nodes.
not
 Topological sort of a directed acyclic graph (DAG) G is
defined as a linear ordering of its nodes in which each
node comes before all nodes to which it has outbound
edges.

A topological sort of a DAG G is an ordering of the

vertices of G such that if G contains an edge (u, v),
then u appears before v in the ordering.
Topological
Sorting Note that topological sort is possible only on directed
acyclic graphs that do not have any cycles.

Topological sorting is widely used in scheduling

applications, jobs, or tasks.
 Topological Sorting
STEP 1: Find the in-degree INDEG(N) of every node in the graph
STEP 2: Enqueue all the nodes with a zero in-degree.

STEP 3: Repeat step 4 and 5 until the QUEUE is empty

STEP 4: Remove the front node N of the QUEUE by setting FRONT = FRONT + 1

STEP 5: Repeat for each neighbor M of node N:

a) Delete the edge from N to M by setting INDEG(M) = INDEG(M) – 1
b)If INDEG(M) = 0, then enqueue M, that is , add M to the rear of the queue.
[END OF INNER LOOP] [END OF LOOP]
STEP 6: EXIT
 Topological Sorting
Adjacency List
C A: B
B: C, D, E
A B E E
C:
D D: E

E: F
G F
G: D

In-deg A=0 B=1 C=1 D=2 E=3 F=1 G=0

FRONT:= 1 REAR:= 2 QUEUE:= A, G
 Topological Sorting
Adjacency List
C A: B
B: C, D, E
A B E E
C:
Remove A E
D D:
FRONT = FRONT + 1 F
E:
Also update In-degree G F
G: D

In-deg A=0 B= C=1 D=2 E=3 F=1 G=0

FRONT:= 2 REAR:= 2 QUEUE:= G, B PRINT:= A
 Topological Sorting
Adjacency List
C A: B
B: C, D, E
A B E E
C:
Remove G E
D D:
FRONT = FRONT + 1 F
E:
Also update In-degree G F
G: D

In-deg A=0 B= C=1 D=1 E=3 F=1 G=0

FRONT:= 3 REAR:= 3 QUEUE:= B PRINT:= A,G
 Topological Sorting
Adjacency List
C A: B
B: C, D, E
A B E E
C:
Remove B E
D D:
FRONT = FRONT + 1 F
E:
Also update In-degree G F
G: D

In-deg A=0 B= C=0 D=0 E=3 F=1 G=0

FRONT:= 4 REAR:= 5 QUEUE:= C, D PRINT:= A,G,B
 Topological Sorting
Adjacency List
C A: B
B: C, D, E
A B E E
C:
Remove C E
D D:
FRONT = FRONT + 1 F
E:
Also update In-degree G F
G: D

In-deg A=0 B= C=0 D=0 E=1 F=1 G=0

FRONT:= 5 REAR:= 5 QUEUE:= D PRINT:= A,G,B,C
 Topological Sorting
Adjacency List
C A: B
B: C, D, E
A B E E
C:
Remove D E
D D:
FRONT = FRONT + 1 F
E:
Also update In-degree G F
G: D

In-deg A=0 B= C=0 D=0 E=0 F=1 G=0

FRONT:= 6 REAR:= 6 QUEUE:= E PRINT:= A,G,B,C,D
 Topological Sorting
Adjacency List
C A: B
B: C, D, E
A B E E
C:
Remove E E
D D:
FRONT = FRONT + 1 F
E:
Also update In-degree G F
G: D

In-deg A=0 B= C=0 D=0 E=0 F=0 G=0

FRONT:= 7 REAR:= 7 QUEUE:= F PRINT:= A,G,B,C,D,E
 Topological Sorting
Adjacency List
C A: B
B: C, D, E
A B E E
C:
D D: E
Remove F E: F
G F
G: D

In-deg A=0 B= C=0 D=0 E=0 F=0 G=0

FRONT:= -1 REAR:= -1 QUEUE:= PRINT:= A,G,B,C,D,E,F
 Topological Sorting

The topological sorting of given graph is:

A, G, B, C, D, E, F

A G B C D E F