GATE CS 2021 Set 2 Q55 — Graph Traversals (BFS, DFS)

The quality-score $Q(v)$ of any vertex $v$ (other than the source $s$) is the maximum of the quality-scores of all paths from $s$ to $v$. This can be computed dynamically using the relation:

With $Q(s) = 1$, we compute the quality-scores of the vertices in topological order:

• Vertex $a$: $Q(a) = Q(s) \times 9 = 9$
• Vertex $b$: $Q(b) = Q(s) \times 9 = 9$
• Vertex $f$: $Q(f) = Q(s) \times 10 = 10$
• Vertex $c$: $Q(c) = \max(Q(a) \times 10, \, Q(b) \times 9) = \max(90, 81) = 90$
• Vertex $d$: $Q(d) = Q(b) \times 9 = 81$
• Vertex $e$: $Q(e) = \max(Q(c) \times 8, \, Q(d) \times 9) = \max(720, 729) = 729$

Summing the quality-scores of all vertices: