数据结构 图基本操作代码.doc

实验五 图/图的邻接矩阵存储#include stdio.h#include stdlib.htypedef structint adj;AdjMatrix1010;typedef struct int vexs10;AdjMatrix arcs;int vexnum,arcnum;MGraph;int LocateVex(MGraph &G,int v)int k,j=0;for(k=0;kG.vexnum;k+)if(G.vexsk=v)j=k;break;return j;void Create(MGraph &G)int i,j,k;int v1=0,v2=0,w=0;printf(请输入图的顶点数:);scanf(%d,&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.arcsji.adj=G.arcsij.adj;void display(MGraph &G)int i,j;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)printf(%d ,G.arcsij.adj);printf(n);void main()MGraph G;Create(G);display(G);/图的邻接表存储及深度广度遍历#include stdio.h#include stdlib.htypedef struct ArcNodeint adjvex;struct ArcNode *nextarc;int weight;ArcNode;typedef struct VNodechar vertex; /顶点域 ArcNode *firstarc;VNode,AdjList10;typedef structAdjList adjlist;int vexnum,arcnum;ALGraph;int LocateVex(ALGraph &G,char v)int k,j=0; for(k=0;kG.vexnum;k+)if(G.adjlistk.vertex=v)j=k;break;return j;void CreateALGraph(ALGraph &G) /建立无向图的邻接表表示 int i,j,k,w; char v1,v2;ArcNode *s; printf(请输入顶点数和边数(vexnum,arcnum):);scanf( %d,%d,&G.vexnum,&G.arcnum); /读人顶点数和边数 for(i=0;iG.vexnum;i+)/建立顶点表 getchar();printf(请输入第%d顶点信息：,i+1);scanf(%c,&G.adjlisti.vertex); /读入顶点信息 G.adjlisti.firstarc=NULL;/边表置为空表 for(k=0;kadjvex=j; /邻接点序号为j s-weight=w; s-nextarc=G.adjlisti.firstarc; G.adjlisti.firstarc=s; /将新结点*s插入顶点vi的边表头部 /若图为无向图则加上下面的四句代码，若图为有向图则注释下面的四句代码s=(ArcNode *)malloc(sizeof(ArcNode); s-adjvex=i; /邻接点序号为i s-weight=w; s-nextarc=G.adjlistj.firstarc; G.adjlistj.firstarc=s; /将新结点*s插入顶点vj的边表头部 /end for bool visited20;int v;void DFS(ALGraph &G,int v)visitedv=true;printf(%c ,G.adjlistv.vertex); ArcNode *w;for(w=G.adjlistv.firstarc;w!=NULL;w=w-nextarc)if(!visitedw-adjvex)DFS(G,w-adjvex);void DFSTraverse(ALGraph &G) /图的深度遍历操作for(v=0;vG.vexnum;v+)visitedv=false;for(v=0;vnext=NULL;void EnQueue(LinkQueue &Q,int e) /进队列QNode *p;p=(QueuePtr)malloc(sizeof(QNode);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;void DeQueue(LinkQueue &Q,int &e2) /出队列QNode *p;p=Q.front-next;e2=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);bool visited120;void BFSTraverse(ALGraph &G)for(v=0;vG.vexnum;v+)visited1v=false;LinkQueue Q;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/BFSTraversevoid display(ALGraph &G)/输出图的顶点信息printf(建立的邻接表位：n);int i;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);void main()ALGrap