Chương trình tìm độ dài chu trình ngắn nhất chứa đỉnh mục tiêu trong đồ thị có hướng bằng Python

Cho danh sách kề đồ thị có hướng và đỉnh target. Tìm độ dài chu trình ngắn nhất chứa target. Không có thì trả về -1.

Ví dụ: đồ thị 5 đỉnh, target=3 → 3 (chu trình 1→2→3→1).

Giải thuật

• BFS từ target theo hướng ngược (hoặc thuận) để tìm đường quay về target.
• Dùng hàng đợi lớp (l), tập visited, biến length.
• Mỗi lớp mở rộng 1 bước: nếu gặp target → trả về length.
• Hết hàng đợi → -1.

Ví dụ minh họa

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