Chương trình kiểm tra xem chu kỳ độ dài lẻ có trong đồ thị hay không bằng Python

Giả sử chúng ta có một biểu đồ vô hướng, chúng ta phải kiểm tra xem chúng ta có thể tìm thấy một chu trình có độ dài lẻ bên trong nó hay không.

Vì vậy, nếu đầu vào giống như adj_list =[[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]

thì đầu ra sẽ là True vì có các chu kỳ độ dài lẻ như [0, 1, 3, 4, 2], [1, 3, 4], [2, 3, 4].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm dfs (). Điều này sẽ chiếm nút, tôi
• nếu nút nằm trong đường dẫn, thì
  • trả về true khi (i - path [node]) là số lẻ
• nếu nút được truy cập, thì
  • trả về Sai
• đánh dấu nút là đã truy cập
• đường dẫn [node]:=i
• đối với mỗi c trong arr [node], thực hiện
  • nếu dfs (c, i + 1) là true, thì
    • trả về True
• del đường dẫn [nút]
• trả về Sai
• Từ phương thức chính, hãy làm như sau -
• đã thăm:=một tập hợp mới, đường dẫn:=một bản đồ mới
• đối với tôi trong phạm vi từ 0 đến kích thước của arr, thực hiện
• nếu dfs (i, 0) là true thì
• trả về True
• trả về Sai

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

True