最小生成树及其性质 最小生成树是在一个给定的无向图中求一棵树T，使得这棵树拥有图G中的所有顶点，且所有的边均是来自图G中的边，并且满足整棵树的边权之和最小。 性质：最小生成树是树，因此其边数等于顶点数减一，且树内没有环；对于一个给定的图，最小生成树可以不唯一，但其边权之和一定是唯一的；由于最小生成树是在无向图中生成的，因此其根结点可以是这棵树上的任意点。 最小生成树的求解 一般有prim算法和kruskal算法，均是贪心的思想，不过贪心策略不大一样。 Prim算法 基本思想是对图G(V,E)设置集合S来存放已被访问的顶点，然后执行n次下面两个步骤(n为顶点数目)： 每次从集合V-...

单源最短路径 Dijkstra算法 Dijkstra算法的策略是：假设顶点集为V，设置集合S存放已被访问的顶点，然后执行下面两个步骤n次：（n为顶点数目） 每次从集合V-S中选择与起点s的最短距离最小的一个顶点（记为u），访问并加入集合S。 之后，令顶点u作为中介点，优化起点s与所有从u能到达且未访问过的顶点v的最短距离。 实现策略 集合S可用一个bool型数组vis[]来实现，vis[i]==true表示顶点Vi已经被访问；int型数组d[]表示起点s到顶点Vi的最短距离，初始时d[s]赋值为0，其余顶点赋值一个很大的数，来表示不可达。 伪代码 // G为图，一般设成全局变量；数组d为源...