Chương trình tìm hiểu xem một cạnh có phải là một phần của cây mở rộng tối thiểu trong Python hay không

Giả sử chúng ta có một ma trận 2D có tên là 'các cạnh', đại diện cho một đồ thị vô hướng. Mọi mục trong ma trận 'các cạnh' đại diện cho một cạnh và có dạng (u, v, w). Điều này có nghĩa là các nút u và v được kết nối và cạnh có trọng lượng w. Chúng ta cũng có các số nguyên a và b, đại diện cho một cạnh (a, b). Chúng ta phải tìm xem cạnh (a, b) có phải là một phần của cây khung tối thiểu hay không.

Lưu ý - đồ thị phải được liên thông và tồn tại cạnh (a, b) trong đồ thị.

Vì vậy, nếu đầu vào giống như các cạnh =

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

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 findPath (). Điều này sẽ có các cạnh, a, b

  • nếu a giống với b thì

    • trả về True

  • nếu các cạnh trống, thì

    • trả về Sai

  • đối với mỗi x trong các cạnh, thực hiện

    • nếu x [2] giống -1 thì

      • tiếp tục lặp lại

    • new_a:=-1

    • nếu x [0] giống với a thì

      • new_a:=x [1]

    • ngược lại khi x [1] giống với a thì

      • new_a:=x [0]

    • nếu new_a không giống -1, thì

      • xóa x khỏi các cạnh

      • nếu findPath (các cạnh, new_a, b) khác 0 thì

        • trả về True

      • chèn x vào cuối các cạnh

    • trả về Sai

Bây giờ từ chức năng chính, hãy làm như sau -

• weight:=trọng số cạnh của cạnh x từ mảng đầu vào ‘các cạnh’, nếu

  • ((x [0] giống a và x [1] giống b) hoặc (x [1] giống a và x [0] giống b))

• edge:=[edge x từ các cạnh mảng đầu vào if x [2]

• trả về không phải findPath (các cạnh, a, b)

Ví dụ

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

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

Đầu vào

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

Đầu ra

True