数据结构判断无向图是否连通

《数据结构判断无向图是否连通》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构实验题目：实现教材P215例8.3的完整算法（判断无向图是否联通）源码：#include"malloc.h"#include#include#defineMAXV6#defineInfoTypeint#defineVertexinttypedefstruct{intno;InfoTypeinfo;}VertexType;typedefstruct{intedge[MAXV][MAXV];intn,e;VertexTypevexs[MAXV];}MGraph;typedefstructANode{intadj

2、vex;structANode*nextarc;InfoTypeinfo;}ArcNode;typedefstructVNode{Vertexdata;ANode*firstarc;}VNode;typedefVNodeAdjList[MAXV];typedefstruct{AdjListadjlist;intn,e;}ALGraph;intvisited[MAXV]={0,0,0,0,0,0};voidListToMat(MGraphg,ALGraph*&G){inti,j;ArcNode*p;for(i=0;in;i++){for(j=0;j<

3、G->n;j++){g.edge[i][j]=0;}}for(i=0;iadjlist[i].firstarc;while(p!=NULL){g.edge[i][p->adjvex]=1;p=p->nextarc;}}g.n=G->n;g.e=G->e;}voidBFS(ALGraph*G,intv){ArcNode*p;inti,j;visited[v]=1;printf("%d",v);p=G->adjlist[v].firstarc;while(p!=NULL){printf("%d",p->adjvex);if(vis

4、ited[p->adjvex]!=1){BFS(G,p->adjvex);}p=p->nextarc;}}voidBFSbook(ALGraph*G,intv){ArcNode*p;intqueue[MAXV],front=0,rear=0;intw,i;printf("%2d",v);visited[v]=1;rear=(rear+1)%MAXV;queue[rear]=v;while(front!=rear){front=(front+1)%MAXV;w=queue[front];p=G->adjlist[w].firstarc;while(p!=NU

5、LL){if(visited[p->adjvex]==0){printf("%2d",p->adjvex);visited[p->adjvex]=1;rear=(rear+1)%MAXV;queue[rear]=p->adjvex;}p=p->nextarc;}}printf("");}voidDFS(ALGraph*G,intv){cout<<"DFS"<adjlist[v].firstarc;visited[v]=1;printf(

6、"=%d=",v);while(p!=NULL){printf("

7、

8、%d

9、

10、",p->adjvex);if(visited[p->adjvex]==0)DFS(G,p->adjvex);p=p->nextarc;}}boolconnect(ALGraph*G){inti;boolflag=true;for(i=0;in;i++){visited[i]=0;}BFSbook(G,3);cout<<"DispVisited"<n;i++)cout<

11、->n;i++){cout<n<<"t"<adjlist[i].firstarc=NULL;for(i=0;i=

12、0;j--){if(g.edge[i][j]==1){p=(Arc