franki Blog

make a small progress every day

数据结构-图-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

数据结构-图-find a path

图的深度优先遍历通过 dfs 得到每个顶点经过的路径，然后通过遍历得到结果代码实现 class Path { constructor(g, s) { this.g = g; this.s = s; this.from = new Array(g.V()).fill(-1); this.visited = new Array(g.V()).fill...

Posted by franki on September 26, 2022

数据结构-图-dfs

图的深度优先遍历图的 dfs 跟树的 dfs 类似，都是从一个顶点一直遍历到不可遍历为止，通过 dfs 可以求出图的联通分量，每个顶点的联通分量代码实现 class DFSComponent { constructor(g) { this.g = g; this.visited = new Array(g.V()).fill(false); this....

Posted by franki on September 25, 2022

数据结构-图-read graph

读取一张图使用 nodejs 本身自带的文件读取模块 read-line 代码实现 const fs = require('fs'); const readline = require('readline'); // const DenseGraph = require('./dense-graph'); const SparseGraph = require('./sparse-g...

Posted by franki on September 24, 2022

数据结构-图-sparse graph

图论基础-稀疏图稀疏图实现过程定义一个 n * x 的数组，x 表示每一个顶点里面相连顶点的集合注意：稀疏图存在平行边，也就是 1 - 2 可能出现多次代码实现 // 稀疏图 class SparseGraph { constructor(n, directed) { this.n = n; // 表示顶点个数 this.m = 0; // 表示边的个数...

Posted by franki on September 23, 2022

数据结构-图-dense graph

图论基础-稠密图稠密图实现过程使用一个 n*n 的矩阵，一开始矩阵里面的元素都是 false 应用场景是：数据较多，场景复杂的图代码实现 // 稠密图 class DenseGraph { constructor(n, directed) { this.n = n; // 图的顶点数 this.m = 0; // 图的边数 this.directed ...

Posted by franki on September 22, 2022

数据结构-图-mind

图 - mind 从今天开始继续温习数据结构与算法，把之前对于图的部分进行代码实现，对于图的里面包括算法需要的数据结构进行融会贯通，争取对于运用到的数据结构理解更加透彻。图的分类及其使用

Posted by franki on September 21, 2022

leetcode 235题

leetcode 235题二叉搜索树的最近公共祖先给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null...

Posted by franki on January 13, 2022

leetcode 234题

leetcode 234题回文链表给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。示例 1：输入：head = [1,2,2,1] 输出：true 示例 2：输入：head = [1,2] 输出：false 提示：链表中节点数目在范围[1, 105] 内 0 <= Node.val <...

Posted by franki on January 12, 2022