파이썬에서 가장 짧은 사이클 길이 유지 대상을 찾는 프로그램

<시간/>

방향성 그래프의 인접 목록이 있다고 가정합니다. 여기서 인덱스 i의 각 목록은 노드 i의 연결된 노드로 표시됩니다. 목표값도 있습니다. 목표를 포함하는 가장 짧은 주기의 길이를 찾아야 합니다. 솔루션이 없으면 -1을 반환합니다.

따라서 입력이 다음과 같으면

target =3., 사이클이 노드 1 -> 2 -> 3 -> 1이므로 출력은 3이 됩니다. 다른 사이클 0 -> 1 -> 2 -> 3 -> 0이 있지만 이것은 다음과 같습니다. 가장 짧지 않습니다.

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

방문함:=새로운 세트
l :=요소 대상이 있는 목록입니다.
길이:=0
l이 비어 있지 않은 동안 do
- 길이 :=길이 + 1
- nl :=새 목록
- l의 각 u에 대해 다음을 수행합니다.
  - 그래프[u]의 각 v에 대해 다음을 수행합니다.
    - v가 target과 같으면
      - 반환 길이
    - v를 방문하면
      - 다음 반복으로 이동
    - v를 방문한 것으로 표시
    - nl 끝에 v 삽입
- l :=nl
반환 -1

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. -

예시

class Solution:
   def solve(self, graph, target):
      visited = set()
      l = [target]
      length = 0

      while l:
         length += 1
         nl = []
         for u in l:
            for v in graph[u]:
               if v == target:
                  return length
               if v in visited:
                  continue
               visited.add(v)
               nl.append(v)
         l = nl

      return -1

ob = Solution()
graph = [[1, 4],[2],[3],[0, 1],[]]
target = 3
print(ob.solve(graph, target))

입력

[[1, 4],[2],[3],[0, 1],[]]