โปรแกรมค้นหาว่า Edge เป็นส่วนหนึ่งของ Spanning Tree ขั้นต่ำใน Python หรือไม่

สมมติว่าเรามีเมทริกซ์ 2 มิติชื่อ 'ขอบ' ซึ่งแสดงถึงกราฟที่ไม่มีทิศทาง ทุกรายการใน "ขอบ" ของเมทริกซ์แสดงถึงขอบและอยู่ในรูปแบบ (u, v, w) ซึ่งหมายความว่าโหนด u และ v เชื่อมต่อกัน และขอบมีน้ำหนัก w เรายังมีจำนวนเต็ม a และ b ซึ่งแทนขอบ (a,b) เราต้องค้นหาว่าขอบ (a, b) เป็นส่วนหนึ่งของต้นไม้ที่ทอดข้ามขั้นต่ำหรือไม่

หมายเหตุ − กราฟจะต้องเชื่อมต่อและมีขอบ (a, b) อยู่ในกราฟ

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

[[0, 2, 100],
[1, 2, 200],
[1, 3, 100],
[2, 3, 300]],
a = 0
b = 2,

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

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

• กำหนดฟังก์ชัน findPath() นี่จะเป็นขอบ a, b

  • ถ้า a เหมือนกับ b แล้ว

    • คืนค่า True

  • หากขอบว่างเปล่า

    • คืนค่าเท็จ

  • สำหรับแต่ละ x ในขอบ ทำ

    • ถ้า x[2] เหมือนกับ -1 แล้ว

      • ทำซ้ำต่อไป

    • new_a :=-1

    • ถ้า x[0] เหมือนกับ a แล้ว

      • new_a :=x[1]

    • มิฉะนั้นเมื่อ x[1] เหมือนกับ a แล้ว

      • new_a :=x[0]

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

      • ลบ x จากขอบ

      • ถ้า findPath(edges, new_a, b) ไม่ใช่ศูนย์ ดังนั้น

        • คืนค่า True

      • ใส่ x ที่ปลายขอบ

    • คืนค่าเท็จ

จากหน้าที่หลัก ให้ทำดังต่อไปนี้ -

• น้ำหนัก :=น้ำหนักขอบของขอบ x จากอาร์เรย์อินพุต 'ขอบ' ถ้า

  • ((x[0] เหมือนกับ a และ x[1] เหมือนกับ b) หรือ(x[1] เหมือนกับ a และ x[0] เหมือนกับ b))

• ขอบ :=[ขอบ x จากขอบอาร์เรย์อินพุต ถ้า x[2] <น้ำหนัก]

• กลับไม่ findPath(ขอบ, a, b)

ตัวอย่าง

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

class Solution:
   def findPath(self, edges, a, b):
      if a == b:
         return True
      if not edges:
         return False
      for x in edges:
         if x[2] == -1:
            continue
         new_a = -1
         if x[0] == a:
            new_a = x[1]
         elif x[1] == a:
            new_a = x[0]
         if new_a != -1:
            edges.remove(x)
            if self.findPath(edges, new_a, b):
               return True
            edges.append(x)
      return False
   def solve(self, edges, a, b):
      weight = next(x for x in edges if (x[0] == a and x[1] == b) or (x[1] == a and x[0] == b))[ 2 ]
      edges = [x for x in edges if x[2] < weight]
      return not self.findPath(edges, a, b)

ob = Solution()
print(ob.solve([
   [0, 2, 100],
   [1, 2, 200],
   [1, 3, 100],
   [2, 3, 300]
], 0, 2))

อินพุต

[
[0, 2, 100],
[1, 2, 200],
[1, 3, 100],
[2, 3, 300]
], 0, 2

ผลลัพธ์

True