数据结构学习(C++)之图

问题出来了，非连通图是否可以讨论含有关节点？我们是否可以说某个连通分量中含有关节点？遗憾的是，严版留下这个问题之后，在后面给出的算法是按照连通图给的，这样当图非连通时结果就是错的。殷版更是滑头，只输出重连通分量，不输出关节点，自己虽然假定图是连通的，同样没有连通判断。

翻翻离散数学吧，结果没找到什么“关节点”，只有“割点”，是这样的：一个无向连通图，如果删除某个顶点后，变为非连通图，该顶点称为割点。权当“割点”就是“关节点”，那么算法至少也要先判断是否连通吧？可是书上都直接当连通的了……

关于算法不再细说，书上都有。下面的示例，能输出每个连通分量的“关节点”（是不是可以这样叫，我也不清楚）。dfn储存的是每个顶点的访问序号，low是深度优先生成树上每个非叶子顶点的子女通过回边所能到达的顶点最小的访问序号。把指向双亲的边也当成回边并不影响判断，因此不必特意区分，殷版显式区分了，属于画蛇添足。这样一来，if (low[n] >= dfn[i]) cout << getV(i);这个输出关节点的判断中的>=就显得很尴尬了，因为只能等于不可能大于。还要注意的是，生成树的根（DFS的起始点）是单独判断的。

最小生成树

说人是最难伺候的，真是一点不假。上面刚刚为了“提高可靠性”添加了几条多余的边，这会儿又来想办法怎么能以最小的代价把所有的顶点都连起来。可能正是人的这种精神才使得人类能够进步吧——看着现在3GHz的CPU真是眼红啊，我还在受500MHz的煎熬，然后再想想8086……

正如图的基本元素是顶点和边，从这两个方向出发，就能得到两个算法——Kruskal算法（从边出发）、Prim算法（从顶点出发）。据说还有别的方法，恕我参考资料有限，不能详查。

最小生成树的储存

显然用常用的树的储存方法来储存没有必要，虽然名曰“树”，实际上，这里谁是谁的“祖先”、“子孙”并不重要。因此，用如下的MSTedge结构数组来储存就可以了。

template <class dist>
class MSTedge
{
public:
MSTedge() {}
MSTedge(int v1, int v2, dist cost) : v1(v1), v2(v2), cost(cost) {}
int v1, v2;
dist cost;
bool operator > (const MSTedge& v2) { return (cost > v2.cost); }
bool operator < (const MSTedge& v2) { return (cost < v2.cost); }
bool operator == (const MSTedge& v2) { return (cost == v2.cost); }
};

Krus

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!