（一）求最小生成树算法
1）生成树
（1）连通图：任意两点都是连通的图。
（2）生成树（Spanning Tree）：设图G=(V,E)是一个连通图，如果其子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。
对于有n个顶点的连通图，至少有n-1条边，而生成树中恰好有n-1条边，所以连通图的生成树是该图的极小连通子图。若在图的生成树中任意加一条边，必然形成回路。
图的生成树不唯一。从不同的顶点出发，选择不同的存储方式和遍历方式，可以得到不同的生成树。
非连通图的生成树森林：对于非连通图而言，每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树。
2）最小生成树
生成树的权：生成树的各边的权值总和。
最小生成树：权值最小的生成树。
算法：普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。
（1）普里姆（Prim）算法
步骤：
①初始化：选择一个起始顶点，并将其加入到最小生成树中。
②选择最小边：在所有连接树内顶点和树外顶点的边中，选择一条权值最小的边，并将其加入到最小生成树中。
③重复操作：重复上述操作，直到所有顶点都被加入到树中。
过程：以一个顶点集合U作初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充U集合直至U=V时为止。
（2）克鲁斯卡尔（Kruskal）算法
步骤：
①初始化：将所有顶点视为独立的连通分量。
②选择边：从所有边中选择权值最小的边，判断这条边是否会与已经选择的边构成回路。
③判断回路：如果选择的边的两个顶点属于同一个连通分量，则这条边会形成回路，应该舍去；如果属于不同的连通分量，则这条边可以加入到最小生成树中，并将两个连通分量合并。
④重复选择：重复上述过程，直到所有顶点都在一个连通分量中为止。
算法时间复杂度为O（eloge） （e为网中边数），与图中顶点数无关，适合于求边稀疏的网的最小生成树。
（二）拓扑排序
1）AOV网
AOV网（Activity On Vertex network）：在工程领域，一个大的工程项目通常被划分为许多较小子工程（活动）。若以顶点表示活动，有向边表示活动之间的优先关系的有向图。孤表示活动之间的优先关系（制约）。
注意：AOV网中不应出现有向环，若存在则意味着某项活动必须以自身任务的完成为先决条件（荒谬）。
若要检测一个工程划分后是否可行，应先检查对应AOV网是否存在回路。检测方法是对其AOV网进行拓扑排序。
2）拓扑排序
将AOV网中所有顶点排成一个线性序列的过程，且该序列满足：若在AOV网中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。
AOV网的一个拓扑排序就是一个工程顺利完成的可行方案。
执行结果会有两种情况：
①所有顶点己输出，此时整个拓扑排序完成，说明网中不存在回路；
②尚有未输出顶点，剩余顶点均有前驱顶点，表明网中存在回路，拓扑排序无法进行下去。
（三）求单源点的最短路径算法
单源点最短路径：指从一个源节点出发，计算到其他所有节点的最短路径。
常用于路由算法和其他网络路径查找应用中。
迪杰斯特拉在1959年（Dijkstra）提出了按路径长度递增的次序产生最短路径的算法。
举例：北京到海南的最短旅行路径
