Chương trình tìm mục tiêu giữ độ dài chu kỳ ngắn nhất trong python

Giả sử chúng ta có danh sách kề của một đồ thị có hướng, trong đó mỗi danh sách tại chỉ mục i được biểu diễn các nút được kết nối từ nút i. Chúng tôi cũng có một giá trị mục tiêu. Chúng ta phải tìm độ dài của một chu kỳ ngắn nhất có chứa mục tiêu. Nếu không có giải pháp, trả về -1.

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

target =3., thì đầu ra sẽ là 3, vì chu kỳ là các nút 1 -> 2 -> 3 -> 1. Lưu ý rằng có một chu kỳ khác 0 -> 1 -> 2 -> 3 -> 0, nhưng đây là không ngắn nhất.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• đã thăm:=một tập hợp mới
• l:=một danh sách với mục tiêu phần tử.
• chiều dài:=0
• trong khi l không trống, hãy thực hiện
  • length:=length + 1
  • nl:=một danh sách mới
  • cho mỗi u trong l, thực hiện
    • đối với mỗi v trong biểu đồ [u], thực hiện
      • nếu v giống với mục tiêu, thì
        • độ dài trả về
      • nếu v được truy cập, thì
        • chuyển sang lần lặp tiếp theo
      • đánh dấu v là đã ghé thăm
      • chèn v vào cuối nl
  • l:=nl
• trả về -1

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

Ví dụ

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

Đầu vào

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

Đầu ra

3