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

《数据结构 图基本操作代码.docx》由会员分享，可在线阅读，更多相关《数据结构 图基本操作代码.docx（6页珍藏版）》请在三一办公上搜索。

1、数据结构 图基本操作代码实验五 图 /图的邻接矩阵存储 #include stdio.h #include stdlib.h typedef struct int 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

2、,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,&v

3、2,&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.h typ

4、edef struct ArcNode int adjvex; struct ArcNode *nextarc; int weight; ArcNode; typedef struct VNode char vertex; /顶点域 ArcNode *firstarc; VNode,AdjList10; typedef struct AdjList 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=

5、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.fi

6、rstarc=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插

7、入顶点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;vn

8、ext=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 BF

9、STraverse(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 /BFSTraverse void display(ALGraph &G)/输出图的顶点信息 printf(建立的邻接表位：n); int i; fo

10、r(i=0;i,G.adjlisti.vertex); ArcNode *p; p=G.adjlisti.firstarc; while(p!=NULL) printf(%d-,p-adjvex); p=p-nextarc; printf(NULLn); else printf(%c-NULLn,G.adjlisti.vertex); void main ALGraph G; CreateALGraph(G); display(G); /* printf(nn); printf(图的深度遍历为：n); DFSTraverse(G); printf(n); printf(nn); printf(图的广度遍历为：); BFSTraverse(G); printf(n); */