先看一下相关的定义：
定义1 设si是有向图G中的一个强连通分量，如果该强连通分量与图G的其他部分相连的所有弧都是向外伸展的，这样的强连通分量称为最高强连通分量。
定义2 在有向图G=(V,E)中，B是V的子集。如果对于任意的Vj属于V，不属于B，都存在一个Vi属于B，使得Vi是Vj的前代，则称B是一个点基。在有向图G中，顶点数最少的点基称为最小点基。设图G的每个顶点Vi都有一个非负的权值ai，使得顶点对应的权值之和最小的点基称为最小权点基。
基本算法：
（1）找出图G=(V,E)的所有强连通分量。
（2）从强连通分量中找出所有最高的强连通分量。
（3）从每个最高的强连通分量中任取一个顶点，组成的顶点集B就是G的最小点基。
如果要求最小权点基，只需将第三部改为“从每个最高强连通分量中取权值最小的一个顶点”即可。
2014-02-23