franki Blog

make a small progress every day

数据结构-图-章节7

章节 7 prim 算法最小生成树由一副连通加权无向图中一课权值最小的生成树。 prim 实现： //定义邻接矩阵 let Arr2 = [ [0, 10, 65535, 65535, 65535, 11, 65535, 65535, 65535], [10, 0, 18, 65535, 65535, 65535, 16, 65535, 12], [65535, 65...

Posted by franki on March 12, 2021

数据结构-图-章节6

章节 6 深度优先搜索（DFS）和广度优先搜索（BFS）深度优先搜索图1 无向图深度优先搜索的过程类似于树的先序遍历,如图1的过程被分解为： 1 首先任意找到一个未被遍历过顶点，从v1开始，由于v1率先被访问过了，所以需要被标注为已访问。 2 接着遍历v1的邻接点，例如访问v2，并做标志，然后访问v2的邻接点，例如v4，然后v8，然后v5。 3 当v5没有邻接点时，根据之前做...

Posted by franki on March 11, 2021

数据结构-图-章节5

章节5 图的邻接表存储法通常，图更多的是采用链表存储，具体存储方式有3种，分别是邻接表、邻接多重表和十字链表。邻接表存储法，既适用于存储无向图，也适用于存储有向图。邻接点：在图中，如果两个点相互连通，即通过其中一个顶点，可直接找到另一个顶点，则称它们互为邻接点。邻接指的是图中顶点之间有边的存在邻接表存储图的实现方式是，给图中的各个顶点独自建立一个链表，用节点存储该顶点，用...

Posted by franki on March 10, 2021

数据结构-图-章节4

章节4 图的顺序存储结构使用图结构表示的数据元素之间虽然具有多对多的关系，但是同样可以采用顺序存储，即是采用数组有效存储图。使用数组表示图时，需要使用两个数组，一个数组存放图中的顶点本身的数据（一维数组），另一个数组存放各顶点之间的关系（二维数组）不同类型的图，存储的方式略有不同，根据图有无权，可以将图划分为两大类：图和网图，包括无向图和有向图；网只表示带权的图，包括无向图和...

Posted by franki on March 9, 2021

数据结构-图-章节3

章节3 生成树（生成森林）对连通图进行遍历，过程中所经历的边和顶点的组合可看作是一颗普通树，通常称为生成树。图1 图1a是一张连通图，图1b是其对应的2中生成树注意：连通图中，由于任意两顶点之间可能含有多条通路，遍历连通图的方式有多种，往往一张连通图可能有多种不同的生成树与之对应对应。连通图中的生成树必须满足以下2个条件 1 包含连通图中的所有顶点 2 任意两顶点之间有且...

Posted by franki on March 8, 2021

数据结构-图-章节2

章节2 连通图图中从一个顶点到另一个顶点，若至少存在一条路径，则称为这两个顶点是想通的。如图1，虽然v1 v3没有直接关联，但从v1到v3存在两条路径，分别是v1-v2-v3和v1-v4-v3，因此v1和v3直接是连通的。图1 无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图。例如图2中的无向图就是一个连通图，因此图中的任意两顶点之间都是想通的。图2 若无向...

Posted by franki on March 7, 2021

数据结构-图-章节1

章节1 图的存储方式完全攻略数据之间的关系有一对一，一对多，多对多，前两种关系可以用链表和树来存储，多对多这种关系需要用到新的数据结构-图来存储图1 无向图可以看到v1 与 v3 v4 v2都有关系，v4与v3 v1有关系图中存储的各个数据元素被称为顶点。如上有v1 v2 v3 v4四个顶点图2 有向图图2的各个顶点之间的关系并不是双向的。比如v3 只与v4有关系，...

Posted by franki on March 6, 2021

数据结构-图阶段目标

力争拿下图 1 稠密图（邻接矩阵） 2 稀疏图（邻接表） 3 深度优先算法 4 广度优先算法 5 普里姆(Prim)算法 6 克鲁斯卡尔(Kruskal)算法 7 拓扑排序算法 8 关键路径 9 最短路径 10 最小生成树 11 迪克斯特拉(Dijkstra)算法 12 弗洛伊德(Floyd)算法

Posted by franki on March 5, 2021

leetcode 151题

leetcode 151题翻转字符串里的单词给定一个字符串，逐个翻转字符串中的每个单词。说明：无空格字符构成一个单词。输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。示例1: 输入："the sky is blue" 输出："blue is sky the" ...

Posted by franki on March 4, 2021

leetcode 344题

leetcode 344题反转字符串编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。示例1: 输入：["h","e","l","l","o"] 输出：["o","l",...

Posted by franki on March 3, 2021