Consider the following acyclic graph that is implement by using adjacency lists.

Question

Consider the following acyclic graph that is implement by using adjacency lists. Assume the adjacency lists are in sorted order, for example when iterating through the edges pointing from vertex a, visit edge(a, b) before edge(a, d). (a) Run breadth-first search (BFS) on the graph to visit all the vertices, starting from vertex a. List the vertices in the order that they are visited. (b) Run depth-first search (DFS) on the graph to visit all the vertices, starts from vertex a. List the vertices in the order that they are visited.

Explanation / Answer

a) Correct,

your order is correct , you start from a and then visit the nodes according to order(like level order traversal )

print A->push(A)-> print B-> push B->print D->push D (1st level)

print e->push(e) ->print C->push(c)-> print f ->push(f) (2nd level)

print f->push(f) -> end ( 3rd level)

so your order is proper.

b) Wrong , correct order is a,b,d,c,e,g,f

Recall DFS algorithm ,

dfs(V) :

vertex V

visit vertex/print vertex V

Each adjacents to vertex V

call dfs(V) for each adjacent

Now, here in your answer you are correct till a,b,d,c, but after that you need to visit next adjacent vertex of d after c , that is e, print e , after that you call DFS for vertex e, so DFS(E) will print the vertex g first and then you backtrack and come back again to vertex d and then you print the vertex g.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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