树分为有根，无根两种，性质有：1.连通，2.n-1条边，3无环。dfs和bfs遍历树。直径：树上两点之间的最长距离。两次dfs确定。偏心距:距路径F最远的点到F的距离。核(为点的时候称为中心)为偏心距最小的点。重心：所有子树中最大子树...
图论——最小生成树(1)
最小生成树一般是求边权之和最小。Prim算法和Kruskal算法是求解最小生成树的两种算法。 //Prim算法堆优化 #include<iostream> #include<vector> #include<queu...
图论——最短路(2)
Floyd算法可在任意权图中求多源最短路，时间复杂度为O(n^3)，适用于n较小的情况。以P2910为例。 #include<iostream> #include<vector> using namespace std; ...
图论——最短路(1)
Dijkstra算法主要在非负权图中求最短路，朴素做法O(n^2),堆优化O((m+n)logn),前者在稠密图(m>=n^2)中效率较高，后者在稀疏图中效率较高。SPFA算法(Bellman-Ford算法队列优化)在...