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

สมมติว่ามีกราฟในรูปแบบรายการความติดกัน เราต้องหาเมทริกซ์ 2D M โดยที่ M[i, j] = 1 เมื่อมีเส้นทางระหว่างจุดยอด i และ j มิฉะนั้น M[i, j] = 0

เช่น ถ้าอินพุตเป็นกราฟดังภาพ ผลลัพธ์จะเป็นเมทริกซ์ที่แสดงความเข้าถึงได้

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

• ans := เมทริกซ์ 2D ขนาด n x n โดย n คือจำนวนจุดยอด เติม 0
• สำหรับ i ในช่วง 0 ถึง n ทำ
  • q := คิว ใส่ i เข้าไปก่อน
  • while q ไม่ว่าง ทำ
    • node := องค์ประกอบแรกของ q ลบออกจาก q
    • ถ้า ans[i, node] ไม่ใช่ 0 ข้ามไปรอบถัดไป
    • ans[i, node] := 1
    • neighbors := graph[node]
    • สำหรับแต่ละ n ใน neighbors ใส่ n เข้า q
• คืนค่า ans

ตัวอย่างโค้ด

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]]
print(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]]