图论 #Eular

欧拉（回）路（树）

一、欧拉路径定义欧拉路径是指从图中任意一个点开始到图中任意一个点结束的路径，并且经过图中每条边，且只经过一次。存在条件连通图对于无向图：有且只有两个点的度为一，且这两个点分别为起点和终点。对于有向图：存在一个点出度比入度多一作为起点，存在一点入度比出度多

acautomaton

Published on 2023-08-26

图论 #Floyd

传递闭包

别以为是什么高级算法，其实就是 $Floyd$算法不计算距离，只判断连通性... public static void floyd(boolean[][] connect, int n) { for (int k = 0; k < n; k++) { for (int i =

acautomaton

Published on 2023-08-25

图论 #Floyd

Floyd算法

一、简介 $ Floyd $ 算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径

acautomaton

Published on 2023-08-25

图论 #前缀和 #差分 #Dijkstra #Bellman-Ford #SPFA

差分约束

部分内容来自差分约束 - 知乎一、简介差分约束系统是一种多元一次不等式组（ y_1,\ y_2 ,...,y_n 为已知量）： \begin{cas

acautomaton

Published on 2023-08-23

图论 #Dijkstra #Bellman-Ford #SPFA

SPFA算法

一、简介 SPFA算法是Bellman-Ford算法的队列优化。它可以求出单源最短路，也可检测到负环，实现起来也比较容易。但是现在很多题目会卡SPFA，所以要看情况使用。二、中心思想可以证明，只有上一次迭代中松弛过的点才有可能参与下一次迭代的松弛操作。朴素的Bellman-Ford算法中对于每一

acautomaton

Published on 2023-07-01

图论 #Bellman-Ford

Bellman-Ford算法

一、简介 Bellman-Ford算法是由Richard Bellman和Leicester Ford创立的，求解单源最短路径问题的一种算法。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。其优于Dijkstra算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(V*

acautomaton

Published on 2023-06-30

图论 #Dijkstra

Dijkstra算法

一、简介 Dijkstra算法是由荷兰计算机科学家Edsger Wybe Dijkstra于1959年提出的，是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。Dijkstra算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩

acautomaton

Published on 2023-06-29