图论基本概念：
自环
重边
孤点
简单图
有向图，无向图
简单图：
无向图的度数
有向图的度数：出度，入度
每个图的最大度，最小度
完全图（无向图）：
完全图（有向图）：
子图，生成子图：
补图：点集相同，边集不相交，并集为完全图
连通图，连通块：
图的储存方式：邻接矩阵，邻接表（链式，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)
题意：求最小生成树文章来源：https://www.toymoban.com/news/detail-816539.html
---板子（朴素or堆优化）文章来源地址https://www.toymoban.com/news/detail-816539.html
到了这里，关于图论基本知识---＞最短路练习---＞最小生成树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[Linux]线程基本知识](https://imgs.yssmx.com/Uploads/2024/02/613310-1.png)
