lOMoARcPSD|49994797
DS-Graph - Data Structure notes for Graphs
B.tech (Dr. A.P.J. Abdul Kalam Technical University)
Scan to open on Studocu
Studocu is not sponsored or endorsed by any college or university
Downloaded by Shiv Keshari (
[email protected])
lOMoARcPSD|49994797
"
1
~PH: -f\- ~1aph J2, o._ non -).ineo.y dclo. 1;hudure.
considJn~ of ve,-ticeJ ond_ e~e..8
e, e,
-4- ~10.ph can be defi'-ned QR group of vn±icu
nnd e~es -:fhot are uied ct:o ronneci ~e;e, ve"lttefl
C,~
-.\ Yrofh con be ~een oJ o. etY,·c hee , whexe
· tht veotic~ lNodes) h)ai'nWn o~ c,orn~ex w\®o
T\}.~ G.mon~ fhern Jn,dead of hovinf parent child
velol:iondll~.,,
bb
1- ~roph can
de-Jt'ned at an mdered set be_
y (v, E) where v Y."i the. icl of vitrHC'e.!) ond
E 1~ :the _gel: of t ~e.&- C,1ne_/O''fc) . ~?
Exarnµe A e1 e.,_
·-
V-{tl,8,C,D,E} e..e,
£= {e ,J e1, e~) et, e,,, e",De;ic1
e 1
:: AB , €t ::. s e.'l = 1) e
e2. 8C e-s -:. B0
e:r=- c~ ') e(,-:: "\ .n
Downloaded by Shiv Keshari ([email protected])
lOMoARcPSD|49994797
Jyn:c; OF Cr~i\PI-J:-
1
SQ Und1Tfcieol ~,-aph. ~mph hav1'rid +re e~eJ
Ore n~± oi:bv~ wrth drrec.l-l'or\ IJ ca11ed undr1tCie4
drnrh.
~'.Di'rede~ C,-rapb. hav\i::q the e~e-) 01e
1 ½rnfh
attQc~~ w11J\ dJredi'oY) ,~ caWed. dhe6feaJ 31Cfh.
1) w----
: Undi re~Jed
~~'\Plj_ Te SMINOLOQy :- 1
PATH:- Pillh rnn he deli'nrd ·!hr- )Pi1ence of node,,£ CIA
H 10.I cn t .foll oui eol Jn Gr e/r r do Yrn ch 1or nc. \~n~i ()o !
'r)od0, v ,frnrn ilw Y~1i:Un.P iwdc. U·
_ Cl"OS E P~T I1\-
lOMoARcPSD|49994797
'_Exornple:-
/0
nJo~l<tN(,:-
'9 !='1\Jt , Lue have ctr) co~ ideo on~ ve1f(:)< o~ o
seu)ee ve1te_'.X.
b) S~fMe we. co1121'c/eo woi€_x I,\ aA o... iouoce veoi~)
cJ tfu dtdu~u +o oil e#,e, o'\he1 wohc~
1':~surne -fhat
ii Jnfl'~ frnlD ve1tex '1,, on~ di,dt1nl.Q cJf 1 o.
">() °() 0()
8 9 1-~ D
4
0 1t
10
--x- ,Now colctJ.QQ d (B) on~ d (E) .
jf lq(A ) + C( A 8J < (g) 1
, dlB = ct(-4) + c(A,G)
Downloaded by Shiv Keshari (
[email protected])
lOMoARcPSD|49994797
-- - IIJ
T~ANSITIVE CLOSU~E OF 'DJ~ECTED yl\APH
l EAC\-\J\BlTY tviAT ~r x)
1 ;'f j M reoLmble 1-rol'6J j . ol!ie"fiAl\le
Yij = {
0
tXQh1/~e'.-
A
t\ B C D E
A 1 i 1 1 o
8 0 L O· 0 o
C o i 1 1 o
D O i O .L 0
E O 1 0 1 1
]IJkSTf<A'5 j~ooi±hrfl :- j0ksha's ~oii11m i/4 a,
;,inaJe • ,&0U1ce ~h0oie-R± paih aiaoo\tt'\rn. ~eoe g\~Pe
ioUte] rneon_s fhab 01')~ Olle iew1ce i) aiven, and !Alb
hove Jo 1hid -fhe shoole.tt pal-h rf!'orn -the go woLe to
alt 1he 11odei.
r-Q u.)-~) -= -dQ
=--
( + -c~-u.)\J-----,)
-U) -
Downloaded by Shiv Keshari (
[email protected])
J
lOMoARcPSD|49994797
0 . 11
]O
Now , we w\-LQ c0rnpG YE' oJ) the ve~tic~ exce\:t ¼e,
veote-x A, , Si'ne_e Veo.hx B hOA ihe \ow€,,,lt vq/¼e(4-)
theyefere J ve)bix B (l -&eled-ecl-
CQlrulctttd th( ~t~~LQ o~ A-II A-dj<1.(~nt n<'Jde ofg
dee)= d(BJ t C_(B,C)
=::; 4 + g
= 12 < upe\cu:e_ d(c)
d(E)=d(GJ+e_(6 1E) .
4 + L1 =is > 9donot cho~ed(E)
Downloaded by Shiv Keshari (
[email protected])
__J
- lOMoARcPSD|49994797
cf
·o 1t
2.i
1\1 DW , Ve_)te,x E f~ ~e_t-ected ,
dtHJ ::; d t f;J + C.: ( E,H)
8 + =t--
= <
15 UpciQte ciLH J:: f s
c:KJ
dO=) =- d(t:) + ( (_EJr:)
= t i
· = _g < ao updc±e_ c{(F). = 9
Now Veryt~x f= i~ ;8eJected
9
d(Cp)-= q(r-)+C(f:;~)
=- i3 + 2
< opctoiQ
'== 11 d() Q(~) :: 'LJ
d(H) = d (FJ + C ( t, J-1)
=9 t =- l 5 = s do 'n&f: upd,.(XQ dlltJ
b 1
i\low 1 Ve~t-ex t~ ~€_\ecfed
d (c) = d l ½) T CCC1 , CJ d at v'"die cl (c)
l = 11 ·+ 4 = l5 >12..
Downloaded by Shiv Keshari (
[email protected])
o fl
lOMoARcPSD|49994797
cl(D) ::: d t~) +- c_ l uI D)
::: It t,2\-
=- 2-s < o0 upct_att d(o)::15
dCIJ d((QJ +t(0,t)
,;: I. t t IC
= 2- 1 < up d_ah_
dJ d (T) =- 2 1
Now, Veotex c i;g -&elected
ct(H) QC()+ C_( C)H)
= 12- -t 1 = l 4 < 15 Ltpdltt( dU-D ::J t-
d(J)) =- d Cc) t c_ ( cJ DJ
= l 2- t =t- = I 9 <2 5 up ciafl (n) =l9
Ne)Lu Veole-x H 1'~ ielettecl.
Now, Vertex D iA ielecf-ed.
d(r) = d(~J+ e_(~,r)
::: 19 f 9
= 2 B >2- t do rrntl upaakt G{ (r)
1 Ne LO~ Ve·ot ~ I 1/2 ~elec+ec/.
/ I 1
o/~--'--~ YYif
0 21
r lOMoARcPSD|49994797
exQlmpl~.-
Supj~o~e, ¼ touoce
Ventex
sta~twl~S~rr(ev~¼ex
'I'-
E
/
A B C -1)
A {Q] 00 oO oO oO
C 10 [5] oO c:,Q
E B 14 (1]
B
1)
rn 13
NI
Veotex A i',,~ leJecJ-eC?f 1
d LB_) = d CA-J + C lA) BJ
O -t 1eJ := 10 < oJ tJ pcttd=e d (G)
dee) :: o t5 5 \ &) LJ(Dd(Ul"
~r)W) v~o t~ C,; i'A ;&elee,teol.
f; dlBJ == :S + 3 :::- <1o <?:i upciai2
(E) S: t 2 -= 1- ( lJ p4fLt(
cl C ::, !: -t!J ':: ' t < D~cli!D
dJ
lOMoARcPSD|49994797
= B~SlC OP~~>\TION ON (p~AP~:-
1- Jnse1¼1'ori of No~e.& tt~J JI\ ,the, aoath.
- lhpe-rC Q node jnto qhe, l(Y#·
2, neleHof! o1 NrxieJi/t~ in the ~aqli.
- ~ele±e Q node 11ern th~ ~14h.
3. SeQ'Htu~rt« on ¼rap\i.
t• 1rrowY~1'~ o{ 0raµ.
_Trti-v@~s4L OF- (.Q ~AP H : -
· 8r:;$ ('Breufh F,·rJt &€arch)
!)PS (1)e!'.lth F1'rAt &e~1cihJ
Cl) BFS :-
/
~~LltWQ rut~ c;huG1u1e J
uief 2---
61Qtl with a?:} 11ode
Downloaded by Shiv Keshari (
[email protected])
lOMoARcPSD|49994797
J o , q}Uttr
~e_,wl± : o 2 s 3 '$
-~dJ ~~Qre11t urwl~iied veolex Qdded 1f1W ~lt(J
Step!. ~l!e\t(l, 0
ste~2. ~LLeLU)r,1 , 2.
~~ult
Reiuic o
steps. ~tte~;r2, s , 3 , b #3 , 0tv~Yl'l;~s , ) '6 , t
~e/2uil- G 1 ReAuitl O , 1, 2-
+, QLLeLU ,:t,x ,); 3, <£ , f
~iwl- 0, 1 I 2, 5
5· ~\ij~ ) ); }g > I 4-
~f/2ul)t G I 2 :i ?:i
b, ~ueu_r )' X ;'>( X ~, 4-
0Elllull-- QJ I l 5 3
f· .:
I\
{ t xx G 4~
Downloaded by Shiv Keshari (
[email protected])
lOMoARcPSD|49994797
1) FS ·. ·-
1) Stack &ala S+ruclure
/ ,I
I I
I /
/
I
~ed. I /
/
,/
,,... ---
3) Start with a~ -node. - --~--
I
( J,
I /
I .I
,,
6
4-
3 J
2
1
0 ~esu.lt: 0 , 1 , 2 , 3 ,4- ,b,
-
g
3
2
i
0
lOMoARcPSD|49994797
SPjNNIN~ T~EE
ft spo'nning +He Jg Q ~Ltblel o1 yrCfh ~,
whleh hGt oJ I 4t]e., wohct'.,,:) C('JVeyed coith ll1inif1lun1
?o-2iible 11umber of ed301 .
4 ~fDnnlDer +ree do0 'Mt hG\\Q ~de..! onJ
1i eQn n~ be d.lie0nnectecL.
I\: ~~Tln1ng rhee eoniiih o{ l-n-t) e~_et,
UJhe'ft 11 Jg. ,fu~ 11urn6e~ of ve~tfct½.
9 <t\- eorn~ek undlre.cled 3ra.ph can ~ave Y\n-').
11urn btX'I' of <Sfe:nrilry~ 1'rrep, ~hete rJ & ¾he,
l)Urrrbe"( o{ w~t1'ce,j.:in the J"~ •
'fl = ) 5
5
c')_ 5 c:: t2, 5 S ?Q nn n\},h,,re
i 3
6
4 2 ~P-L
r lOMoARcPSD|49994797
ntNrMut".] f:.P,1t-ltMG, TREE (MST)
' )
-ft minimum sfQnf~1 fyee CQ'f1 be ds1fne~ ax the,
~po.nllJ(J +re~ 117 1.dd'ch +he turn oJ the weith of
fu ectr Ji rn1nirmrrri- The w~ o{ 1he
,S'~~hf(f +oie 1) tUtll cf int (,\)ejF eiv~Y1
+a qt)e, e~ of ~e ~pa'l)nJri~ ~ee.
W,
s
W:: Sf 3-t '1 s: !-0
® s B
0 ®
3
©-- l) I
lOMoARcPSD|49994797
· 7T minimum ~po.f)nll1j_ +~e mn be ,fotin~ CF~
Ci ~eJ,tto) 8,cth ub0lJA'f)t-
Q) ~~1"1 ~<; 4_l~O\tTHM.
1
\~US~ L'. S '\l40~nti f'lj .
'PR 1 M's AL~o ITH f"J ;- t'"o\rn's ~l~o,l-1\.rn i& · Q
s\eed~ nlgoai~f() 'i~Qt iJ wied 41\'\d 1he. tninimL011
Bponnind rfnt 1-Yom o_ ~,~h.
6~ ;
1 spQ\'\flif)a r\te e 12 ,:\he, subd~h 01 on
f\ dM_cted Cll\1l'\E..C,,\-€d o/Af -~1
kltnkiri~- sfa1± 1mrf) _one ve1+~:x G\Y)d e0n\-\roe
,-to o.dcl ~e e,e.& w/ th ~e ~mo_\\~t we.ift
tA.n-HQ ¾he, 300.~ Ji, ieo.checl- 8
1.
~eJ()ove ~00R
3
on~ pa rnileJ e,~f ·
8
[ Wefa.ke an~ nod~
10
%. scLnlQ
Downloaded by Shiv Keshari ([email protected])
"3
lOMoARcPSD|49994797
~:; ti 1-t 2t 2
.=- 11-
V G
E ::-- V- t 6-l ::: S
0 ~USi l\'t-L'.S iL~O~fT~t')..:-
~mov~ Joo~ on~
Po"!Oll~ e~0;-
9
&tart w\ 1Dln\111urn °
¥~ lVeiF 1~ -
Downloaded by Shiv Keshari (
[email protected])
---
lOMoARcPSD|49994797
S) )1)t 6, Jn 4tcerldl~ 5
crde~ of w~ - 4 3
3
DI:-- ~ v
EF - 2 V'
c_~ - 3 V'
Be -3 v
l)F - 4- 1
80 - 5~
Cn-G x
f\B
AC-9 1 kl = ,-+3 t s+2-+'l.
~, :: {t
