Consider the graph in Figure 1 a Traverse it using DFS algor

Consider the graph in Figure 1. a. Traverse it using DFS algorithm. b. Traverse it using BFS algorithm. Consider the graph in Figure 2. a. Traverse it using DFS algorithm. b. Traverse it using BFS algorithm. Consider the weighted graph in Figure 3. a. Traverse it using DFS algorithm. b. Traverse it using BFS algorithm.

Solution

1)

a) DFS uses stack..
a a
b c a
d c a-b
e f c a-b-d
g f c a-b-d-e
f c a-b-d-e-f
null a-b-d-e-f-c

--------------------------------------------------------------------------------------------------
1)
b)
BFS uses queue
a a
c b a
c d a-b
d a-b-c
f e a-b-c-d
g f a-b-c-d-e
g a-b-c-d-e-f
null a-b-c-d-e-f-g

---------------------------------------------------------------------------------------------------
2)
a)
DFA uses stack
a a
b a
c a-b
d e f i a-b-c
g h e f i a-b-c-d
h e f i a-b-c-d-g
e f i a-b-c-d-g-h
f i a-b-c-d-g-h-e
j i a-b-c-d-g-h-e-f
i a-b-c-d-g-h-e-f-j
null a-b-c-d-g-h-e-f-j-i

----------------------------------------------------------------------------------------------------------
2) b)
BFS uses queue
a           null
b a
c a-b
d e f i a-b-c
e f i g h a-b-c-d
f i g h a-b-c-d-e
i g h a-b-c-d-e-f
g h a-b-c-d-e-f-i
h a-b-c-d-e-f-i-g
null a-b-c-d-e-f-i-g-h

-------------------------------------------------------------------------------------------------------------
3) a)
DFS uses stack
a       null
e c b a
f c b a-e
d c b a-e-f
c b a-e-f-d
b a-e-f-d-c
null a-e-f-d-c-b

---------------------------------------------------------------------------------------------------------------
3) b)
BFS uses queue

a       null
b c e a
c e d a-b
e d a-b-c
d f a-b-c-e
f a-b-c-e-d
null a-b-c-e-d-f