图论基本知识—＞最短路练习—＞最小生成树

图论基本概念：

自环

重边服务器托管网

孤点

简单图

有向图，无向图

简单图：

无向图的度数

有向图的度数：出度，入度

每个图的最大度，最小度

完全图（无向图）：

完全图（有向图）：

子图，生成子图：

补图：点集相同，边集不相交，并集为完全图

连通图，连通块：

图的储存方式：邻接矩阵，邻接表（链式，ve）

图的遍历：（BFS，双向DFS(优化),DFS）

图上DFS：汉密尔顿通路问题，汉密尔顿回路问题，旅行商问题

最短路问题：贝尔曼，弗洛伊德，迪杰斯特拉

最小生成树：Prim,Kruskai

拓扑排序：

1：P1629 邮递员送信 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：求送信来回距离和最小

服务器托管网

—-双向dij或者spfa都可以（为啥优先队列不能存放结构体）

2:https://www.luogu.com.cn/problem/P2910

题意：求多个给定的定点间的最短距离并求和

—floyd

3：https://www.luogu.com.cn/problem/P1144

题意：算最短路数目

—dij或者spfa

***4：P1462 通往奥格瑞玛的道路 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

https://www.luogu.com.cn/problem/P1462

题意： 给定每个城市的过路费，经过每个城市会扣掉一定血量，歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。

—二分+单源最短路

5：P3366 【模板】最小生成树 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：求最小生成树

—板子（朴素or堆优化）

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: BWO白鲸优化算法

白鲸算法 ​ 白鲸算法(BWO)是一种新的元启发式算法，是一种基于群体的算法，其灵感来自于白鲸的行为，包括游泳，猎物和鲸落。在BWO的数学模型中构建了勘探，开发和鲸落阶段，并在开发阶段利用Levy飞行函数来提高BWO的收敛能力。 勘探阶段 ​ 由于BWO基于种…