图的应用:最小生成树、最短路径、拓扑排序、关键路径
2021/10/12 23:16:39
本文主要是介绍图的应用:最小生成树、最短路径、拓扑排序、关键路径,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
最小生成树:
在图的所有生成树中,各边代价之和最小的那棵生成树称为最小代价生成树,简称最小生成树;
利用MST性质构造的算法:Prim、Kruskal
Prim:
初始u为v1,找v1的权值最小的边,<v1,v3>
找与v1、v3连接的权值最小的边,<v3,v6>
找与v1,v3,v6连接的权值最小的边,<v6,v4>
找v1,v3,v6,v4连接的权值最小的边,<v3,v2>
找v1,v3,v6,v4,v2连接的权值最小的边,<v2,v5>
Kruskal:
初始状态为n个顶点;不断添加权值最小的边;
最短路径:
Dijkstra算法:从某个源点到其余各顶点的最短路径
Floyd算法:顶点vi到vj之间的最短路径;
不断在vi和vj间加入其它顶点,并更新(筛选最短路径)
拓扑排序:
拓扑排序:AOV-网中vi到vj的路径,线性序列中vi必须在vj前面
用弧表示活动间的优先关系的有向图,顶点表示活动的网 activity on network(AOV-网)
有向无环图 directed acycline graph(DAG)
关键路径:
- 估算工程至少需要多少时间;
- 判断哪些活动是影响工程进度的关键
以边表示活动的网 activity on edge(AOE-网)
这篇关于图的应用:最小生成树、最短路径、拓扑排序、关键路径的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)