Question:
Which graph traversal algorithm can detect a cycle in a directed graph using three-color marking (White, Gray, Black)?
किस ग्राफ ट्रैवर्सल कलनविधि द्वारा तीन रंगों (White, Gray, Black) के अंकन का उपयोग करके निर्देशित ग्राफ में चक्र (cycle) का पता लगाया जा सकता है?
Options:
- Depth First Search (DFS)
- Breadth First Search (BFS)
- Dijkstra’s Algorithm
- Kruskal’s Algorithm
- Depth First Search (DFS)
- Breadth First Search (BFS)
- Dijkstra’s Algorithm
- Kruskal’s Algorithm
Correct Answer: a)
Explanation:
In a directed graph, DFS with three-color tracking identifies back-edges (edges pointing to a Gray node currently in the recursion stack), which definitively indicates a cycle.
निर्देशित ग्राफ में DFS द्वारा बैक-एज (back-edge) की पहचान करके चक्र का सटीक पता लगाया जाता है जब कोई एज वर्तमान में ग्रे (Gray) नोड की ओर इंगित करती है।