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

【附注】这里需要说明一下，对于edge[I][I]这样的是应该是0呢还是NoEdge呢？显然0合理，但是不好用。并且，从有权图无权图统一的角度来说，是NoEdge更好。因此，在我的有权图的邻接矩阵中，主对角线上的元素是NoEdge，而不是书上的0。

测试程序

储存和操作分离，没想到得到了一个有趣的结果——对于最后的无向图而言，最小生成树的算法对外表现不知道是采用了那个算法。

template <class name, class dist, class mem>
bool Graph<name, dist, mem>::MinSpanTree()
{
MSTedge<dist>* a = new MSTedge<dist>[vNum() - 1];
int n = data.MinSpanTree(a); dist sum = dist();
if (n < vNum() - 1) return false;//不够N－1条边，不是生成树
for (int i = 0; i < n; i++)
{
cout << ''('' << getV(a[i].v1) << '','' << getV(a[i].v2) << '')'' << a[i].cost << '' '';
sum += a[i].cost;
}
cout << endl << "MinCost: " << sum << endl;
delete []a;
return true;
}

最后的测试图的数据取自殷版（C++）——不知是这组数据好是怎么的，殷版居然原封不动的照抄了《数据结构算法与应用-C++语言描述》（中文译名）

最短路径

最短路径恐怕是图的各种算法中最能吸引初学者眼球的了——在地图上找一条最短的路或许每个人都曾经尝试过。下面我们用计算机来完成我们曾经的“愿望”。

在图的算法中有个有趣的现象，就是问题的规模越大，算法就越简单。图是个复杂的结构，对于一个特定问题，求解特定顶点的结果都会受到其他顶点的影响——就好比一堆互相碰撞的球体，要求解特定球体的状态，就必须考虑其他球体的状态。既然每个顶点都要扫描，如果对所有的顶点都求解，那么算法就非常的简单——无非是遍历吗。然而，当我们降低问题规模，那很自然的，我们希望算法的规模也降低——如果不降低，不是杀鸡用牛刀？但是，正是由于图的复杂性，使得这种降低不容易达到，因此，为了降低算法的规模，使得算法就复杂了。

在下面的介绍中，清楚了印证了上面的结论。人的认知过程是从简单到复杂，虽然表面看上去，求每对顶点之间的最短路径要比特定顶点到其他顶点之间的最短路径复杂，但是，就像上面说的，本质上，前者更为简单。下面的介绍没有考虑历史因素（就是指哪个算法先提出来），也没有考虑算法提出者的真实想法（究竟是谁参考

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