六讲贯通C++图的应用之三 无向图(1)

笔者从基本储存方法、DFS和BFS、无向图、最小生成树、最短路径以及活动网络(AOV、AOE)六个方面详细介绍C++图的应用。之前我们已经介绍了基本存储方法、DFS和BFS，这篇我们继续介绍无向图。

无向图

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

无向图类

template <class name, class dist, class mem>  
class Graph : public Network  
{  
public:  
Graph() {}  
Graph(dist maxdist) : Network (maxdist) {}  
bool insertE(name v1, name v2, dist cost)  
{  
if (Network::insertE(v1, v2, cost))  
return Network::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;  
}