邻接表和邻接矩阵是计算机科学中表示图的两种常见方法。
邻接列表：
邻接表将图表示为链表数组。数组的索引代表一个顶点，其链表中的每个元素代表与该顶点形成边的其他顶点。
优点：
表示稀疏图（边较少的图）的空间效率。添加顶点更容易。
缺点：
立即学习“Java免费学习笔记（深入）”；
对于某些类型的查询效率较低，例如检查两个顶点之间是否存在边。更复杂的数据结构。
邻接矩阵：
邻接矩阵将图表示为二维数组，其中第 i 行第 j 列的单元表示顶点 i 和 j 之间的边。
优点：
易于理解和实施。对于密集图（具有更多边的图）非常有效。快速检查两个顶点之间是否存在边。
缺点：
立即学习“Java免费学习笔记（深入）”；
需要更多空间（o(v^2)，其中v是顶点数）。添加顶点的时间复杂度为 o(v^2)，可能比邻接表慢。
重要提示
事先告知面试官你将采用哪种方法，并告诉他/她的优点和缺点。
图遍历
dfs（深度优先搜索）（堆栈）bfs（呼吸优先搜索）（队列）
找到最短路径bfs会更好
*有向图与无向图：*
有向图，也称为有向图，是每条边都有一个方向的图。边从一个顶点指向另一个顶点。
无向图是边没有方向的图。边 (x, y) 与边 (y, x) 相同。
加权与未加权图表：
加权图是为每条边分配权重或成本的图。这对于某些边具有不同重要性或长度的问题很有用。
未加权图是所有边的权重或成本相等的图。
自循环：
自环是将顶点连接到自身的边。
稀疏图与密集图：
稀疏图是边数接近最小边数的图。换句话说，顶点之间的边很少。
稠密图是边数接近最大可能边数的图。换句话说，顶点之间有很多条边。
循环图与非循环图：
循环图是一种至少包含一个循环的图（一条边和顶点的路径，其中顶点可以从自身到达）。
非循环图是没有循环的图。一种特殊类型的无环图称为树，是一种无环的连通无向图。
// weighted graph adjacency list would look like{1: [ {node: 2, weight: 50}, {node: 3, weight: 60}]...6: [{node: 1, weight: 40}, {node:5, weight:30 }, {node:4, weight: 90}]}
登录后复制
class Graph { constructor() { this.adjList = {}; } addNode(value) { this.adjList[value] = [] } addEdge(node1, node2) { this.adjList[node1].push(node2); this.adjList[node2].push(node1); } removeEdge(node1, node2) { this.removeElement(node1, node2); this.removeElement(node2, node1); } removeElement(node, value) { const index = this.adjList[node].indexOf(value); this.adjList[node] = [...this.adjList[node].slice(0, index), ...this.adjList[node].slice(index+1)]; } removeNode(node) { const connectedNodes = this.adjList[node]; for (let connectedNode of connectedNodes) { this.removeElement(connectedNode, node); } delete this.adjList[node]; }depthFirstTraversal(startNode) { const stack = []; const visited = {}; stack.push(startNode); visited[startNode] = true; while(stack.length > 0) { const currentNode = stack.pop(); const connectedNodes = this.adjList[currentNode]; console.log(currentNode); connectedNodes.forEach(connectedNode => { if (!visited[connectedNode]) { visited[connectedNode] = true; stack.push(connectedNode); } }) } } breathFirstTraversal(startNode) { const queue = []; const visited = {} queue.push(startNode); visited[startNode] = true; while(queue.length > 0) { const currentElement = queue.shift(); const connectedNodes = this.adjList[currentElement]; console.log(currentElement); connectedNodes.forEach(connectedNode => { if (!visited[connectedNode]) { visited[connectedNode]=true; queue.push(connectedNode); } }); } }}const test = new Graph();test.addNode(1);test.addNode(2);test.addNode(3);test.addNode(4);test.addNode(5);test.addNode(6);test.addEdge(1,2)test.addEdge(1,3)test.addEdge(1,6)test.addEdge(2, 3);test.addEdge(2, 5);test.addEdge(2, 4);test.addEdge(3, 4);test.addEdge(3, 5);test.addEdge(4, 5);test.addEdge(4, 6);test.addEdge(5, 6);console.log('After adding all node and Edge --> ', test.adjList)test.removeNode(4);console.log('After Removing node 4 --> ', test.adjList)console.log('----------Depth First Traversal -------------')test.depthFirstTraversal(1);console.log('----------Breath First Traversal -------------')test.breathFirstTraversal(1);/*After adding all node and Edge --> { '1': [ 2, 3, 6 ], '2': [ 1, 3, 5, 4 ], '3': [ 1, 2, 4, 5 ], '4': [ 2, 3, 5, 6 ], '5': [ 2, 3, 4, 6 ], '6': [ 1, 4, 5 ]}After Removing node 4 --> { '1': [ 2, 3, 6 ], '2': [ 1, 3, 5 ], '3': [ 1, 2, 5 ], '5': [ 2, 3, 6 ], '6': [ 1, 5 ]}----------Depth First Traversal -------------16532----------Breath First Traversal -------------12365*/
登录后复制
以上就是使用 Javascript 处理图形数据结构的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2671591.html
