Python에서 Edge가 최소 스패닝 트리의 일부인지 확인하는 프로그램

무방향 그래프를 나타내는 'edges'라는 2D 행렬이 있다고 가정합니다. 행렬 '에지'의 모든 항목은 에지를 나타내며 (u, v, w) 형식입니다. 이것은 노드 u와 v가 연결되고 간선이 가중치 w를 갖는다는 것을 의미합니다. 모서리(a,b)를 나타내는 정수와 b도 있습니다. 에지(a, b)가 최소 스패닝 트리의 일부인지 알아내야 합니다.

참고 - 그래프가 연결되어 있어야 하며 그래프에 간선(a, b)이 존재합니다.

따라서 입력이 edge =

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

그러면 출력이 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• findPath() 함수를 정의합니다. 이것은 가장자리를 취할 것입니다, b

  • b와 같으면

    • 참을 반환

  • 가장자리가 비어 있으면

    • 거짓을 반환

  • 가장자리의 각 x에 대해 수행

    • x[2]가 -1과 같으면

      • 반복을 계속하십시오

    • new_a :=-1

    • x[0]이 와 같으면

      • new_a :=x[1]

    • 그렇지 않으면 x[1]이 와 같을 때

      • new_a :=x[0]

    • new_a가 -1과 같지 않으면

      • 가장자리에서 x 삭제

      • findPath(edges, new_a, b)가 0이 아니면

        • 참을 반환

      • 가장자리 끝에 x 삽입

    • 거짓을 반환

이제 주요 기능에서 다음을 수행하십시오 -

• weight :=입력 배열 '에지'에서 에지 x의 에지 가중치, if

  • ((x[0]은 b와 동일하고 x[1]은 b와 동일) or(x[1]은 a와 동일하고 x[0]은 b와 동일))

• edge :=[x[2] 인 경우 입력 배열 edge의 edge x

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