PrepSnap logoPrepSnap
Pass

Question

1.
2.
3.
4.
Answer (Detailed Solution Below)

Option 4 : Run DFS tracking nodes currently on the recursion stack (three-colour marking) / पुनरावर्तन स्टैक पर वर्तमान नोडों को ट्रैक करते हुए DFS (त्रि-रंग अंकन)

Advertisement

Detailed Solution

सही उत्तर Run DFS tracking nodes currently on the recursion stack (three-colour marking) / पुनरावर्तन स्टैक पर वर्तमान नोडों को ट्रैक करते हुए DFS (त्रि-रंग अंकन) है।

Key Points
Helpful?
PrepSnapprepsnap.in • Part -A

Question:

A teacher asks students to detect whether a course-prerequisite digraph contains a circular dependency. Which method is correct? / एक शिक्षक विद्यार्थियों से पूछता है कि पाठ्यक्रम-पूर्वापेक्षा दिष्ट ग्राफ़ में चक्रीय निर्भरता है या नहीं, इसका पता लगाएँ। कौन-सी विधि सही है?

1.
Run BFS from each node using a single visited set / प्रत्येक नोड से एकल विज़िटेड समुच्चय से BFS चलाना
2.
Count whether the number of edges exceeds the number of vertices / गिनना कि किनारों की संख्या शीर्षों से अधिक है या नहीं
3.
Sort vertices alphabetically and look for back edges / शीर्षों को वर्णमाला क्रम में रखकर पश्च किनारे खोजना
4.
Run DFS tracking nodes currently on the recursion stack (three-colour marking) / पुनरावर्तन स्टैक पर वर्तमान नोडों को ट्रैक करते हुए DFS (त्रि-रंग अंकन)

Correct Answer: Run DFS tracking nodes currently on the recursion stack (three-colour marking) / पुनरावर्तन स्टैक पर वर्तमान नोडों को ट्रैक करते हुए DFS (त्रि-रंग अंकन)

In a directed graph a cycle exists exactly when DFS meets a node still on the recursion stack (grey); a plain visited set cannot distinguish cross edges from back edges, and edge counts prove nothing. / दिष्ट ग्राफ़ में चक्र तभी है जब DFS पुनरावर्तन स्टैक पर स्थित नोड (धूसर) से मिले; सादा विज़िटेड समुच्चय क्रॉस व पश्च किनारों में भेद नहीं करता, और किनारा-गणना कुछ सिद्ध नहीं करती।

Downloaded from PrepSnap (prepsnap.in)