搜索
#includestdio.h#includemalloc.h#defineMAXV30typedefintInfoType;typedefstruct{intno;InfoTypeinfo;}VertexType;typedefstruct{VertexTypevexs[MAXV];intarcs[MAXV][MAXV];intvexnum,arcnum;}MGraph;typedefstructArcNode{intadjvex;intweight;structArcNode*nextarc;}ArcNode;typedefstructVNode{VertexTypedata;ArcNode*firstarc;}VNode;//typedefVNodeAdjList[MAXV];typedefstruct{VNodevertices[MAXV];intvexnum,arcnum;}LGraph;intvisited[MAXV];intqueue[MAXV];voidCreateMG(MGraph&mg){inti,j;intA[7][7];mg.vexnum=7;mg.arcnum=9;for(i=0;img.vexnum;i++)for(j=0;jmg.vexnum;j++)A[i][j]=0;A[0][1]=A[0][2]=A[0][6]=1;A[1][3]=1;A[2][3]=A[2][5]=A[2][6]=1;A[3][4]=1;A[5][6]=1;for(i=1;img.vexnum;i++)for(j=0;ji;j++)A[i][j]=A[j][i];for(i=0;img.vexnum;i++)for(j=0;jmg.vexnum;j++)mg.arcs[i][j]=A[i][j];}voidCreatLG(LGraph*&lg,MGraphmg){inti,j;ArcNode*p;lg=(LGraph*)malloc(sizeof(LGraph));for(i=0;img.vexnum;i++)lg-vertices[i].firstarc=NULL;for(i=0;img.vexnum;i++)for(j=mg.vexnum-1;j=0;j--)if(mg.arcs[i][j]!=0){p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-weight=mg.arcs[i][j];p-nextarc=lg-vertices[i].firstarc;lg-vertices[i].firstarc=p;}lg-vexnum=mg.vexnum;lg-arcnum=mg.arcnum;}voidOutputMG(MGraphmg){inti,j;for(i=0;img.vexnum;i++){for(j=0;jmg.vexnum;j++)printf(%3d,mg.arcs[i][j]);printf(\n);}}voidOutputLG(LGraph*lg){inti;ArcNode*p;for(i=0;ilg-vexnum;i++){p=lg-vertices[i].firstarc;if(p)printf(%3d:,i);while(p){printf(%3d,p-adjvex);p=p-nextarc;}printf(\n);}}voidLDFS(LGraph*lg,inti){ArcNode*p;printf(%3d,i);visited[i]=1;p=lg-vertices[i].firstarc;while(p){if(!visited[p-adjvex])LDFS(lg,p-adjvex);p=p-nextarc;}}voidMDFS(MGraphmg,inti){intj;printf(%3d,i);visited[i]=1;for(j=0;jmg.vexnum;j++){if(mg.arcs[i][j]!=0&&visited[j]==0)MDFS(mg,j);}}voidLBFS(LGraph*lg,ints){inti,v,w,front,rear;ArcNode*p;for(i=0;ilg-vexnum;i++)visited[i]=0;front=rear=0;printf(%3d,s);visited[s]=1;queue[rear++]=s;while(frontrear){v=queue[front++];for(p=lg-vertices[v].firstarc;p!=NULL;p=p-nextarc){w=p-adjvex;if(visited[w]==0){printf(%3d,w);visited[w]=1;queue[rear++]=w;}}}}voidMBFS(MGraphmg,ints){inti,j,v,front,rear;for(i=0;img.vexnum;i++)visited[i]=0;front=rear=0;printf(%3d,s);visited[s]=1;queue[rear++]=s;while(frontrear){v=queue[front++];for(i=0;img.vexnum;i++)for(j=0;jmg.vexnum;j++){if(mg.arcs[i][j]!=0&&visited[j]==0){printf(%3d,j);visited[j]=1;queue[rear++]=j;}}}}voidmain(){LGraph*lg;MGraphmg;inti;CreateMG(mg);CreatLG(lg,mg);printf((1)当前图的邻接矩阵是:\n);OutputMG(mg);printf((2)当前图的邻接表是:\n);OutputLG(lg);for(i=0;img.vexnum;i++)visited[i]=0;getchar();printf((3)邻接表表示的图的深度优先遍历序列是:);LDFS(lg,0);getchar();for(i=0;img.vexnum;i++)visited[i]=0;printf((4)邻接矩阵表示的图的深度优先遍历序列是:);MDFS(mg,0);getchar();printf((5)邻接表表示的图的广度优先遍历序列是:);LBFS(lg,0);getchar();printf((6)邻接矩阵表示的图的广度优先遍历序列是:);MBFS(mg,0);printf(\n);}