本节内容主要涉及图论中主要思想的解答
都已经写了三份博文介绍图论了，那么目前来说主要的内容都基本涉及到了，本文就稍微对第一和第二节文章中的内容稍微概况总结一下，有可能会有相同的地方，主要需要具有离散数学知识的可以参考一下

图主要涉及的问题

最小生成树

在图G所有生成树中，代价最小的生成树称为最小生成树。
应用举例：在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？

两种主要求生成树的算法

普里姆（Prim）算法　　　

基本思想：设G=(V, E)是一个无向连通网，T=(U, TE)是G的最小生成树， T的初始状态为U={u0}（u0∈V），TE={ }，重复执行下述操作：在所有u∈U，v∈V-U的边中找一条代价最小的边(u, v)并入集合TE，同时v并入U，直至U=V。

克鲁斯卡尔（Kruskal）算法　

基本思想：设无向连通网为G＝(V, E)，令G的最小生成树为T＝(U, TE)，其初态为U＝V，TE＝{ }，然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。
prim一般求稠密图，kruscal算法求稀疏图。

最短路径

最短路径是指两顶点之间经历的边上权值之和最短的路径。（最小生成树的延伸）

Dijkstra算法　

基本思想设集合S 存放已找到最短路径的顶点，S的初态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, …, vk，就将vk 加入集合S中，并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。

Floyd算法

基本思想：对于从vi到vj的弧，进行n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，则比较vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。

上面的两种算法都是用于从某一点开始，到其他点的最短路径，其算法复杂度均为O(n^3)。

关键思想通过不断的调整路径，实现最短。

SPFA 算法　　　　　　

算法思想：我们用数组d记录每个结点的最短路径估计值，用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止

AOV网与拓扑排序

AOE网与关键路径

主要是拓扑排序

拓扑序列：设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1, v2, …, vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。拓扑排序：对一个有向图构造拓扑序列的过程称为拓扑排序