JavaScript 邻接矩阵

在图论中，邻接矩阵是一种表示图结构的数据结构。它通过一个二维数组来存储节点之间的连接信息。在这个章节中，我们将详细探讨如何使用 JavaScript 实现和操作邻接矩阵。

创建邻接矩阵

首先，我们需要创建一个邻接矩阵。这可以通过定义一个二维数组来实现。假设我们有一个简单的无向图，其中包含三个节点：A、B 和 C。我们可以使用以下代码来初始化一个邻接矩阵：

const numNodes = 3;
let adjacencyMatrix = Array.from({ length: numNodes }, () => new Array(numNodes).fill(0));

// 打印邻接矩阵
console.log(adjacencyMatrix);

在这个例子中，numNodes 表示图中的节点数量，adjacencyMatrix 是一个由 numNodes x numNodes 的数组组成的二维数组，并且所有元素都被初始化为 0。这表示图中没有任何边。

插入边

接下来，我们需要能够在邻接矩阵中插入边。对于无向图，如果节点 A 和节点 B 之间存在一条边，则在邻接矩阵中，adjacencyMatrix[A][B] 和 adjacencyMatrix[B][A] 应该被设置为 1。以下是插入边的示例代码：

// www.javascriptcn.com code example
function addEdge(matrix, node1, node2) {
    matrix[node1][node2] = 1;
    matrix[node2][node1] = 1; // 对于无向图
}

addEdge(adjacencyMatrix, 0, 1); // 添加节点 0 到节点 1 的边
addEdge(adjacencyMatrix, 1, 2); // 添加节点 1 到节点 2 的边
addEdge(adjacencyMatrix, 2, 0); // 添加节点 2 到节点 0 的边

console.log(adjacencyMatrix);

上述代码会更新邻接矩阵，使其反映图中新的边。

检查边的存在

为了检查两个节点之间是否存在边，我们只需要查看邻接矩阵中的相应位置是否为 1。以下是检查边存在的函数：

function hasEdge(matrix, node1, node2) {
    return matrix[node1][node2] === 1;
}

console.log(hasEdge(adjacencyMatrix, 0, 1)); // 输出 true
console.log(hasEdge(adjacencyMatrix, 1, 2)); // 输出 true
console.log(hasEdge(adjacencyMatrix, 2, 0)); // 输出 true
console.log(hasEdge(adjacencyMatrix, 0, 2)); // 输出 false

这个函数会返回一个布尔值，指示给定的两个节点之间是否存在边。

删除边

删除边的操作与插入边类似。我们只需要将邻接矩阵中对应位置的值设为 0。以下是删除边的示例代码：

function removeEdge(matrix, node1, node2) {
    matrix[node1][node2] = 0;
    matrix[node2][node1] = 0; // 对于无向图
}

removeEdge(adjacencyMatrix, 0, 1);

console.log(adjacencyMatrix);

这段代码会从邻接矩阵中移除指定的边。

图的遍历

邻接矩阵也可以用于图的遍历算法，如深度优先搜索（DFS）和广度优先搜索（BFS）。以下是使用邻接矩阵进行深度优先搜索的一个示例：

// www.javascriptcn.com code example
function dfs(matrix, startNode) {
    const visited = new Array(matrix.length).fill(false);
    const result = [];

    function traverse(node) {
        if (!visited[node]) {
            visited[node] = true;
            result.push(node);
            for (let i = 0; i < matrix[node].length; i++) {
                if (matrix[node][i] === 1 && !visited[i]) {
                    traverse(i);
                }
            }
        }
    }

    traverse(startNode);
    return result;
}

console.log(dfs(adjacencyMatrix, 0)); // 输出 [0, 1, 2]

上述代码演示了如何使用邻接矩阵进行 DFS 遍历。我们同样可以实现 BFS 遍历，方法类似，只是需要使用队列来管理待访问的节点。

总结

本章节详细介绍了如何使用 JavaScript 实现和操作邻接矩阵。邻接矩阵是一种强大的工具，可用于表示和操作图数据。通过使用邻接矩阵，我们可以轻松地插入、删除边以及进行图的遍历。希望这些示例能够帮助您更好地理解和应用邻接矩阵。