在图论中，邻接矩阵是一种表示图结构的数据结构。它通过一个二维数组来存储节点之间的连接信息。在这个章节中，我们将详细探讨如何使用 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。以下是插入边的示例代码：
-- -------------------- ---- -------
-------- --------------- ------ ------ -
-------------------- - --
-------------------- - -- -- -----
-
------------------------ -- --- -- ---- - --- - --
------------------------ -- --- -- ---- - --- - --
------------------------ -- --- -- ---- - --- - --
-----------------------------上述代码会更新邻接矩阵，使其反映图中新的边。
检查边的存在
为了检查两个节点之间是否存在边，我们只需要查看邻接矩阵中的相应位置是否为 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）。以下是使用邻接矩阵进行深度优先搜索的一个示例：
-- -------------------- ---- -------
-------- ----------- ---------- -
----- ------- - --- ---------------------------------
----- ------ - ---
-------- -------------- -
-- ---------------- -
------------- - -----
------------------
--- ---- - - -- - - -------------------- ---- -
-- ---------------- --- - -- ------------ -
------------
-
-
-
-
--------------------
------ -------
-
-------------------------------- ---- -- -- --- -- --上述代码演示了如何使用邻接矩阵进行 DFS 遍历。我们同样可以实现 BFS 遍历，方法类似，只是需要使用队列来管理待访问的节点。
总结
本章节详细介绍了如何使用 JavaScript 实现和操作邻接矩阵。邻接矩阵是一种强大的工具，可用于表示和操作图数据。通过使用邻接矩阵，我们可以轻松地插入、删除边以及进行图的遍历。希望这些示例能够帮助您更好地理解和应用邻接矩阵。