Python程式：判斷邊是否屬於最小生成樹

假設我們有一個名為“edges”的二維矩陣，它表示一個無向圖。矩陣“edges”中的每個專案都表示一條邊，其形式為(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()。它將接收edges, a, b作為引數。

  • 如果a等於b，則

    • 返回True

  • 如果edges為空，則

    • 返回False

  • 對edges中的每個x進行迭代：

    • 如果x[2]等於-1，則

      • 繼續迭代

    • new_a := -1

    • 如果x[0]等於a，則

      • new_a := x[1]

    • 否則，如果x[1]等於a，則

      • new_a := x[0]

    • 如果new_a不等於-1，則

      • 從edges中刪除x

      • 如果findPath(edges, new_a, b)不為零，則

        • 返回True

      • 將x插入edges的末尾

    • 返回False

現在，從主函式執行以下操作：

• weight := 從輸入陣列“edges”中獲取邊x的權重，如果

  • ((x[0]等於a且x[1]等於b)或(x[1]等於a且x[0]等於b))

• edges := [從輸入陣列edges中獲取邊x，如果x[2] < weight]

• 返回!findPath(edges, 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

Arnab Chakraborty

更新於：2020-12-23

瀏覽量：358

開啟您的職業生涯

完成課程獲得認證

開始學習