Chuyển từ ma trận trọng số (adjacency matrix) sang danh sách kề (adjacency list)

Chuyển ma trận trọng số (adjacency matrix) sang danh sách kề (adjacency list) là một thao tác phổ biến khi làm việc với đồ thị.

🎯 Mục tiêu

Cho ma trận trọng số như sau:

$matrix = [
    // A   B   C   D
    [ 0,  1,  4,  0], // A
    [ 0,  0,  2,  5], // B
    [ 0,  0,  0,  1], // C
    [ 0,  0,  0,  0]  // D
];

Chúng ta sẽ chuyển thành:

$graph = [
    'A' => ['B' => 1, 'C' => 4],
    'B' => ['C' => 2, 'D' => 5],
    'C' => ['D' => 1],
    'D' => []
];

🛠️ Code PHP để chuyển đổi

function matrixToAdjList(array $matrix, array $nodes): array {
    $n = count($matrix);
    $adjList = [];

    for ($i = 0; $i < $n; $i++) {
        $fromNode = $nodes[$i];
        $adjList[$fromNode] = [];

        for ($j = 0; $j < $n; $j++) {
            $weight = $matrix[$i][$j];
            if ($weight > 0) {
                $toNode = $nodes[$j];
                $adjList[$fromNode][$toNode] = $weight;
            }
        }
    }

    return $adjList;
}

🧪 Cách sử dụng:

$matrix = [
    [0, 1, 4, 0],
    [0, 0, 2, 5],
    [0, 0, 0, 1],
    [0, 0, 0, 0]
];

$nodes = ['A', 'B', 'C', 'D'];

$graph = matrixToAdjList($matrix, $nodes);

print_r($graph);

✅ Kết quả:

Array
(
    [A] => Array
        (
            [B] => 1
            [C] => 4
        )

    [B] => Array
        (
            [C] => 2
            [D] => 5
        )

    [C] => Array
        (
            [D] => 1
        )

    [D] => Array
        (
        )
)

📌 Ghi chú:

• Trọng số 0 nghĩa là không có cạnh giữa hai đỉnh.
• Có thể áp dụng cho cả đồ thị vô hướng nếu bạn thêm cạnh ngược lại (ví dụ: nếu A→B thì thêm cả B→A).