Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में ग्राफ में कोई सामान्य पहुंच योग्य नोड है या नहीं जांचने का प्रोग्राम

मान लीजिए हमारे पास एक निर्देशित ग्राफ की एज सूची है, इसमें n नोड हैं और नोड नाम 0 से n-1 हैं। हमारे पास दो पूर्णांक मान a और b भी हैं। हमें जांचना है कि क्या कोई नोड c ऐसा है कि हम c से a जा सकते हैं और c से b भी जा सकते हैं।

इसलिए, यदि इनपुट ग्राफ छवि में दिखाए अनुसार है और a = 2, b = 3, तो आउटपुट होगा True, क्योंकि यहां c = 0, इसलिए 0 से 2 और 0 से 3 तक मार्ग है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

  • DFS() फ़ंक्शन परिभाषित करें। यह graph, node, visited लेगा:
    • यदि node विज़िट नहीं किया गया है, तो:
      • node को विज़िट किया गया चिह्नित करें
      • graph[node] में प्रत्येक x के लिए, करें:
        • DFS(graph, x, visited)
  • मुख्य विधि से, निम्नलिखित करें:
    • graph := edge_list से एडजेंसी सूची उत्पन्न करें
    • visited_a, visited_b := दो खाली सेट
    • DFS(graph, a, visited_a)
    • DFS(graph, b, visited_b)
    • ans := visited_b और visited_a के इंटरसेक्शन से एक नई सूची
    • यदि ans खाली नहीं है, तो:
      • True लौटाएं
    • False लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

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
  1. पायथन में चेक करें कि क्या ग्राफ में विषम लंबाई का चक्र है पायथन में चेक करें कि क्या ग्राफ में विषम लंबाई का चक्र है

    मान लीजिए हमारे पास एक अनडायरेक्टेड ग्राफ है हमें चेक करना है कि क्या हम इसके अंदर विषम लंबाई का चक्र ढूंढ सकते हैं या नहीं।उदाहरण के लिए, यदि इनपुट adj_list = [[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]] है, तो आउटपुट True होगा क्योंकि विषम लंबाई के चक्र हैं जैसे [0, 1, 3, 4, 2], [1, 3, 4],

  1. पायथन में जांचें कि दिया गया ग्राफ द्विभाजित है या नहीं पायथन में जांचें कि दिया गया ग्राफ द्विभाजित है या नहीं

    मान लीजिए हमारे पास एक अविकल्पित ग्राफ है, हमें जांचना है कि ग्राफ द्विभाजित है या नहीं। जैसा कि हम जानते हैं, एक ग्राफ द्विभाजित होता है जब हम ग्राफ के नोड्स को दो सेट A और B में विभाजित कर सकते हैं ताकि ग्राफ में प्रत्येक किनारा {u,v} का एक नोड u A में और दूसरा नोड v B में हो। उदाहरण के लिए, यदि

  1. पायथन प्रोग्राम: जांचें कि दी गई स्ट्रिंग कीवर्ड है या नहीं पायथन प्रोग्राम: जांचें कि दी गई स्ट्रिंग कीवर्ड है या नहीं

    इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे। समस्या कथन हमें एक स्ट्रिंग दी गई है, हमें जांचना है कि यह स्ट्रिंग पायथन का कीवर्ड है या नहीं। कीवर्ड किसी भी भाषा द्वारा आरक्षित विशेष शब्द होते हैं जिनका विशिष्ट उपयोग होता है और उन्हें पहचानकर्ता के रूप में उपयोग नहीं किया जा सकता। यह जां