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

图论基本概念：

自环

重边

孤点

简单图

有向图，无向图

简单图：

无向图的度数

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

每个图的最大度，最小度

完全图（无向图）：

完全图（有向图）：

子图，生成子图：

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

连通图，连通块：

图的储存方式：邻接矩阵，邻接表（链式，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堆优化）

代码007普通

打赏 收藏 海报 链接