图算法分类简介

最小生成树能够保证整个拓扑图的所有路径之和最小，但不能保证任意两点之间是最短路径。 （路总长最小连接所有点）

最短路径是从一点出发，到达目的地的路径最小 （一点到达零一点）

最小生成树-prim和krustal

给定一个n个点m条边的无向图，求最小生成树的树边权重之和 目标如何找到一条路径使得沿此路径上各边上的权值总和达到最小（路径规划）

http://www.cppblog.com/abilitytao/archive/2009/09/05/95399.html

例子：684. 冗余连接 （leetcode） 859

prim：

一个找过的节点附近最短边：从连通网络 N = {V, E}中的某一顶点 u0出发, 选择与它关联的具有最小权值的边 (u0 , v), 将其顶点加入到生成树顶点集合U中。以后每一步从一个顶点在集合U中, 而另一个顶点不在集合U中的各条边中选择权值最小的边(u, v), 把它的顶点加入到集合U中。如此继续下去, 直到网络中的所有顶点都加入到生成树顶点集合U中为止。

比较

Prim算法适用于边稠密的网络。

 Kruskal算法更适合于边稀疏的情形。

 注意：当各边有相同权值时，由于选择的随意性，产生的生成树可能不唯一。

从二者的原理来看, Kruskal算法是基于边的算法，而Prim算法则是基于顶点的。因此对于一个边数很多的图，Prim算法较快。

最短路径—Dijkstra算法和Floyd算法

leetcode 743

Dijkstra算法：

krustal：克鲁斯卡尔算

一个先找最短边，不连通就加进去，联通下一个；-最小堆和并查集

并查集：

初始：每个元素都属于各自独立的集合

 操作

Find(x) 返回元素x在哪个集合中

Union(x, y) 合并元素x和y所在的集合

Warshall-Floyd算法

 

环判断是否有向图：拓扑和dfs

leetcode 207,210

https://my.oschina.net/u/4365005/blog/3858341/print https://www.cnblogs.com/helloWaston/p/4624773.html

不会的算法题找到思路在搜索不要搜原题