franki Blog

make a small progress every day

数据结构-带优化的 prim

带优化的 prim 从上文求出的最小生成树，可以发现有很多重复的选项被判断，而且最小堆里面存在很多相同的顶点不同边，没有及时判断出那条边是最小的情况，理应得到当前顶点相连的最小的边，其他的排除掉，减少执行的判断，减少复杂度。代码实现 const IndexReverseMinHeap = require('./index-reverse-min-heap'); class Prim...

Posted by franki on October 5, 2022

数据结构-带优化的最小索引堆

带优化的最小索引堆上文实现的最小索引堆，存在以下问题： 1 extractMin 需要把索引数组 pop 出来，导致索引数组大小发生变化 2 没有实现 change 方法，用于改变索引对应的值，如果要实现的话，需要通过索引遍历的方式去找到数据数组在排序后在索引堆的位置所以在这里加入了反向索引堆的概念，主要是为了方便 change 的使用，可以通过小标直接找到数组排序后在索引堆的正确位...

Posted by franki on October 4, 2022

数据结构-最小索引堆

最小索引堆由于最小堆存在以下问题：如果数据非常大的情况下，堆中交换元素会消耗大部分的时间位置改变后，查询元素会变得困难所以需要通过索引堆来实现，实现之后，现在不是直接交换堆中的元素，而是增加多一个 index 堆，直接对于索引执行操作代码实现 const MinHeap = require('./min-heap'); class IndexMinHeap ...

Posted by franki on October 3, 2022

数据结构-图-最小生成树

最小生成树最小生成树通过每个顶点相连接的所有边，取当前最小的一条边，判断两个顶点是否都被记录过，如果是，则跳过，否则，继续使用另一个顶点重复上述过程。期间使用最小堆模拟优先队列，每次拿到最小的那条边，放入到最小生成树中，把生成树中的每条边累加就得到生成树所有权值。代码实现 const MinHeap = require('./min-heap'); class LazyPrim ...

Posted by franki on October 2, 2022

数据结构-图-最小堆

最小堆最小堆的实现是通过数组来模拟的，最小堆是一颗完全二叉树，主要通过上移操作、下移操作来实现。代码实现 class MinHeap { constructor() { this.data = []; this.count = 0; // 下标从1开始，为了获取父节点的时候好计算 } buildData(arr) { // data 第一个元素...

Posted by franki on October 1, 2022

数据结构-图-read weight graph

读取有权图读取有权图跟读取一般图没有什么大的区别，只是在添加边的时候，需要把边的权重传入而已。（稠密图使用矩阵实现，稀疏图使用邻接表实现）代码实现 const fs = require('fs'); const readline = require('readline'); const SparseGraph = require('./sparse-graph'); const ...

Posted by franki on October 1, 2022

数据结构-图-weight sparse graph

有权图-实现稀疏图有向图的稀疏图实现也跟一般的稀疏图实现类似，主要是把邻接表里面的每个元素换成了 edge 代码实现 const Edge = require("./edge"); class SparseGraph { constructor(n, directed) { this.n = n; this.m = 0; this.directed = ...

Posted by franki on September 30, 2022

数据结构-图-weight dense graph

有权图-实现稠密图带权的稠密图，跟普通稠密图类似，只不过现在二维数组里面的每个元素，不再是存放简单的 true 或者 false，而是存放 edge (包含顶点 v, 顶点 w，weight 权重) 代码实现 const Edge = require('./edge'); class DenseGraph { constructor(n, directed) { thi...

Posted by franki on September 29, 2022

数据结构-图-edge

有向图-边的表示有向图需要用到权的概念，即是两个顶点之间的权重，在现实生活中，可以用来表示两个顶点之间的距离，也可以表示两个顶点之间的交通费用。代码实现 class Edge { constructor(a, b, w) { this.a = a; this.b = b; this.weight = w; } v() { return ...

Posted by franki on September 28, 2022

数据结构-图-bfs

图的宽度优先遍历图的宽度优先遍历类似于树的宽度优先遍历，都是先遍历根，然后找到这个节点的邻近节点，通过一个 queue 来保存这些节点，通过遍历这个 queue，重复以上过程，则可以实现代码实现 class BFCComponent { constructor(g, s) { this.g = g; this.s = s; this.visited = ...

Posted by franki on September 27, 2022