本文介绍: 图论基本知识—>最短路练习—>最小生成树
图论基本概念：
自环
重边
孤点
简单图
有向图，无向图
简单图：
无向图的度数
有向图的度数：出度，入度
每个图的最大度，最小度
完全图（无向图）：
完全图（有向图）：
子图，生成子图：
补图：点集相同，边集不相交，并集为完全图
连通图，连通块：
图的储存方式：邻接矩阵，邻接表（链式，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
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_61413.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
