【数据结构笔记】5：图的邻接表结构下求无向图的连通分量

对于图的邻接表存储结构，有以下数据成员：

int vexNum, vexMaxNum, arcNum;// 顶点数目、允许的顶点最大数目和边数
AdjListNetWorkVex<ElemType, WeightType> *vexTable;// 顶点表
mutable Status *tag;        // 标志数组
WeightType infinity;// 无穷大的值

其中顶点节点的数据成员：

ElemType data;// 数据元素值
AdjListNetworkArc<WeightType> *firstarc;
// 指向邻接链表边结点的指针

其中边节点的数据成员：

int adjVex;// 弧头顶点序号
WeightType weight;// 边的权值
AdjListNetworkArc<WeightType> *nextarc; // 下一条边结点的指针

要实现求无向图的连通分量，可以按顶点节点数组顺序，从每个未被访问的节点开始DFS，搜索过的节点设为已经访问过的，每次执行DFS都对计数器w+1即可。

 

 

下面增加这两个函数作为邻接表类的public方法。

*邻接表的DFS

template <class ElemType, class WeightType>
void AdjListDirNetwork<ElemType, WeightType>::DFS(int v)
{
if(GetTag(v)==UNVISITED)//如果它没有访问过
{
SetTag(v, VISITED);//访问一下
AdjListNetworkArc<WeightType> *p;
p = vexTable[v].firstarc;//p从v的第一个相邻节点开始
while(p!=NULL)
{
if(GetTag(p->adjVex)==UNVISITED)//如果这个相邻节点没访问过
DFS(p->adjVex);//DFS它
p=p->nextarc;
}
}
}

*获取连通分量(传给引用w)

template <class ElemType, class WeightType>
void AdjListDirNetwork<ElemType, WeightType>::GetFenLiang(int &w)
{
w=0;//初始化计数器

//初始化全图
for(int v=0;v<vexNum;v++)
SetTag(v, UNVISITED);//全都变为没访问过的

for(int v=0;v<vexNum;v++)//对于每个顶点
{
if(GetTag(v)==UNVISITED)//如果没访问过
{
DFS(v);//DFS之,结束后其整个连通图的节点都将变为VISITED
w++;//如果执行到这里,说明进行了一次必要的DFS,子图显然要+1
}
}
}

加油。