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

数据结构实验题目：实现教材P215例8.3的完整算法（判断无向图是否联通）源码：#include malloc.h#include #include #define MAXV 6#define InfoType int#define Vertex inttypedef structint no;InfoType info; VertexType;typedef structint edgeMAXVMAXV;int n,e;VertexType vexsMAXV;MGraph;typedef struct ANodeint adjvex;struct ANode *nextarc;InfoType info;ArcNode;typedef struct VNodeVertex data;ANode *firstarc;VNode;typedef VNode AdjListMAXV;typedef structAdjList adjlist;int n,e;ALGraph;int visitedMAXV=0,0,0,0,0,0;void ListToMat(MGraph g,ALGraph * &G)int i,j;ArcNode *p;for(i=0;in;i+)for(j=0;jn;j+)g.edgeij=0;for(i=0;iadjlisti.firstarc;while(p!=NULL)g.edgeip-adjvex=1;p=p-nextarc;g.n=G-n;g.e=G-e;void BFS(ALGraph *G,int v)ArcNode *p;int i,j;visitedv=1;printf(%d,v);p=G-adjlistv.firstarc;while(p!=NULL) printf(%d,p-adjvex);if(visitedp-adjvex!=1)BFS(G,p-adjvex);p=p-nextarc;void BFSbook(ALGraph *G,int v)ArcNode *p;int queueMAXV,front=0,rear=0; int w ,i;printf(%2d,v);visitedv=1;rear=(rear+1)%MAXV;queuerear=v;while(front!=rear)front=(front+1)%MAXV;w=queuefront;p=G-adjlistw.firstarc;while(p!=NULL)if(visitedp-adjvex=0)printf(%2d,p-adjvex);visitedp-adjvex=1;rear=(rear+1)%MAXV;queuerear=p-adjvex;p=p-nextarc;printf(n);void DFS(ALGraph *G,int v)coutDFSnadjlistv.firstarc;visitedv=1;printf(=%d= n,v);while(p!=NULL) printf(|%d| n,p-adjvex);if(visitedp-adjvex=0)DFS(G,p-adjvex);p=p-nextarc; bool connect(ALGraph * G)int i;bool flag=true;for(i=0;in;i+)visitedi=0;BFSbook(G,3); coutDispVisitedendl;for(i=0;in;i+)coutvisitediendl;for(i=0;in;i+)coutntiendl;if(visitedi=0)flag=false;break;coutnnendl;return flag;void MatToList(MGraph g,ALGraph * &G) int i,j,k=0,flag=1;ArcNode * p;G=(ALGraph *)malloc(sizeof(ALGraph);for(i=0;iadjlisti.firstarc=NULL;for(i=0;i=0;j-)if(g.edgeij=1)p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=j;p-nextarc=G-adjlisti.firstarc;G-adjlisti.firstarc=p; G-n=g.n; G-e=g.e;void DispGraph(ALGraph * &G,int num)int i;ArcNode *p;for(i=0;i,i);p=G-adjlisti.firstarc;while(p!=NULL)printf(%d-,p-adjvex);p=p-nextarc;printf(n);void DispMat(MGraph g)int i,j;for(i=0;ig.n;i+)for(j=0;jg.n;j+)printf(%dt,g.edgeij);printf(n);MGraph DataToMat(MGraph mgraph,int dataMAXVMAXV)int i,j;for(i=0;iMAXV;i+)for(j=0;jMAXV;j+)mgraph.edgeij=dataij;mgraph.n=MAXV;mgraph.e=14;return mgraph;int main()/矩阵图数据源int dataMAXVMAXV=0,1,0,1,0,1,1,0,1,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,0;ALGraph * algraph;MGraph mgraph;mgraph=DataToMat(mgraph,data);DispMat(mgraph);MatToList(mgraph,algraph);DispGraph(algraph,MAXV);cout是否连通：(connect