โปรแกรมเช็คว่ากราฟที่ให้มาเป็นแบบสองส่วนหรือไม่ใน Python

สมมติว่าเรามีกราฟแบบไม่มีทิศทาง 1 กราฟ เราต้องตรวจสอบว่ากราฟนั้นเป็นแบบสองส่วนหรือไม่ ดังที่เราทราบดีว่ากราฟเป็นแบบสองส่วน เมื่อเราสามารถแบ่งโหนดของกราฟออกเป็นสองชุด A และ B เพื่อให้ทุกขอบ {u,v} ในกราฟมีหนึ่งโหนด u ใน A และอีกโหนด v ใน B

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น True [0,4] อยู่ในชุด A และ [1,2,3] อยู่ในชุด B และขอบทั้งหมดมาจาก A ถึง B หรือ B ถึง A ไม่ใช่ A ถึง A หรือ B ถึง B .

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้-

• กำหนดฟังก์ชัน dfs() นี่จะเป็นแหล่งที่มา

• สำหรับแต่ละจุดยอดในกราฟ[แหล่งที่มา] ทำ

  • ถ้า color[vertex] ไม่เหมือนกับ -1 แล้ว

    • ถ้า color[vertex] เหมือนกับ color[source] แล้ว

      • ผลลัพธ์[0] :=เท็จ

      • กลับ

    • ไปอ่านตอนต่อไป

  • สี[จุดยอด] :=1 - สี[แหล่งที่มา]

  • dfs(จุดยอด)

• จากวิธีหลัก ให้ทำดังนี้−

• n :=ขนาดของ arr

• กราฟ :=รายการที่อยู่ติดกันว่างสำหรับจุดยอด 0 ถึง n-1

• สำหรับผมอยู่ในช่วง 0 ถึง n ทำ

  • สำหรับแต่ละ j ใน arr[i] ทำ

    • แทรก i ลงในกราฟ[j]

    • แทรก j ลงในกราฟ[i]

  • color :=รายการขนาด n และเติมด้วย -1

  • result :=รายการที่มีค่า True หนึ่งค่า

• สำหรับผมอยู่ในช่วง 0 ถึง n ทำ

  • ถ้า color[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