使用 Javascript 处理图形数据结构

邻接表和邻接矩阵是计算机科学中表示图的两种常见方法。

邻接列表：

1. 邻接表将图表示为链表数组。
2. 数组的索引代表一个顶点，其链表中的每个元素代表与该顶点形成边的其他顶点。

优点：

1. 表示稀疏图（边较少的图）的空间效率。
2. 添加顶点更容易。

缺点：

1. 对于某些类型的查询效率较低，例如检查两个顶点之间是否存在边。
   更复杂的数据结构。

邻接矩阵：

1. 邻接矩阵将图表示为二维数组，其中第 i 行第 j 列的单元表示顶点 i 和 j 之间的边。

优点：

1. 易于理解和实施。
2. 对于密集图（具有更多边的图）非常有效。
3. 快速检查两个顶点之间是否存在边。

缺点：

1. 需要更多空间（o(v^2)，其中v是顶点数）。
   添加顶点的时间复杂度为 o(v^2)，可能比邻接表慢。

重要提示

1. 事先告知面试官你将采用哪种方法，并告诉他/她的优点和缺点。

图遍历

1. dfs（深度优先搜索）（堆栈）
2. bfs（呼吸优先搜索）（队列）

找到最短路径bfs会更好

*有向图与无向图：*

1. 有向图，也称为有向图，是每条边都有一个方向的图。边从一个顶点指向另一个顶点。

2. 无向图是边没有方向的图。边 (x, y) 与边 (y, x) 相同。

加权与未加权图表：

1. 加权图是为每条边分配权重或成本的图。这对于某些边具有不同重要性或长度的问题很有用。

2. 未加权图是所有边的权重或成本相等的图。

自循环：

1. 自环是将顶点连接到自身的边。

稀疏图与密集图：

1. 稀疏图是边数接近最小边数的图。换句话说，顶点之间的边很少。

2. 稠密图是边数接近最大可能边数的图。换句话说，顶点之间有很多条边。

循环图与非循环图：

1. 循环图是一种至少包含一个循环的图（一条边和顶点的路径，其中顶点可以从自身到达）。

2. 非循环图是没有循环的图。一种特殊类型的无环图称为树，是一种无环的连通无向图。

// 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 -------------
1
6
5
3
2
----------Breath First Traversal -------------
1
2
3
6
5
*/

登录后复制

以上就是使用 Javascript 处理图形数据结构的详细内容，更多请关注叮当号网其它相关文章！