โปรแกรมค้นหาเป้าหมายการถือครองความยาวรอบที่สั้นที่สุดใน python

สมมติว่าเรามีรายการที่อยู่ติดกันของกราฟกำกับ ซึ่งแต่ละรายการที่ดัชนี i จะแสดงโหนดที่เชื่อมต่อจากโหนด i เรายังมีค่าเป้าหมาย เราต้องหาความยาวของรอบที่สั้นที่สุดที่มีเป้าหมาย หากไม่มีวิธีแก้ปัญหา ให้คืนค่า -1

ดังนั้นหากอินพุตเป็นแบบ

เป้าหมาย =3 จากนั้นผลลัพธ์จะเป็น 3 เนื่องจากรอบคือโหนด 1 -> 2 -> 3 -> 1 โปรดทราบว่ายังมีอีกรอบ 0 -> 1 -> 2 -> 3 -> 0 แต่นี่คือ ไม่สั้นที่สุด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

เข้าชมแล้ว :=ชุดใหม่
l :=รายการที่มีองค์ประกอบเป้าหมาย
ความยาว :=0
ในขณะที่ l ไม่ว่าง ทำ
- ยาว :=ยาว + 1
- nl :=รายการใหม่
- สำหรับคุณแต่ละคนใน l ทำ
  - สำหรับแต่ละ v ในกราฟ[u] ทำ
    - ถ้า v เหมือนกับเป้าหมาย แล้ว
      - ความยาวคืน
    - ถ้า v ถูกเยี่ยมชม แล้ว
      - ติดตามตอนต่อไป
    - ทำเครื่องหมาย v ว่าเข้าชมแล้ว
    - ใส่ v ต่อท้าย nl
- 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],[]]