エッジがPythonの最小スパニングツリーの一部であるかどうかを確認するプログラム

無向グラフを表す「edges」という名前の2D行列があるとします。マトリックス'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（）を定義します。これはエッジを取ります、a、b

  • aがbと同じ場合、

    • Trueを返す

  • エッジが空の場合、

    • Falseを返す

  • エッジの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を挿入します

    • Falseを返す

ここで、main関数から、次のようにします-

• weight：=入力配列「edges」からのエッジxのエッジの重み（

  の場合）

  • （（x [0]はaと同じで、x [1]はbと同じです）または（x [1]はaと同じで、x [0]はbと同じです））

• エッジ：=[x [2] の場合の入力配列エッジからのエッジx

• 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