试编写求无向图G的连通分量的算法。要求输出每一连通分量的顶点

[问答题]

试编写求无向图G的连通分量的算法。要求输出每一连通分量的顶点值。(设图G已用邻接表存储)

类似本题的另外叙述有：

（1）写出求无向图G中各连通分量的顶点集的算法COMF（G）。可调用的运算是：FIRST_ADJ（G，V）--求顶点V的第一邻接点，NEXTADJ（G，V，W）--求顶点V关于W的下一个邻接点。

（2）编程求解无向图G的所有连通分量。

Letitia

[ 题目分析] 使用图的遍历可以求出图的连通分量。进入dfs或bfs一次，就可以访问到图的一个连通分量的所有顶点。

void  dfs (){visited[v]=1; printf ( “%3d”,v); //输出连通分量的顶点。p=g[v].firstarc;
while 
(p!=null)  {if（visited[p->adjvex==0]） 
dfs(p->adjvex);   p=p->next;
}//while
}// 
dfs
  void  
Count()
    //求图中连通分量的个数     {int k=0 ; static AdjList g ; //设无向图g有n个结点      for (i=1;i<=n;i++ 
)
         if (visited[i]==0) { printf 
("\n第%d个连通分量:\n",++k); dfs(i);}//if      }//Count
算法中visited[]数组是全程变量，每个连通分量的顶点集按遍历顺序输出。这里设顶点信息就是顶点编号，否则应取其g[i].vertex分量输出。

发表于 2017-05-12 23:45:35 回复(0)