数据结构图基本操作代码

1、实验五图/图的邻接矩阵存储#includestdio.h#includestdlib.htypedefstructintadj;AdjMatrix1010;typedefstructintvexs10;AdjMatrixarcs;intvexnum,arcnum;MGraph;intLocateVex(MGraph&G,intv)intk,j=0;for(k=0;kG.vexnum;k+)if(G.vexsk=v)j=k;break;returnj;voidCreate(MGraph&G)inti,j,k;intv1=0,v2=0,w=0;printf(请输入图的顶点数:)；scanf(%d,

2、&G.vexnum);printf(请输入图的边数:);scanf(%d,&G.arcnum);printf(请输入图的顶点:);for(i=0;iG.vexnum;i+)G.vexsi=i+1;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)G.arcsij.adj=0;for(k=0;kG.arcnum;k+)printf(请输入一条边依附的顶点v1,v2及权值(v1,v2,w):);scanf(%d,%d,%d,&v1,&v2,&w);i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcsij.adj=w;/G.arcsj

3、i.adj=G.arcsij.adj;voiddisplay(MGraph&G)inti,j;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)printf(%d,G.arcsij.adj);printf(n);voidmain()MGraphG;Create(G);display(G);/图的邻接表存储及深度广度遍历#includestdio.h#includestdlib.htypedefstructArcNodeintadjvex;structArcNode*nextarc;intweight;ArcNode;typedefstructVNodechar

4、vertex;/顶点域ArcNode*firstarc;VNode,AdjList10;typedefstructAdjListadjlist;intvexnum,arcnum;ALGraph;intLocateVex(ALGraph&G,charv)intk,j=0;for(k=0;kG.vexnum;k+)if(G.adjlistk.vertex=v)j=k;break;returnj;voidCreateALGraph(ALGraph&G)/建立无向图的邻接表表示inti,j,k,w;charv1,v2;ArcNode*s;printf(请输入顶点数和边数(vexnum,arcnum):

5、);scanf(%d,%d,&G.vexnum,&G.arcnum);/读人顶点数和边数for(i=0;iG.vexnum;i+)/建立顶点表getchar();printf(”请输入第小顶点信息：,i+l);scanf(%c,&G.adjlisti.vertex);/读入顶点信息G.adjlisti.firstarc=NULL;边表置为空表for(k=0;kadjvex=j;/邻接点序号为js-weight=w;s-nextarc=G.adjlisti.firstarc;G.adjlisti.firstarc=s;将新结点*s插入顶点vi的边表头部/若图为无向图则加上下面的四句代码，若图为有

6、向图则注释下面的四句代码s=(ArcNode*)malloc(sizeof(ArcNode);s-adjvex=i;邻接点序号为is-weight=w;s-nextarc=G.adjlistj.firstarc;G.adjlistj.firstarc=s;将新结点*s插入顶点vj的边表头部/endforboolvisited20;intv;voidDFS(ALGraph&G,intv)visitedv=true;printf(%c,G.adjlistv.vertex);ArcNode*w;for(w=G.adjlistv.firstarc;w!=NULL;w=w-nextarc)if(!vis

7、itedw-adjvex)DFS(G,w-adjvex);voidDFSTraverse(ALGraph&G)/图的深度遍历操作for(v=0;vG.vexnum;v+)visitedv=false;for(v=0;vnext=NULL;voidEnQueue(LinkQueue&Q,inte)/进队列QNode*p;p=(QueuePtr)malloc(sizeof(QNode);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;voidDeQueue(LinkQueue&Q,int&e2)/出队列QNode*p;p=Q.front-next;e2=p-

8、data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);boolvisited120;voidBFSTraverse(ALGraph&G)for(v=0;vG.vexnum;v+)visited1v=false;LinkQueueQ;InitQueue(Q);for(v=0;vnextarc)if(!visited1w-adjvex)visited1w-adjvex=true;printf(%c,G.adjlistw-adjvex.vertex);EnQueue(Q,w-adjvex);/if/while/if/BFSTraversevoiddisplay(ALGraph&G)输出图的顶点信息printf(建立的邻接表位：n);inti;for(i=0;i,G.adjlisti.vertex);ArcNode*p;p=G.adjlisti.firstarc;while(p!=NULL)printf(%d-,p-adjvex);p=p-nextarc;printf(NULLn);elseprintf(%c-NULLn,G.adjlisti.vertex);voidmain()ALGraphG;C