CS & IT 20 25

ENGINEERING
Algorithms

Graph Algorithms

Lecture No.- 1 By- Aditya sir

Recap of Previous Lecture

Topic Salesman Problem

Travelling
Tsp
Topic imp
Is
 Topics to be Covered

Topic Graph Transals

Topic

3
 GraphTraversals

Graph Transal
is a process of visiting
node the Tree
each and
every of Graph
in some specific order and processing

the information Layonce

4
 Graphtraversals

First Search DFS Transal DFT

Depth

Hraph
d
NConnected
4 Disconnected
b DIAraph DAG
1 Directed Acyclic graph
Topological sorting

5
 Breadth First Search BFS Tranual BFT

Standard Approach
a FIFO BFS default
BFS b
LIFO

DFS Stack

BFS Queue

5
 Applications DFS and BFS
of I

Topological Sorting
Connected Components
Connected Components
Strongly
Point Cut vertex
Articulation
Bi Connected Components

Properties

5
 Breadth First Transal BFT

a FIFO BFS BFT

default

startatA­BFSSpanningt­ag.in
Given D
2
E
B
p
A
A BI
E k
y ft
see 3
G
6
MITTI
5
EC
mFC2 Op
ABCDEGFK
 I

observations AI
Assume evryse1 1 A B D 1 1 2

2 A B E It I I 4
H D

more
AT and many

where every edge

Property In a
unfeigned graph has equal weight

solves the problem SSSP Single Source

BFS
of
Shortest Paths from starting nutex to all other

5 vertex
 diff than
Bonds LIFOB
FSlspece.cl DFS
LIFO order
there we use a Queue that follows
Lastinustot
LIFO BFS
start
B D
BÉE H
Spanning
Tree a
F
of
LIFO
Not
as
same
DFS
3
at
Queue spanker
5 First.IT
hmatofp AcGHEDFB
 ramals
IpthF.rs DIE
Disconnected
Connected
94h
graph GIV.FI

1F

ATeaIf

1
D

LEI
5
 Demffttransal DFT

on an Undirected Graph 1
Connected
a DFS DFT

Exploring Node
i E
mode getting explored
Node which is currently

2 lineHode
explored
Node that is NOT yet fullyin stack
line nodes are
present
alarympopped
Isdxotditn.at explored
5
has already been fully stack
 During Transal the different types of timing values

that a node is associated with v.v Imp

d n
1
Discoverytime
which the node has
It is the time at
time
disconned visited for
the very first
got
2 Finishingtime fin
at which the node
It is the time
becomes a
deadode
Nod
5
 eg DFS in Undirected Connected Groph

start 14
E
3
1B H 211 5
a
G
FI nil 7 12
E 1113
A 11

mggm.gs q

Olp ABDHEFC stack

5
 Stack End DFS
empty of
d F multiple
BIST
seepossible

qf

a_are p
Spanning
B
Tree A ACGH DBEF abovalid
a
Not
as
same
DFS
DFS Starting from
I A
spanetre did
5 Ofp ACGHEDFB
Test O which of the following represents
G
valid DFS traversal on graph

MSG a HGC
ABFED D

b ABE HD FCG
B E
VC DHGCFABE A

D HEDACGF FT
E

HDBEFCGA­Ansi.BE
5
Sota
invalid
A
EHGL DFS
a_BEEIT

B F
X
A 6
15

B ABEND FLG valid 115 2 144 13

F
9110
G
5
c BE vales
PICEA
a F
1
16

1 4100 it's D HE BDACGF valid

3 D

031,4 E H

F
c
5 G
 E HD BEFCGA
BLE
Id
A

at
a
Dolt r

AF D
n

E
F
5

5
 DFT a Undirected Disconnected graph
DFS on

A B given GIVE

Id
I
K

5
Sold 3 Connected
components 3DFS
6 5
1 5 Spanning Trees

Ic fi for each
WH
C 7 14
D
e AIF g
risk 2
Fam
qq.no DFS

Spanning
7 J 18 19 Forest
t.v.IM Typeof8uIoninGATE Application of
Discovery
Time
f with Finishing
9 You are
given
a
graph
A B C D E
5 vertices
ID F each node with
times for
The Disloyahdfinsing
out DFS are as
follows
after carrying
are in G
9.1
Howtyonnectedomponents
G 2 what
aretenticasineach
connected
those
of components

for each option

7
 B C D E
IF
A
1 Disceddgan
1 D 18,20J A 9133 13 D E

2 Connected graph
11151 13113 4,12 15,11 6,9
2 A B C D E

Disconnected graph
0
3
i
1 25 121
3 1 A B 13 D E

graph
04
Disconnected
4
fifths 20,25
2123
A B C D E

7
AIsinglrnoduisaboaconnectd­component.­NO

ind F times its only

time in
to have
mandatory
order
Pnireasing 12.3

7 5101211
 THANK - YOU

Telegram Link for Aditya Jain sir:

https://t.me/AdityaSir_PW