1. 最小生成树——Prime算法


从初始结点开始，依次找最短的边连接各结点。

2. 最小生成树——Kruskal算法


两两连接最小边，再并入结点

3. 最短路径——Dijkstra算法



最小子树

1 2 10 10

①1 5 5 5

②5 4 2 7

③5 2 3 8

④2 3 1 9

并查集（树）

①1—5:5

②1—5—4:7

③1—5—2:8

④1—5—2—3:9

4. 最短路径——Floyd算法


写出邻接矩阵，逐个加入点更新矩阵

5. AOV网及拓扑排序

DAG：有向无环图

AOV：顶点表示活动，边表示先后关系


依次去掉出发结点

7. AOE网及关键路径

AOE:顶点表示事件、边表示活动、权值表示开销


Ve(i):头结点到各个结点的最大距离，比如Ve(4)=a2+a5=2+4=6

Vl(i):倒序写，依次用最大距离减去临近的边长（注意最近的问题）比如：Vl(3)=V4-a5=6-4=2

e(i):将Ve(i)按结点划分写（最后一个结点不用写）

V1 | V2 | V3 | V4 | V5

a1 a2 | a3 a4 | a5 a6 | a7 | a8

0 0 3 3 2 2 6 6   

l(i):最近一个结点减去边长，例l(5) = V4-4

l-e=0为关键结点

广度优先搜索（BFS）



深度优先搜索（DFS）



总结：

BFS一层一层来

DFS一条路走到黑，不撞南墙不回头