图论基本知识--->最短路练习--->最小生成树

发布时间:2024年01月23日

图论基本概念:

自环

重边

孤点

简单图

有向图,无向图

简单图:

无向图的度数

有向图的度数:出度,入度

每个图的最大度,最小度

完全图(无向图):

完全图(有向图):

子图,生成子图:

补图:点集相同,边集不相交,并集为完全图

连通图,连通块:

图的储存方式:邻接矩阵,邻接表(链式,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堆优化)

文章来源:https://blog.csdn.net/2302_79690531/article/details/135714155
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。