Java教程

图的应用:最小生成树、最短路径、拓扑排序、关键路径

本文主要是介绍图的应用:最小生成树、最短路径、拓扑排序、关键路径,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

 最小生成树:

在图的所有生成树中,各边代价之和最小的那棵生成树称为最小代价生成树,简称最小生成树;

 利用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-网)

 

这篇关于图的应用:最小生成树、最短路径、拓扑排序、关键路径的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!