โปรแกรมตรวจสอบกราฟที่กำหนดเป็นชุดของต้นไม้หรือไม่ใน Python

สมมติว่าเรามีกราฟซึ่งแสดงเป็นรายการขอบ เราต้องเช็คว่ากราฟเป็นไม้รวม (ป่า) หรือเปล่า

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

แล้วผลลัพธ์จะเป็น True

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

• กำหนดฟังก์ชัน dfs() สิ่งนี้จะใช้โหนดก่อนหน้า

• ถ้าเห็นโหนดในแล้ว

  • คืนค่าเท็จ

• แทรกโหนดที่มองเห็น

• สำหรับแต่ละโหนดที่อยู่ติดกัน n ใน e[node] ทำ

  • ถ้า n ไม่เหมือนกับก่อนหน้า แล้ว

    • ถ้า dfs(n, node) เป็นเท็จ แล้ว

      • คืนค่าเท็จ

• คืนค่า True

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

• e :=แผนที่ว่างเปล่า

• สำหรับแต่ละโหนดเริ่มต้น u และ end node v ในขอบ ทำ

  • ใส่ v ต่อท้าย e[u]

  • ใส่ u ต่อท้าย e[v]

• เห็นแล้ว :=ชุดใหม่

• สำหรับแต่ละโหนดใน e ทำ

  • หากไม่เห็นโหนดและ dfs(node, -1) เป็นเท็จ ดังนั้น

    • คืนค่าเท็จ

• คืนค่า True

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

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

True