26. (3pes) Given the node is printed order graph in Figure 4 What is the output

Question

26. (3pes) Given the node is printed order graph in Figure 4 What is the output of BI'S starting at B if the lahel of cach I when removed from the queue? Note adjacencies are processed in alphabetical A. B.A.C.E.D.E.G B. B.A.C,D.E.G.F BA.CDEFG D. A.B.C.D.E.F.G 27. (3pts) Given the graph in Figure 4, What is the output of DFS, starting at B, if the label of each node is printed when all its adjacencies are processed in alphabetical order? A. FE.CG,D.A.B B, C,G.F.ED C. A,G.F.E.D.C.B D. C.D.FE.G.A.B 5 Figure 4: Graph use for graph questions

Explanation / Answer

1.

Initially Queue has empty

Visited=> _ _ _ _ _ _ _

Now we start at B. So add B to queue.

Visited=> _ B _ _ _ _ _

PRINT B

Add adjacency. We visited A B C D E _ _.

Queue has A C D E.

Dequeue and print.

B A

A's adjacencies are already added to the queue i.e identified by visited list..

Queue has C D E. Now we visited A B C D E F

Dequeue and print B A C

C's adjacencies are F and B.

visited A B C D E F _. Queue has D E F.

Dequeue and print B A C D

D's adjacenciesa re A, E, B, G. Add G to the queue.

Queue has E F G. Visited A B C D E F G.

Dequeue and print B A C D E F.

Queue has F G.

Dequeue and print B A C D E F.

Queue has G.

Dequeue and print B A C D E F G.

Queue is empty stop the process.

E's adjacenciesa are B, D F. Already visited.

Dequeue and print B A C D E

Final answer is B A C D E F G.

2.

Let's maintain adjacency list.

A - B,D

B. - A,C,D,E

C - B, F

D - A,B,E,G

E - B, D, F

F. - C,E,G

G. - D,F

Simiilarly if you use visited and queue with the above adjacency list, we will get B as the correct answer.

In case of any doubts, please comment.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.