图是一种非线性数据结构,表示一组顶点(也称为节点)以及它们之间的关系(或边)。顶点表示实体或对象,而边表示顶点之间的关系或连接。图可用于对许多不同类型的关系进行建模,例如社交网络、交通系统或信息流。
图有两种主要类型:有向图(也称为有向图)和无向图。在有向图中,边有一个方向,并且只能在一个方向上遍历,即从起始顶点到结束顶点。在无向图中,边没有方向,可以在两个方向上遍历。
JavaScript 中图的实现
图可以使用邻接矩阵或邻接列表来实现。在这里,我们将使用邻接列表在 JavaScript 中实现图形。
创建图表类
这里我们创建了图形类的蓝图。
class Graph { constructor() { this.adjacencyList = {}; } }
添加顶点
该函数通过在 adjacencyList 对象中创建一个新键并将空数组作为其值来向图中添加一个新顶点(或节点)。新顶点将作为键,空数组将用于存储其邻居。
addVertex(vertex) { if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = []; }
添加边缘
此函数在两个顶点之间添加一条新边。它接受两个参数:vertex1 和 vertex2,并将 vertex2 添加到 vertex1 的邻居数组中,反之亦然。这会在两个顶点之间创建连接。
addEdge(vertex1, vertex2) { this.adjacencyList[vertex1].push(vertex2); this.adjacencyList[vertex2].push(vertex1); }
打印图表
此函数将图表记录到控制台。它迭代 adjacencyList 对象中的每个顶点并记录该顶点及其邻居。
print() { for (const [vertex, edges] of Object.entries(this.adjacencyList)) { console.log(`${vertex} -> ${edges.join(", ")}`); } }
示例
在下面的示例中,我们定义一个图并向该图添加顶点和边。最后打印图表。
class Graph { constructor() { this.adjacencyList = {}; } addVertex(vertex) { if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = []; } addEdge(vertex1, vertex2) { this.adjacencyList[vertex1].push(vertex2); this.adjacencyList[vertex2].push(vertex1); } print() { for (const [vertex, edges] of Object.entries(this.adjacencyList)) { console.log(`${vertex} -> ${edges.join(", ")}`); } } } const graph = new Graph(); graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C"); graph.addVertex("D"); graph.addEdge("A", "B"); graph.addEdge("A", "C"); graph.addEdge("B", "D"); graph.addEdge("C", "D"); console.log("Graph:"); graph.print();
输出
Graph: A -> B, C B -> A, D C -> A, D D -> B, C
删除边
此函数删除两个顶点之间的边。它接受两个参数:vertex1 和 vertex2,并从 vertex1 的邻居数组中过滤掉 vertex2,反之亦然。
removeEdge(vertex1, vertex2) { this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter( (v) => v !== vertex2 ); this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter( (v) => v !== vertex1 ); }
删除顶点
该函数从图中删除一个顶点。它接受一个顶点参数,并首先删除连接到该顶点的所有边。然后,它从 adjacencyList 对象中删除该键。
removeVertex(vertex) { while (this.adjacencyList[vertex].length) { const adjacentVertex = this.adjacencyList[vertex].pop(); this.removeEdge(vertex, adjacentVertex); } delete this.adjacencyList[vertex]; }
示例
在下面的示例中,我们定义一个图并添加顶点和边,然后打印该图。我们从图中删除一条边 AC,最后打印结果图。
class Graph { constructor() { this.adjacencyList = {}; } addVertex(vertex) { if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = []; } addEdge(vertex1, vertex2) { this.adjacencyList[vertex1].push(vertex2); this.adjacencyList[vertex2].push(vertex1); } removeEdge(vertex1, vertex2) { this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter( (v) => v !== vertex2 ); this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter( (v) => v !== vertex1 ); } removeVertex(vertex) { while (this.adjacencyList[vertex].length) { const adjacentVertex = this.adjacencyList[vertex].pop(); this.removeEdge(vertex, adjacentVertex); } delete this.adjacencyList[vertex]; } print() { for (const [vertex, edges] of Object.entries(this.adjacencyList)) { console.log(`${vertex} -> ${edges.join(", ")}`); } } } const graph = new Graph(); graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C"); graph.addVertex("D"); graph.addEdge("A", "B"); graph.addEdge("A", "C"); graph.addEdge("B", "D"); graph.addEdge("C", "D"); console.log("Initial Graph:"); graph.print(); console.log("Graph after removal of edge AC:") graph.removeEdge("A","C"); graph.print();
输出
Initial Graph: A -> B, C B -> A, D C -> A, D D -> B, C Graph after removal of edge AC: A -> B B -> A, D C -> D D -> B, C
图的遍历方法
图遍历是指访问图的所有顶点(或节点)并处理与其关联的信息的过程。图遍历是图算法中的重要操作,用于查找两个节点之间的最短路径、检测环路、查找连通分量等任务。
图遍历主要有两种方法:广度优先搜索(BFS)和深度优先搜索(DFS)
A.广度优先搜索(BFS)
它是使用breadthFirstSearch()函数实现的。该函数实现广度优先搜索算法并采用 start 参数,即起始顶点。它使用队列来跟踪要访问的顶点,使用结果数组来存储访问过的顶点,并使用访问对象来跟踪已经访问过的顶点。该函数首先将起始顶点添加到队列中并将其标记为已访问。然后,当队列不为空时,它从队列中取出第一个顶点,将其添加到结果数组中,并将其标记为已访问。然后它将所有未访问的邻居添加到队列中。这个过程一直持续到所有顶点都被访问过,并且结果数组作为 BFS 的结果返回。
breadthFirstSearch(start) { const queue = [start]; const result = []; const visited = {}; let currentVertex; visited[start] = true; while (queue.length) { currentVertex = queue.shift(); result.push(currentVertex); this.adjacencyList[currentVertex].forEach((neighbor) => { if (!visited[neighbor]) { visited[neighbor] = true; queue.push(neighbor); } }); } return result; } }
B。深度优先搜索
深度优先搜索方法通过使用以顶点作为参数的递归内部函数 dfs 来实现 DFS 算法。该函数使用访问的对象来跟踪访问的顶点,并将每个访问的顶点添加到结果数组中。该函数首先将当前顶点标记为已访问并将其添加到结果数组中。然后,它迭代当前顶点的所有邻居,并为每个未访问的邻居递归调用 dfs 函数。该过程一直持续到所有顶点都被访问过并且结果数组作为 DFS 的结果返回。
depthFirstSearch(start) { const result = []; const visited = {}; const adjacencyList = this.adjacencyList; (function dfs(vertex) { if (!vertex) return null; visited[vertex] = true; result.push(vertex); adjacencyList[vertex].forEach(neighbor => { if (!visited[neighbor]) { return dfs(neighbor); } }); })(start); return result; }
示例
在下面的示例中,我们演示了广度优先搜索(BFS)和深度优先搜索(DFS)。
class Graph { constructor() { this.adjacencyList = {}; } addVertex(vertex) { if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = []; } addEdge(vertex1, vertex2) { this.adjacencyList[vertex1].push(vertex2); this.adjacencyList[vertex2].push(vertex1); } print() { for (const [vertex, edges] of Object.entries(this.adjacencyList)) { console.log(`${vertex} -> ${edges.join(", ")}`); } } breadthFirstSearch(start) { const queue = [start]; const result = []; const visited = {}; let currentVertex; visited[start] = true; while (queue.length) { currentVertex = queue.shift(); result.push(currentVertex); this.adjacencyList[currentVertex].forEach((neighbor) => { if (!visited[neighbor]) { visited[neighbor] = true; queue.push(neighbor); } }); } return result; } depthFirstSearch(start) { const result = []; const visited = {}; const adjacencyList = this.adjacencyList; (function dfs(vertex) { if (!vertex) return null; visited[vertex] = true; result.push(vertex); adjacencyList[vertex].forEach(neighbor => { if (!visited[neighbor]) { return dfs(neighbor); } }); })(start); return result; } } const graph = new Graph(); graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C"); graph.addVertex("D"); graph.addEdge("A", "B"); graph.addEdge("A", "C"); graph.addEdge("B", "D"); graph.addEdge("C", "D"); console.log("Initial Graph:"); graph.print(); console.log("BFS: "+graph.breadthFirstSearch('A')); console.log("DFS: "+graph.depthFirstSearch('A'));
输出
Initial Graph: A -> B, C B -> A, D C -> A, D D -> B, C BFS: A,B,C,D DFS: A,B,D,C
结论
图是一种有用的数据结构,可用于表示对象之间的关系和连接。在 JavaScript 中实现图可以使用多种技术来完成,包括使用邻接列表或邻接矩阵。本答案中演示的 Graph 类使用邻接列表表示形式,其中每个顶点都作为键存储在对象中,其相应的边作为该键的值存储在数组中。
Graph 类实现了向图形添加顶点和边、打印图形以及执行深度优先搜索和广度优先搜索遍历的方法。