图是一种非线性数据结构，表示一组顶点（也称为节点）以及它们之间的关系（或边）。顶点表示实体或对象，而边表示顶点之间的关系或连接。图可用于对许多不同类型的关系进行建模，例如社交网络、交通系统或信息流。
图有两种主要类型：有向图（也称为有向图）和无向图。在有向图中，边有一个方向，并且只能在一个方向上遍历，即从起始顶点到结束顶点。在无向图中，边没有方向，可以在两个方向上遍历。
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 类实现了向图形添加顶点和边、打印图形以及执行深度优先搜索和广度优先搜索遍历的方法。
以上就是JavaScript 中图的实现的详细内容，更多请关注双恒网络其它相关文章！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！
8. 精力有限，不少源码未能详细测试（解密），不能分辨部分源码是病毒还是误报，所以没有进行任何修改，大家使用前请进行甄别
9.本站默认解压密码为:www.sudo1.com
本站提供的一切软件、教程和内容信息仅限用于学习和研究目的。
不得将上述内容用于商业或者非法用途，否则，一切后果请用户自负。
本站信息来自网络收集整理，版权争议与本站无关。您必须在下载后的24个小时之内，从您的电脑或手机中彻底删除上述内容。
如果您喜欢该程序和内容，请支持正版，购买注册，得到更好的正版服务。
我们非常重视版权问题，如有侵权请邮件与我们联系处理。敬请谅解！
云资源网 » JavaScript 中图的实现
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用？
- 本站所有资源版权均属于原作者所有，这里所提供资源均只能用于参考学习用，请勿直接商用。若由于商用引起版权纠纷，一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了？
- 你们有qq群吗怎么加入？
