โปรแกรมหาความยาวรอบสั้นที่สุดที่มี target ในกราฟมีทิศทางใน Python

มี adjacency list กราฟมีทิศทาง และค่า target หาความยาวรอบสั้นที่สุดที่ผ่าน target ถ้าไม่มีคืน -1

เช่น กราฟ [[1,4],[2],[3],[0,1],[]] target=3 ให้ 3 รอบ 1→2→3→1

ขั้นตอนการแก้ปัญหา

• BFS จาก target: visited กันซ้ำ, l ชั้นปัจจุบัน
• แต่ละรอบเพิ่ม length ขยายไปเพื่อนบ้าน
• ถ้าพบ target คืน length
• จบลูปไม่พบคืน -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],[]]

เอาต์พุต

3