Chương trình tính ma trận khả thi đỉnh-đỉnh trong Python

Cho đồ thị dưới dạng danh sách kề, tìm ma trận 2D M nơi M[i][j] = 1 nếu có đường đi từ đỉnh i đến j, ngược lại 0.

Ví dụ

Đồ thị đầu vào: (hình ảnh).
Ma trận đầu ra: (bảng 5x5).

Thuật toán

1. Khởi tạo ma trận ans kích thước n x n toàn 0.
2. Với mỗi đỉnh i:
   • Khởi tạo hàng đợi q chứa i.
   • Khi q không rỗng:
     • Lấy đỉnh node từ q.
     • Nếu ans[i][node] != 0, bỏ qua.
     • Đặt ans[i][node] = 1.
     • Thêm tất cả đỉnh kề của node vào q.
3. Trả về ans.

Mã nguồn Python

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))

Đầu vào / Đầu ra

Input: [[1,2],[4],[4],[1,2],[3]]
Output: [[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]]