理解JavaScript中的图数据结构：邻接矩阵详解

class GraphWithAdjMatrix { /** * 初始化图的邻接矩阵表示。 * @param {number} vertices - 图中的顶点数量。 */ constructor(vertices) { this.matrix = []; for (let i = 0; i < vertices; i++) { // 初始化一个二维数组，并将所有值设置为0 this.matrix[i] = Array(vertices).fill(0); } } /** * 添加无向边。 * @param {number} vertex1 - 边的起点。 * @param {number} vertex2 - 边的终点。 */ addEdge(vertex1, vertex2) { // 在两个顶点之间添加一条边 this.matrix[vertex1][vertex2] = 1; this.matrix[vertex2][vertex1] = 1; // 因为是无向图 } /** * 检查两个顶点之间是否存在边。 * @param {number} vertex1 - 第一个顶点。 * @param {number} vertex2 - 第二个顶点。 * @returns {boolean} - 如果两个顶点之间存在边，返回 true，否则返回 false。 */ hasEdge(vertex1, vertex2) { return this.matrix[vertex1][vertex2] === 1; } /** * 打印整个邻接矩阵。 */ printMatrix() { for (let i = 0; i < this.matrix.length; i++) { console.log(this.matrix[i].join(' ')); } } /** * 深度优先搜索 (DFS) * @param {number} startVertex - 开始搜索的顶点索引。 */ dfs(startVertex) { // 初始化一个数组来跟踪每个顶点是否被访问过 const visited = Array(this.matrix.length).fill(false); // 使用一个栈来辅助DFS搜索 const stack = []; // 将开始顶点推入栈 stack.push(startVertex); while (stack.length > 0) { // 当栈不为空时，继续搜索 const currentVertex = stack.pop(); // 取出栈顶的顶点 if (!visited[currentVertex]) { // 如果该顶点未被访问 console.log(currentVertex); // 打印顶点 visited[currentVertex] = true; // 标记为已访问 // 检查当前顶点的所有邻接顶点 for (let i = 0; i < this.matrix.length; i++) { // 如果找到一个邻接点且该邻接点未被访问 if (this.matrix[currentVertex][i] === 1 && !visited[i]) { stack.push(i); // 将该邻接点推入栈以便后续访问 } } } } } /** * 广度优先搜索 (BFS) * @param {number} startVertex - 开始搜索的顶点索引。 */ bfs(startVertex) { // 初始化一个数组来跟踪每个顶点是否被访问过 const visited = Array(this.matrix.length).fill(false); // 使用一个队列来辅助BFS搜索 const queue = []; // 将开始顶点加入队列并标记为已访问 queue.push(startVertex); visited[startVertex] = true; while (queue.length > 0) { // 当队列不为空时，继续搜索 const currentVertex = queue.shift(); // 取出队列前部的顶点 console.log(currentVertex); // 打印顶点 // 检查当前顶点的所有邻接顶点 for (let i = 0; i < this.matrix.length; i++) { // 如果找到一个邻接点且该邻接点未被访问 if (this.matrix[currentVertex][i] === 1 && !visited[i]) { queue.push(i); // 将该邻接点加入队列以便后续访问 visited[i] = true; // 标记为已访问 } } } } }