franki Blog

make a small progress every day

数据结构-图-章节9

章节 8 拓扑排序 AOV kahh 算法应用场景：工程当中需要用到事件活动，其中图中的顶点表示活动，图中的边表示事件遵循原则： <i,j> i 为 j 的直接前驱，j 为 i 的直接后继，当i无直接前驱时，可以先把这个顶点去掉，加到到一个数组里面并删除以 i 为弧尾的边重复以上过程当所有的顶点都已出现在数组中，说明图中不存在环。以下是 js...

Posted by franki on March 22, 2021

数据结构-图-章节8

章节 8 kruskal 算法最小生成树 kruskal 算法是一种贪婪算法，工作流程如下：创建图中所有的边当以上集合不为空，并且所有的顶点还未覆盖移除集合中最小边检查这条边是否构成一个环或者连接成2颗树，因此需要抛弃这条边，否则的话，把它加入到树当中当上述过程完毕后，就产生了一颗最小生成树为了实现这个算...

Posted by franki on March 13, 2021

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