数据结构实验-图的基本操作.doc

《数据结构实验-图的基本操作.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、#include#include#defineMAXV30typedefintInfoType;typedefstruct{intno;InfoTypeinfo;}VertexType;typedefstruct{VertexTypevexs[MAXV];intarcs[MAXV][MAXV];intvexnum,arcnum;}MGraph;typedefstructArcNode{intadjvex;intweight;structArcNode*nextarc;}ArcNode;typedefstr

2、uctVNode{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;i

3、um;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;i

4、p;lg=(LGraph*)malloc(sizeof(LGraph));for(i=0;ivertices[i].firstarc=NULL;for(i=0;i=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-

5、>vertices[i].firstarc=p;}lg->vexnum=mg.vexnum;lg->arcnum=mg.arcnum;}voidOutputMG(MGraphmg){inti,j;for(i=0;ivexnum;i++){p=lg->vertices[i].f

6、irstarc;if(p)printf("%3d:",i);while(p){printf("%3d",p->adjvex);p=p->nextarc;}printf("");}}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){i

7、ntj;printf("%3d",i);visited[i]=1;for(j=0;jvexnum;i++)visited[i]=0;front=rear=0;printf("%3d",s);visited[s]=1;queue[rear++]=s;while(front

8、{v=queue[front++];for(p=lg->vertices[v].firstarc;p!=NULL;p=p->nextarc){w=p->adjvex