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

DFS和BFS函数很难写得像树的遍历方法那么通用，这在后面就会看到，虽然我们使用了DFS和BFS的思想，但是上面的函数却不能直接使用。因为树的信息主要在节点上，而图的边上还有信息。

测试程序

#include <iostream>
using namespace std;
#include "Graph.h"
int main()
{
Network<char, int, LinkedList<char, int> > a;
a.insertV(''A''); a.insertV(''B'');
a.insertV(''C''); a.insertV(''D'');
a.insertE(''A'', ''B'', 1); a.insertE(''A'', ''C'', 2);
a.insertE(''B'', ''D'', 3);
cout << "DFS: "; a.DFS(); cout << endl;
cout << "BFS: "; a.BFS(); cout << endl;
return 0;
}

老实说，这个类用起来真的不是很方便。不过能说明问题就好。

无向图

要是在纸上随便画画，或者只是对图做点示范性的说明，大多数人都会选择无向图。然而在计算机中，无向图却是按照有向图的方法来储存的——存两条有向边。实际上，当我们说到无向的时候，只是忽略方向——在纸上画一条线，难不成那线“嗖”的就出现了，不是从一头到另一头画出来的？ 无向图有几个特有的概念，连通分量、关节点、最小生成树。下面将分别介绍，在此之前，先完成无向图类的基本操作。

无向图类

template <class name, class dist, class mem>
class Graph : public Network<name, dist, mem>
{
public:
Graph() {}
Graph(dist maxdist) : Network<name, dist, mem> (maxdist) {}
bool insertE(name v1, name v2, dist cost)
{
if (Network<name, dist, mem>::insertE(v1, v2, cost))
return Network<name, dist, mem>::insertE(v2, v1, cost);
return false;
}
};

仅仅是添加边的时候，再添加一条反向边，很简单。

连通分量

这是无向图特有的，有向图可要复杂多了（强、单、弱连通），原因就是无向图的边怎么走都行，有向图的边好像掉下无底深渊就再也爬不上来了。有了DFS，求连通分量的算法就变得非常简单了——对每个没有访问的顶点调用DFS就可以了。

void components()
{
visited = new bool[vNum()]; int i, j = 0;
for (i = 0; i < vNum(); i++) visited[i] = false;
cout << "Components:" << endl;
for (i = 0; i < vNum(); i++)
{
if (!visited[i]) { cout << ''('' << ++j << '')''; DFS(i); cout << endl; }
}
delete []visited;
}

关节点

下定义是人们认识事物的一个方法，因为概念使得人们能够区分事物——关于这个还有个绝对的运动和相对的静止的哲学观点（河水总在流，但是长江还叫长江，记得那个著名的“不可能踏进同一条河里”吗？）因此，能否有个准确的概念往往是一门学科发展程度的标志，而能否下一个准确的定义反映了一个人的思维能力。说这么多废话，原因只有一个，我没搞清楚什么叫“关节点”——参考书有限，不能仔细的考究了，如有误解，还望指正。

严版是这么说的：如果删除某个顶点，将图的一个连通分量分割成两个或两个以上的连通分量，称该顶点为关节点。——虽然没有提到图必须是无向的，但是提到了连通分量已经默认是无向图了。

殷版是这么说

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