最小生成树和最短路径

一、概念的理清

1、图分为连通图和非连通图，我们一般讨论连通图。带权的图叫做网。

2、连通图的生成树：（1）包含图的所有的n个顶点；（2）只有n-1条边，且这n-1条边足以构成一棵树；

3、最小生成树：构造连通网的生成树，且代价最小。简单理解，就是连通所有的点，而且权值总和最小的生成树。

4、最短路径：两点之间权值总和最小的路径。

二、最小生成树常用算法

1、P算法：

2、K算法：

三、最短路径常用算法

1、D算法：特定两点之间的最短路径；

2、F算法：可以算出所有顶点两两之间的最短路径；

3、深度优先和广度优先：找出两点之间的所有路径，比较得出结果