- 博客(5)
- 收藏
- 关注
RSS订阅原创 图论学习笔记——最短路径之Dijkstra算法
Dijkstra（迪杰斯特拉）算法Dijkstra算法是一种时间复杂度为的算法，相较于时间复杂度为的Floyd算法来说效率更高了一些，但是Dijkstra算法是一种单源路径算法，也就是说只能计算起点只有一个的情况，并且不能处理存在边的权值为负数的情况。Dijkstra算法的实现（使用邻接矩阵储存图）首先我们要定义一个一维的dis数组，设起点为s，则设dis[v]表示的是从起点s到点v的...
2019-02-13 15:54:51
336
5
原创 数论学习笔记——快速幂||取模运算
快速幂快速幂，就是幂运算的一种快速算法，它的时间复杂度为，相较于传统计算方式的有很大的提升。在了解快速幂之前，我们需要先了解一下传说中的二进制。浅谈二进制要知道，这个世界上只有10种人，一种是懂二进制的人，另一种是不懂二进制的人。（滑稽）相对于十进制， 我们生活中所用的是十进制，满十进一。那么二进制，顾名思义，就是满二进一。就像上上段的那个笑话一样，10（读作：一零）它其实...
2019-02-12 16:42:53
411
1
原创 图论学习笔记——求最短路长度之万用（大概）但不万能（O(n^3)）的Floyed|Floyd算法
经典Floyed（弗洛伊德）算法Floyed算法是最简单的求最短路的算法，这种算法可以计算出图中任意两点的最短路的距离，但是。。。经典Floyed算法的时间复杂度是O()。。。如此高的时间复杂度也只能用来骗骗分了，已笔者目前的知识水平也只能将其优化至特定条件下最坏情况的时间复杂度为，顶多骗一个点。。。 下面介绍一下传统的Floyed算法：首先我们先定义一些量，dis[u][v]表示...
2019-02-12 10:14:40
331
2
原创 图论学习笔记——一笔画（最少笔画）问题
咳，要想解决如题的问题，我们首先要引入一些定理（仅在一张连通图中通用）。我们先定义寄点是跟这个点相连的边数目有奇数个的点。对于能够一笔画的图，我们有一下两个定理。定理1：如果一张图存在一笔画且不会回到起点，这个图有且只有2个寄点。（前提是图是连通的）。我们称这样的路径为欧拉路。。。所以我们也可以知道这玩意是谁恁出来的了。。。。。。。定理2：如果一个张图存在一笔画且最后回到起点，这个图没...
2019-02-11 10:07:44
4756
原创 图论学习笔记——图的储存结构
1、二维数组邻接矩阵储存这是一种以点来储存图的方式具体操作就是建立一个整形二维数组G，G[i][j]表示从i点到j点的边的权值（有向），无向图可以灵活变通运用，如果图中只存在边通不通的情况可以建立bool类型的数组节约内存。2、数组模拟邻接表储存（链式前向星）①、前向星在学习链式前向星之前，我们首先要明白什么是前向星，也就是链式前向星的前身。相对于用二维数组储存邻接矩阵以两...
2019-02-11 09:44:32
311
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人