解法一：采用深度优先遍历方法。算法如下：#defineMAX_VERTEX_NUM20／／最大顶点数为20typedefstructArcNode{／／边表结点intadjvex；／／邻接点域structArcNode*nextarc；／／指向下一个邻接点的指针域／／若要表示边上信息则应增加一个数据域info}ArcNode；typedefstructVNode{／／顶点表结点VertexTypedata；／／顶点域ArcNode*firstarc；／／边表头指针}VNodeAdjList[MAX_VERTEX_NUM3；／／AdjList是邻接表类型typedefstruct{AdjListadjlist；／／邻接表intvexnumarcnum；／／顶点数和边数}ALGraph；／／ALGraph是以邻接表方式存储的图类型voidDFS(ALGraphGintv){ArcNode*P：visited[v]=1；／／置已访问标记prinf(”％d”v)；／／输出被访问顶点的编号P=G－>adjlist[v]．firstarc；／／p指向顶点v的第一条边的终结点while(p!=NULL){if(visited[p一>adjvex]==0)／／若p一>adjvex顶点未访问递归访问它DFS(GP一>adjvex)；p=p－>nextarc；／／p指向顶点v的下一条边的终结点}}intConnNuml(ALGraphG){／／求图G的连通分量intinum=0；for(i=0；in；i++)visited[i]=0；for(i=0；in；i++)if(visited[i]==0){DFS(Gi)；／／调用DFS算法num++；}return(num)；}解法二：采用广度优先遍历方法。算法如下：voidBFS(ALGraphGintv){ArcNode*p；intQu[MAXVERTEX_NUM]front=0rear=0；／／定义循环队列并初始化intwi；for(i=0；in；i++)visited[i]=0；／／访问标志数组初始化prinf(”2％d”v)；／／输出被访问顶点的编号visited[v]=1；／／置已访问标记rear=(rear+1)％MAx_VERTEXNUM；Qu[rear]=v；／／v入队while(front!=rear){／／若队列不空时循环front=(front+1)％MAX_VERTEX_NUM；w=Qu[front]；／／出队并赋予wP=G一>adjlist[w]．firstarc；／／找与顶点W邻接的第一个顶点while(p!=NULL){if(visited[p一>adjvex]：=0){／／若当前邻接顶点未被访问printf(”％2d”P一>adjvex)；／／访问相邻顶点visited[p一>adjvex]=1；／／置该顶点已被访问的标志rear=(rear+1)％MAx_VERTEX_NUM；／／该顶点入队Qurear]=P－>adjvex；}p=p->nextarc；／／找下一个邻接顶点}}printf(”＼n”)；}intConnNum2(ALGraphG){／／求图G的连通分量intinum=0；for(i=0；in；i++)visited[i]=0；for(i=0；in；i++)if(visited[i]==0){BFS(Gi)；／／调用BFS算法num++：}return(num)；}解法一：采用深度优先遍历方法。算法如下：#defineMAX_VERTEX_NUM20／／最大顶点数为20typedefstructArcNode{／／边表结点intadjvex；／／邻接点域structArcNode*nextarc；／／指向下一个邻接点的指针域／／若要表示边上信息，则应增加一个数据域info}ArcNode；typedefstructVNode{／／顶点表结点VertexTypedata；／／顶点域ArcNode*firstarc；／／边表头指针}VNode，AdjList[MAX_VERTEX_NUM3；／／AdjList是邻接表类型typedefstruct{AdjListadjlist；／／邻接表intvexnum，arcnum；／／顶点数和边数}ALGraph；／／ALGraph是以邻接表方式存储的图类型voidDFS(ALGraphG，intv){ArcNode*P：visited[v]=1；／／置已访问标记prinf(”％d”，v)；／／输出被访问顶点的编号P=G－>adjlist[v]．firstarc；／／p指向顶点v的第一条边的终结点while(p!=NULL){if(visited[p一>adjvex]==0)／／若p一>adjvex顶点未访问，递归访问它DFS(G，P一>adjvex)；p=p－>nextarc；／／p指向顶点v的下一条边的终结点}}intConnNuml(ALGraphG){／／求图G的连通分量inti，num=0；for(i=0；in；i++)visited[i]=0；for(i=0；in；i++)if(visited[i]==0){DFS(G，i)；／／调用DFS算法num++；}return(num)；}解法二：采用广度优先遍历方法。算法如下：voidBFS(ALGraphG，intv){ArcNode*p；intQu[MAXVERTEX_NUM]，front=0，rear=0；／／定义循环队列并初始化intw，i；for(i=0；in；i++)visited[i]=0；／／访问标志数组初始化prinf(”2％d”，v)；／／输出被访问顶点的编号visited[v]=1；／／置已访问标记rear=(rear+1)％MAx_VERTEXNUM；Qu[rear]=v；／／v入队while(front!=rear){／／若队列不空时循环front=(front+1)％MAX_VERTEX_NUM；w=Qu[front]；／／出队并赋予wP=G一>adjlist[w]．firstarc；／／找与顶点W邻接的第一个顶点while(p!=NULL){if(visited[p一>adjvex]：=0){／／若当前邻接顶点未被访问printf(”％2d”，P一>adjvex)；／／访问相邻顶点visited[p一>adjvex]=1；／／置该顶点已被访问的标志rear=(rear+1)％MAx_VERTEX_NUM；／／该顶点入队Qurear]=P－>adjvex；}p=p->nextarc；／／找下一个邻接顶点}}printf(”＼n”)；}intConnNum2(ALGraphG){／／求图G的连通分量inti，num=0；for(i=0；in；i++)visited[i]=0；for(i=0；in；i++)if(visited[i]==0){BFS(G，i)；／／调用BFS算法num++：}return(num)；}解析：本题主要考查图的遍历的应用。对于无向图来说，深度优先遍历或者是广度优先遍历，若无向图是连通图，则一次遍历能够访问到图中的所有顶点，但若无向图是非连通图，则只能访问到初始点所在连通分量中的所有顶点，其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点，分别进行遍历，才能够访问到图中的所有顶点。因为在选择初始点的同时加上计数器，最后计数器的值即为连通分量个数。[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]