ग्राफ़ में चक्रों का पता लगाना
ग्राफ़ में चक्रों का पता लगाना डेटा की संरचना और गुणों को समझने के लिए बहुत महत्वपूर्ण है। इसका उपयोग कई क्षेत्रों में होता है, जैसे निर्भरता प्रबंधन (dependency management), डेडलॉक का पता लगाना (deadlock detection), और नेटवर्क रूटिंग। चक्रों की पहचान करके, हम परस्पर निर्भरता (circular dependencies), कार्यक्षमता में कमी, या यहाँ तक कि प्रणालीगत असफलताओं जैसी समस्याओं से बच सकते हैं।
ग्राफ़ में चक्र ढूँढने के लिए आप DFS (Depth First Search) के एक संशोधित संस्करण का उपयोग कर सकते हैं।
जब हम DFS की मदद से किसी ग्राफ़ मेंTraversal (परिवहन) करते हैं, तो सामान्यतः हम किसी शीर्षक (vertex) को "देखा गया" या "नहीं देखा गया" के रूप में चिह्नित करते हैं। लेकिन चक्रों का पता लगाने के लिए यह पर्याप्त नहीं है। इसके लिए हमें प्रत्येक शीर्षक के लिए 3 अवस्थाएँ रखनी पड़ती हैं:
- शीर्षक अभी तक देखा नहीं गया
- शीर्षक और उसकी DFS उपवृक्ष (subtree) पर कार्य चल रहा है
- शीर्षक पूर्ण रूप से देखा जा चुका है (इसके सभी चाइल्ड नोड्स भी देखे जा चुके हैं)
इस प्रकार, यदिTraversal के दौरान हम किसी ऐसे शीर्षक पर पहुँचते हैं जिसकी अवस्था "प्रक्रियाधीन" (दूसरा बिंदु) है, तो इसका अर्थ है कि हमने एक चक्र खोज लिया है।
➰
यदिTraversal के दौरान हम किसी ऐसे शीर्षक तक पहुँचते हैं जिसे "प्रक्रियाधीन" (2) चिह्नित किया गया है, तो यह दर्शाता है कि ग्राफ़ में चक्र मौजूद है।
एल्गोरिथ्म निम्नलिखित चरणों का पालन करता है:
- सभी शीर्षकों को "नहीं देखा गया" के रूप में चिह्नित करें
- किसी शीर्षक से DFS शुरू करें
- वर्तमान शीर्षक को "प्रक्रियाधीन" के रूप में चिह्नित करें
- जब वर्तमान शीर्षक के सभी चाइल्ड नोड्स की जाँच पूरी हो जाए, शीर्षक को "पूर्ण रूप से देखा गया" के रूप में चिह्नित करें
यह एल्गोरिथ्म निर्देशित (directed) और अदिश निर्देशित (undirected) दोनों प्रकार के ग्राफ़ पर लागू किया जा सकता है:
color = [1] * n # शीर्षकों का रंग (1: नहीं देखा गया, 2: प्रक्रियाधीन, 3: पूर्ण रूप से देखा गया)
def dfs(v, p): # depth-first search (v: शीर्षक, p: पेरेंट)
color[v] = 2 # शीर्षक को प्रक्रियाधीन के रूप में चिह्नित करें
cycle = False # चक्र होने की स्थिति जाँचने वाला फ्लैग
for to in g[v]: # v से जुड़े प्रत्येक शीर्षक के लिए
if color[to] == 1: # यदि शीर्षक नहीं देखा गया
cycle |= dfs(to, v) # dfs चलाएँ और देखें कि चक्र मिलता है या नहीं
elif color[to] == 2 and to != p: # यदि शीर्षक प्रक्रियाधीन है और वह पेरेंट नहीं है
cycle = True # चक्र मिला, फ्लैग को True करें
color[v] = 3 # शीर्षक को पूर्ण रूप से देखा गया के रूप में चिह्नित करें
return cycle # फ्लैग लौटाएँ
for start in range(n): # प्रत्येक शीर्षक के लिए
if color[start] == 1: # यदि शीर्षक नहीं देखा गया
if dfs(start, -1): # dfs चलाएँ और देखें कि चक्र मिलता है या नहीं
print('Cycle') # 'Cycle' प्रिंट करें
break # लूप रोक दें
else: # यदि लूप break से कभी नहीं रुका
print('No cycle') # 'No cycle' प्रिंट करेंध्यान दें कि निर्देशित ग्राफ़ के लिए पेरेंट शीर्षक को ध्यान में रखना ज़रूरी नहीं है। क्या आप बता सकते हैं क्यों 🤔?
चलिए इस एल्गोरिथ्म को कुछ इनपुट्स पर चलाकर देखते हैं:
n = 4, e = 4
इनपुट
a, b जोड़े इस प्रकार हैं: [(0, 1), (0, 2), (1, 2), (3, 2)]शुरुआती शीर्षक 3 है
v=3, p=-1→color = [1, 1, 1, 2]⇒ 3 के सभी पड़ोसी देखें ⇒[2]
v=2, p=3→color = [1, 1, 2, 2]⇒ 2 के सभी पड़ोसी देखें ⇒[0, 1]
v=0, p=2→color = [2, 1, 2, 2]⇒ 0 के सभी पड़ोसी देखें ⇒[1, 2]
v=1, p=0→color = [2, 2, 2, 2]⇒ 1 के सभी पड़ोसी देखें ⇒[0, 2]⇒ 0 की अवस्था 1 है ⇒cycle = True⇒return True
चुनौती: जाँचें कि ग्राफ़ में चक्र मौजूद है या नहीं
आपको निर्देशित ग्राफ़ दिया गया है जिसमें
v शीर्षक और e किनारें हैं। आपको जाँचना है कि इस ग्राफ़ में चक्र है या नहीं।इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
v (1 ≤ v ≤ 100 000) और e (1 ≤ e ≤ 100 000) होते हैं।अगली
e पंक्तियों में प्रत्येक पंक्ति में दो पूर्णांक v1, v2 (1 ≤ v1, v2 ≤ v) दिए जाते हैं, जिनका अर्थ है कि शीर्षक v1 से शीर्षक v2 के लिए एक पथ मौजूद है।आउटपुट
यदि ग्राफ़ में चक्र है तो प्रोग्राम को "Yes" प्रिंट करना चाहिए, अन्यथा "No"।
उदाहरण
Input | Output |
4 3
1 2
2 3
3 1
| Yes |
4 3
1 2
1 3
2 4 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB