CS & IT 20 25

ENGINEERING
Algorithms

Graph Algorithms

Lecture No.- 2 By- Aditya sir

Recap of Previous Lecture

Topic GraphTraversals
1 BFT
Topic
BFS
1 FIFO default
2
Icons
Terminologies
ected
Typesof Nodes
1 Connected
time
IF Types of 2 Disconnected
 Topics to be Covered

Topic DFS

Topic
1 Directedgraphs

DAG
Topological Sort

3
 DFS in directed graphs i

Terminologies it
a ded Graph
DFS on
Whenever we perform below
edges listed
can lead to the different types of

1
Treedge
edges are those edges that are
present
True
Tree Forest
in the DFS spanning
DFS spanning
Tree Forest
in
The edges that are not present
Forward 2 Backward 3 Cross
4 can be of 3 types 1
 2
Forwardedge
node
It is the edge
that is
going from a

non child descendent

to its
mmmm

3 Backwardadge
Back
This is an edge from
a node to its actor

4 Crossedge to some
one node
This is the edge from nor its
that is neither its ancestor
other node
4 descendent
eg given GIVES
DFS starting
Typesofedges
at A 78
1
8 13 17
13 D

1 17 i

i
forwarded
15 6 e
Apply DFS 7 0 3
Bwd
at A
starting
DFS spanning 4 Crossedge
Tree
4 DC
 D C
11
10
D U 5 6 13 4
1
C V 3 4 Flu
do Ffu
drag

u V

A
Iowlapping
2 c

C dfa flu 3 4 to

Aidsu FCV 1 8 drug II

drug flu
a v
Badge
5
dg A I
o

1 8
A drug Ffa
i

dru FUT 5 6 drug

fay
D
drug Flu

a v forward
edge

4
 starting vertex
Note for same graph for same

Trees are possible

DFS Spanning
different
can also
and hence the types of edges
be different

Obs Tree edges

Graphs
Forward adgs
Backward edges
4 Cros's edges
 1
DFS starting Teedges
at A AB BD DC

1 8
A

a
2 Fm
E
I

Apply DFS 316k

3
Backwyllye
at A I
starting
I
i
5 4 Crossedges

DFS Spanning Hot

4 Tree
 Topic : Graph Techniques PT
day daggrestin flat finishingtimeof u

In any Depth-First Search of a (directed or undirected) graph G = (V, E), for any
two vertices u and v exactly one of the following three conditions holds:

Tonomlapping
I. The intervals [d[u]], f[u]] and d[v], f[v] are entirely disjoint, and neither u nor v
is a descendant of the other in the depth-first forest,
emericrostages
II. The interval [d[u], f[u]] is contained entirely within the interval [d[v], f[v]],
and u is a descendant of v in a depth-first tree, or
u V
Backwardedge Fov
III. The interval [d[v], f[v]] is contained entirely within the interval [d[u], f[u]], and
v is a descendant of u in a depth-first tree.
a
a r forward are
edge
 V0
Backward
v
To
u du Flu
day Ffv
0
4
backward

Forward Ono
u V du flu
dsu Fru
4 forward
Test En ndPrace
8 2 1 p
PFSstntn.at
given GI typesfedgs
A 16
ped's 1stast
75 TT 91Treeedgi
AC CD DH HG
LAB BE EF
input i 318
It 2
Foreffedges
III tilt
fE
3 B
t.ly
4 0616
4211
4
15 En
 IinDiddAydGh DE

Directed graph without it

DAG any cycle in

undirected
Cycle
A B A B

1
I C
D

DAG
4
 Ilgicasost Application of DFS

on a directed Acyclic graph

DAE
Definition
is the linear order vertices nodes that
It
of
that has some
represent some activities

precedencesf

4
 et

BIBB amet Paint

stM

4
992

you
APPO
MBM

C2

4
 91 Source Indgano
Sink Quero
givenaDAG.mn no
of outgoing no of incoming
DAG edges 0
edges o
t
C E
A
node only
DMF 11 we visit a
13
sin when Oall of its precedences
nodes are visited
source C
dg D is precedence
of
Topological Sost
Source no Sink
4
 finding all possible Topological orderings
Source from
every branch
Source sink will
give
Ginence D topological order
A 1 possible
A E
I
F D 1 BADCEF
A
BID BacFE

C 3 BDACEF
4 BDACFE
E F
E F
valid topological orders
1 I 1 DAG
of given
4 SIR
Algorithm
For Topological Cost using DFS

Topological Cost G
Algo
E vertex v DFS v
at any
I Apply DFS starting or

in
the vertices nodes
obtained
all
2 Arrange the Descending decreasing
step DFS transal in

order of their finishing times to Tetavalid

4
Topological Fordering
 walkthrough Dry Run of prev Algo

DFS at A
De cases starting
C E
A
F
A É E DFS
spanning
B D F Forest
11
010

Finishingtime
11
A 8 D
BDACFE
B Eng
c4 F 6
 Ce DEortingaE
15
DAG
E DFS
A
C
Spanning
F 8 9 forest
B
B D
10 11

Fininshingtimes
Descended
D
A 9
B 12 E 2 BDACFE
4 c 6 F 5
 at D
Cares Starting l

A C E

F
D'kc tsE
D eI

B
12
10 31
4
BADCFED
4
#Q.Consider the depth-first-search of an undirected graph with 3vertices P, Q, & R.
Let discovery time d(V) represent the time instant when the vertex ‘V’ is visited
first, and finish time f(V) represent finishing time ; given
d(p) = 5 f(p) = 12
d(Q = 6 f(Q) = 10 11
d(R) = 14 f(R) = 18
Which is true?
A There is only one connected component.
x

X
B There are two connected components, P and R are connected

C There are two connected components, Q and R are connected

x
D There are two connected components, P and Q are connected
Soln
5 12 6 10 14 18

DFS spanning
Tree
T

4
 THANK - YOU

Telegram Link for Aditya Jain sir:

https://t.me/AdityaSir_PW