408
数据结构 6.4 图的应用
最小生成树
Prim算法 从一个点出发寻找权值小的下一点
时间复杂度V^2
Kruskal算法 并查集寻找最短边的集合
时间复杂度e log e
最短路径
BFS 无权图
Djikstra算法 单源有权图 动态规划 加入后比较最短边
时间复杂度V^2 边上有负值不适用
Floyd算法 任意两点 顺序作为中间点比较
时间复杂度V^3 负值环路不适用
有向无环图DAG
用来储存算术表达式，压缩空间
拓扑排序
AOV网 节点代表活动
拓扑排序 先进行的活动必在前，无关系的点任意
无环必有拓扑排序 起始有入度，时间复杂度 V+E或V^2 三角矩阵必存在拓扑排序
关键路径
AOE网 边代表活动
关键路径 时间最长的路径
先画出关键路径再计算最迟时间