Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมตรวจสอบความยาวคี่เป็นกราฟหรือไม่อยู่ใน Python


สมมติว่าเรามีกราฟที่ไม่มีทิศทาง ซึ่งเราต้องตรวจสอบว่าเราสามารถหาวงจรความยาวคี่ในกราฟนั้นได้หรือไม่

ดังนั้น หากอินพุตเป็นเหมือน adj_list =[[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]

โปรแกรมตรวจสอบความยาวคี่เป็นกราฟหรือไม่อยู่ใน Python

แล้วผลลัพธ์จะเป็น True เนื่องจากมีรอบความยาวคี่ เช่น [0, 1, 3, 4, 2], [1, 3, 4], [2, 3, 4].

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

  • กำหนดฟังก์ชัน dfs() นี่จะใช้โหนดฉัน
  • ถ้าโหนดอยู่ในเส้นทาง
    • คืนค่าจริงเมื่อ (i - path[node]) เป็นเลขคี่
  • ถ้าโหนดถูกเยี่ยมชมแล้ว
    • คืนค่าเท็จ
  • ทำเครื่องหมายโหนดว่าเข้าชมแล้ว
  • เส้นทาง[โหนด] :=ผม
  • สำหรับแต่ละ c ใน arr[node] ทำ
    • ถ้า dfs(c, i + 1) เป็นจริง ดังนั้น
      • คืนค่า True
  • เส้นทางเดล[โหนด]
  • คืนค่าเท็จ
  • จากวิธีหลัก ให้ทำดังนี้ -
  • เข้าชมแล้ว :=ชุดใหม่ เส้นทาง :=แผนที่ใหม่
  • สำหรับ i ในช่วง 0 ถึงขนาดของ arr ทำ
  • ถ้า dfs(i, 0) เป็นจริง ดังนั้น
  • คืนค่า True
  • คืนค่าเท็จ

ตัวอย่าง (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

class Solution:
   def solve(self, arr):
      def dfs(node, i):
         if node in path:
            return (i - path[node]) % 2 == 1
         if node in visited:
            return False
         visited.add(node)
         path[node] = i
         for c in arr[node]:
            if dfs(c, i + 1):
               return True
         del path[node]
         return False
      visited, path = set(), {}
      for i in range(len(arr)):
         if dfs(i, 0):
            return True
      return False
ob = Solution()
adj_list = [[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]
print(ob.solve(adj_list))

อินพุต

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

ผลลัพธ์

True