मान लीजिए कि हमारे पास एक निर्देशित ग्राफ की एक बढ़त सूची है, n नोड्स हैं और नोड नाम 0 से n-1 हैं। हमारे पास दो पूर्णांक मान a और b भी हैं। हमें यह जांचना होगा कि क्या कोई नोड c ऐसा है कि हम c से a और c से b तक भी जा सकते हैं।
तो, अगर इनपुट पसंद है
और a =2, b =3, तो आउटपुट ट्रू होगा, क्योंकि यहाँ c =0 है, इसलिए हमारे पास 0 से 2 तक का रूट है और 0 से 3 तक भी।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक फ़ंक्शन को परिभाषित करें DFS() । यह ग्राफ़, नोड, विज़िट किया जाएगा
- यदि नोड का दौरा नहीं किया जाता है, तो
- नोड को विज़िट किया गया के रूप में चिह्नित करें
- ग्राफ में प्रत्येक x के लिए[नोड], करें
- DFS(ग्राफ, x, विज़िट किया गया)
- मुख्य विधि से, निम्न कार्य करें -
- ग्राफ:=edge_list से आसन्नता सूची उत्पन्न करें
- विज़िट_ए, विज़िट_बी:=दो खाली सेट
- डीएफएस (ग्राफ, ए, विज़िट_ए)
- डीएफएस (ग्राफ, बी, विज़िट_बी)
- उत्तर:=विज़िट_बी और विज़िट_ए के चौराहे से एक नई सूची
- यदि उत्तर खाली नहीं है, तो
- सही लौटें
- झूठी वापसी
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
def edge_list_to_graph(edges): s = set() for x, y in edges: s.add(x) s.add(y) s = len(list(s)) graph = [[] for x in range(s)] for x, y in edges: graph[y].append(x) return graph def DFS(graph, node, visited): if node not in visited: visited.add(node) for x in graph[node]: DFS(graph, x, visited) def solve(edges, a, b): graph = edge_list_to_graph(edges) visited_a, visited_b = set(), set() DFS(graph, a, visited_a) DFS(graph, b, visited_b) ans = list(visited_a.intersection(visited_b)) if ans: return True return False ed_list = [(0, 4),(4, 3),(1, 2),(0, 1),(0, 2),(1, 1)] a = 2 b = 3 print(solve(ed_list, a, b))
इनपुट
[(0, 4),(4, 3),(1, 2),(0, 1),(0, 2),(1, 1)], 2, 3
आउटपुट
True