Chương trình kiểm tra đồ thị đã cho có phải là một tập hợp cây hay không trong Python

Giả sử chúng ta có một đồ thị, được biểu diễn dưới dạng danh sách các cạnh. Chúng ta phải kiểm tra xem biểu đồ có phải là tập hợp cây (rừng) hay không.

Vì vậy, nếu đầu vào như

thì đầu ra sẽ là True

Để 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, trước

• nếu nút được nhìn thấy, thì

  • trả về Sai

• chèn nút vào thấy

• đối với mỗi nút lân cận n trong e [nút], thực hiện

  • nếu n không giống với trước thì

    • nếu dfs (n, node) là false thì

      • trả về Sai

• trả về True

• Từ phương thức chính, thực hiện như sau -

• e:=một bản đồ trống

• đối với mỗi nút bắt đầu u và nút kết thúc v trong các cạnh, thực hiện

  • chèn v vào cuối e [u]

  • chèn u vào cuối e [v]

• đã thấy:=một tập hợp mới

• đối với mỗi nút trong e, thực hiện

  • nếu nút không được nhìn thấy và dfs (nút, -1) là sai, thì

    • trả về Sai

• trả về True

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

Ví dụ

from collections import defaultdict
class Solution:
   def solve(self, edges):
      e = defaultdict(list)
      for t,f in edges:
         e[t].append(f)
         e[f].append(t)

      seen = set()

      def dfs(node, prev):
         if node in seen:
            return False
         seen.add(node)
      for adj in e[node]:
         if adj != prev:
            if not dfs(adj, node):
               return False
      return True

   for node in e:
      if node not in seen and not dfs(node, -1):
         return False
   return True

ob = Solution()
edges = [[0, 1],[0, 2],[4, 3]]
print(ob.solve(edges))

Đầu vào

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

Đầu ra

True