Consider the following acyclic graph that is implemented by using adjacency list

Question

Consider the following acyclic graph that is implemented by using adjacency lists. Assume the adjacency lists are in sorted order, for example, when iterating through the edges pointing from vertex 3, visit edge(2 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, starting from vertex a. List the vertices in the order that they are visited.

Explanation / Answer

Q-1

A B D E C F G

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

1. Print A

2. Print Unvisited Children of A : Print B -> Print D

3. Print Unvisited Children of B : Print E

4. Print Unvisited Children of D : Print C -> Print F -> Print G

5. No Nodes are Unvisited -> break

b) 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

Call trace :

Print A -> call the next unvisited children in sequence for A ( it is B) -> Print B -> call the next unvisited children in sequence for B(it is D) ->Print D-> call the next unvisited children in sequence for D ( it is C) -> Print C -> Call the next unvisited children in sequence for C -> C has no children that is un visited -> call the next unvisited children in sequence for D -> Print E -> Call the next unvisited children of E -> Print G -> call the next unvisited children of G -> None so back track -> call the next unvisited children of E- > NONE so backtrack -> we again came back to D -> call the next unvisited children of D -> Print F -> All nodes are visited so END

Cheers:)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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