首页建站笔记 web前端 JavaScript 正文

我要投稿

使用 Javascript 处理图形数据结构

资讯主编 JavaScript

2024-08-12 0 331

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

邻接列表：

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

优点：

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

缺点：

立即学习“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}]
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

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 &gt; 0) {
            const currentNode = stack.pop();
            const connectedNodes = this.adjList[currentNode];
            console.log(currentNode);
            connectedNodes.forEach(connectedNode =&gt; {
                if (!visited[connectedNode]) {
                    visited[connectedNode] = true;
                    stack.push(connectedNode);
                }
            })
        }
    }

    breathFirstTraversal(startNode) {
        const queue = [];
        const visited = {}

        queue.push(startNode);
        visited[startNode] = true;

        while(queue.length &gt; 0) {
            const currentElement = queue.shift();
            const connectedNodes = this.adjList[currentElement];
            console.log(currentElement);
            connectedNodes.forEach(connectedNode =&gt; {
                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 --&gt; ', test.adjList)

test.removeNode(4);

console.log('After Removing node 4 --&gt; ', test.adjList)
console.log('----------Depth First Traversal -------------')
test.depthFirstTraversal(1);
console.log('----------Breath First Traversal -------------')
test.breathFirstTraversal(1);

/*
After adding all node and Edge --&gt;  {
  '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 --&gt;  {
  '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
*/

登录后复制

收藏 (0) 打赏

感谢您的支持，我会继续努力的!

打开微信/支付宝扫一扫，即可进行扫码打赏哦，分享从这里开始，精彩与您同在

免责声明
1. 本站所有资源来源于用户上传和网络等，如有侵权请邮件联系本站整改team@lcwl.fun！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系本站工作人员处理！
6. 本站资源售价或VIP只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，请使用WINRAR解压，如遇到无法解压的请联系管理员！
8. 因人力时间成本问题，部分源码未能详细测试（解密），不能分辨部分源码是病毒还是误报，所以没有进行任何修改，大家使用前请进行甄别！
9.本站所有源码资源都是经过本站工作人员人工亲测可搭建的，保证每个源码都可以正常搭建，但不保证源码内功能都完全可用，源码属于可复制的产品，无任何理由退款！

网站搭建学习网 JavaScript 使用 Javascript 处理图形数据结构 https://www.xuezuoweb.com/12229.html