一个无向图G的最小生成树就是由该图的那些连接了G的所有顶点的边构成的树，且其总权重最低。最小生成树存在当且仅当G是连通的。 对于任何一生成树T，如果将一条不属于T的边e加进来，则产生一个圈。如果从圈中...

Dijkstra算法解决了有向图G=(V,E)上带权的单源最短路径问题，但要求所有边的权值非负。 Dijkstra算法是贪婪算法的一个很好的例子。设置一顶点集合S，从源点s到集合中的顶点的最终最短路径...

有一个无权的图G，使用某个顶点s作为输入参数，找出从s到其它顶点的最短路径。这样，只要计算包含在路径中的边数就可以了。 比如，一个word ladder problem，一次只变换一个字母，找出从fo...

拓扑排序是对有向无圈图的顶点的一种排序。如果存在一条vi到vj的路径，则vi排在vj前面。如果图含有圈，则拓扑排序是不可能的。 拓扑排序的两种排法： 一个简单的求拓扑排序的算法是先找出任意一个没有入边...

一个图(graph)G=(V,E)是由顶点集V和边集E组成。每一条边就是一个顶点对(v,w)，其中v,w∈V。如果点对是有序的，那么图就是有向图。 图中的一条路径path是一个顶点序列w1,w2,w3...

如果我们可将自己的工作诠释成一个图问题的话，那么该问题至少已经接近解决方案了。而我们我们的问题实例可以用**树结构（tree）**来诠释，那么我们基本上已经拥有了一个真正有效的解决方案了。 0. 常见...

python数据结构之图的实现，官方有一篇文章介绍，http://www.python.org/doc/essays/graphs.html 下面简要的介绍下： 比如有这么一张图： A -> B...