पायथन में दिया गया ग्राफ द्विदलीय है या नहीं, यह जांचने के लिए कार्यक्रम

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

तो, अगर इनपुट पसंद है

तब आउटपुट सही होगा, [0,4] सेट ए में हैं और [1,2,3] सेट बी में हैं, और सभी किनारे ए से बी या बी से ए तक हैं, ए से ए या बी से बी नहीं हैं। ।

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

• फ़ंक्शन को परिभाषित करें dfs() । यह स्रोत लेगा

• ग्राफ़ [स्रोत] में प्रत्येक शीर्ष के लिए, करें

  • अगर रंग [वर्टेक्स] -1 के समान नहीं है, तो

    • अगर रंग [वर्टेक्स] रंग [स्रोत] के समान है, तो

      • परिणाम [0] :=गलत

      • वापसी

    • अगले पुनरावृत्ति के लिए जाएं

  • रंग [शीर्ष]:=1 - रंग [स्रोत]

  • dfs(वर्टेक्स)

• मुख्य विधि से, निम्न कार्य करें-

• n :=गिरफ्तारी का आकार

• ग्राफ़ :=0 से n-1 तक के शीर्षों के लिए खाली आसन्न सूची

• मेरे लिए 0 से n की सीमा में, करें

  • गिरफ्तारी में प्रत्येक j के लिए[i], करें

    • ग्राफ़ में i डालें[j]

    • ग्राफ़ में j डालें[i]

  • रंग :=आकार n की सूची और -1 से भरें

  • परिणाम:=एक सही मूल्य वाली सूची

• मेरे लिए 0 से n की सीमा में, करें

  • अगर रंग [i] -1 के समान है, तो

  • dfs(i)

• वापसी परिणाम[0]

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

उदाहरण

from collections import defaultdict
class Solution:
   def solve(self, arr):
      n = len(arr)
      graph = [set() for i in range(n)]
      for i in range(n):
         for j in arr[i]:
            graph[j].add(i)
            graph[i].add(j)
      color = [-1] * n
      result = [True]
      def dfs(source):
      for child in graph[source]:
         if color[child] != -1:
            if color[child] == color[source]:
               result[0] = False
               return
            continue
      color[child] = 1 - color[source]
      dfs(child)
   for i in range(n):
      if color[i] == -1:
      dfs(i)
   return result[0]
ob = Solution()
graph = [[1,2,3],[0],[0,4],[0,4],[2,3]]
print(ob.solve(graph))

इनपुट

graph = [[1,2,3],[0],[0,4],[0,4],[2,3]]

आउटपुट

True