โปรแกรมคำนวณเมทริกซ์การเข้าถึงจากจุดยอดถึงจุดยอดใน Python

สมมติว่าเรามีกราฟเป็นรายการที่อยู่ติดกัน เราต้องหาเมทริกซ์ 2 มิติ M โดยที่

• M[i, j] =1 เมื่อมีเส้นทางระหว่างจุดยอด i และ j

• M[i, j] =0 ไม่เช่นนั้น

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

แล้วผลลัพธ์ที่ได้จะเป็น

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

• ans:=เมทริกซ์ขนาด 2 มิติ n x n โดยที่ n คือจำนวนจุดยอด เติมด้วย 0s

• สำหรับผมอยู่ในช่วง 0 ถึง n ทำ

  • q:=เป็นคิวแล้วใส่ i เข้าไปก่อน

  • ในขณะที่ q ไม่ว่างให้ทำ

    • node:=องค์ประกอบแรกของ q และลบองค์ประกอบแรกออกจาก q

    • ถ้า ans[i, node] ไม่ใช่ศูนย์ ดังนั้น

      • ไปทำซ้ำต่อไป

    • ตอบ[i, โหนด]:=1

    • เพื่อนบ้าน:=กราฟ[โหนด]

    • ให้เพื่อนบ้านแต่ละคนทำ

      • ใส่ n ต่อท้าย q

• กลับมาอีกครั้ง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def solve(self, graph):
      ans=[[0 for _ in graph] for _ in graph]
      for i in range(len(graph)):
         q=[i]
         while q:
            node=q.pop(0)
            if ans[i][node]: continue
            ans[i][node]=1
            neighbors=graph[node]
            for n in neighbors:
               q.append(n)
      return ans
ob = Solution()
adj_list = [[1,2],[4],[4],[1,2],[3]]
priunt(ob.solve(adj_list))

อินพุต

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

ผลลัพธ์

[[1, 1, 1, 1, 1],
   [0, 1, 1, 1, 1],
   [0, 1, 1, 1, 1],
   [0, 1, 1, 1, 1],
   [0, 1, 1, 1, 1]
]