图是一种非线性数据结构，表示一组顶点（也称为节点）以及它们之间的关系（或边）。顶点表示实体或对象，而边表示顶点之间的关系或连接。图可用于对许多不同类型的关系进行建模，例如社交网络、交通系统或信息流。
图有两种主要类型：有向图（也称为有向图）和无向图。在有向图中，边有一个方向，并且只能在一个方向上遍历，即从起始顶点到结束顶点。在无向图中，边没有方向，可以在两个方向上遍历。
JavaScript 中图的实现
图可以使用邻接矩阵或邻接列表来实现。在这里，我们将使用邻接列表在 JavaScript 中实现图形。
创建图表类
这里我们创建了图形类的蓝图。
立即学习“Java免费学习笔记（深入）”；
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, CB -> A, DC -> A, DD -> B, C
删除边
此函数删除两个顶点之间的边。它接受两个参数：vertex1 和 vertex2，并从 vertex1 的邻居数组中过滤掉 vertex2，反之亦然。
ViiTor实时翻译
AI实时多语言翻译专家！强大的语音识别、AR翻译功能。
116 查看详情
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, CB -> A, DC -> A, DD -> B, CGraph after removal of edge AC:A -> BB -> A, DC -> DD -> 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, CB -> A, DC -> A, DD -> B, CBFS: A,B,C,DDFS: A,B,D,C
结论
图是一种有用的数据结构，可用于表示对象之间的关系和连接。在 JavaScript 中实现图可以使用多种技术来完成，包括使用邻接列表或邻接矩阵。本答案中演示的 Graph 类使用邻接列表表示形式，其中每个顶点都作为键存储在对象中，其相应的边作为该键的值存储在数组中。
Graph 类实现了向图形添加顶点和边、打印图形以及执行深度优先搜索和广度优先搜索遍历的方法。
以上就是JavaScript 中图的实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/529559.html
微信扫一扫 
支付宝扫一扫 
