设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。

admin2013-12-31  30

问题 设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。

选项

答案解法一:采用深度优先遍历方法。算法如下: #define MAX_VERTEX_NUM 20 //最大顶点数为20 typedef struct ArcNode{ //边表结点 int adjvex; //邻接点域 struct ArcNode*nextarc; //指向下一个邻接点的指针域 //若要表示边上信息,则应增加一个数据域info }ArcNode; typedef struct VNode{ //顶点表结点 VertexType data; //顶点域 ArcNode *firstarc; //边表头指针 }VNode,AdjList[MAX_VERTEX_NUM]; //AdjList是邻接表类型 typedef struct{ AdjList adjlist; //邻接表 int vexnum,arcnum; //顶点数和边数 }ALGraph; //ALGraph是以邻接表方式存储的图类型 void DFS(ALGraph G,int V){ 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的下一条边的终结点 } } int ConnNum1(ALGraph G){ //求图G的连通分量 int i,num=0; for(i=0;i<G->n;i++) visited[i]=0; for(i=0;i<G->n;i++) if(visited[i]==0){ DFS(G,i); //调用DFS算法 num++: } return(num); } 解法二:采用广度优先遍历方法。算法如下: void BFS(ALGraph G,int v){ ArcNode*p; int Qu[MAX_VERTEX_NUM],front=0,rear=0; //定义循环队列并初始化 int W,i; for(i:0;i<G->n;i++)visited[i]=0; //访问标志数组初始化 prinf("2%d",v); //输出被访问顶点的编号 visited[v]=1; //置已访问标记 rear=(rear+1)%MAX_VERTEX_NUM; Qu[rear]=v: //v入队 while(front!=rear){ //若队列不空时循环 front=(front+1)%MAX_VERTEX_NUM; w=Qu[front]; //出队并赋予W p=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! //该顶点人队 Qu[rear]=p->adjvex; } p=p->nextarc; //找下一个邻接顶点 } } printf("\n"); } int ConnNum2(ALGraph G){ //求图G的连通分量 int i,num=0; for(i=0;i<G->n;i++) visited[i]=0; for(i=0;i<G->n;i++) if(visited[i]==0){ BFS(G,i); //调用BFS算法 num++: } return(num); }

解析
转载请注明原文地址:https://kaotiyun.com/show/5vxi777K
0

最新回复(0)