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

数据结构 图基本操作代码实验五 图 /图的邻接矩阵存储 #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;k<G.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;i<G.vexnum;i+) G.vexsi=i+1; for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) G.arcsij.adj=0; for(k=0;k<G.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;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) printf("%d ",G.arcsij.adj); printf("n"); void main MGraph G; Create(G); display(G); /图的邻接表存储及深度广度遍历 #include "stdio.h" #include "stdlib.h" typedef 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;k<G.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;i<G.vexnum;i+) /建立顶点表 getchar; printf("请输入第%d顶点信息：",i+1); scanf("%c",&G.adjlisti.vertex); /读入顶点信息 G.adjlisti.firstarc=NULL;/边表置为空表 for(k=0;k<G.arcnum;k+) /建立边表 getchar; printf("请输入第%d边的顶点对序号和边的权值(v1，v2，w)：",k+1); scanf("%c,%c,%d",&v1,&v2,&w);/读入边(vi，vj)的顶点对序号 j=LocateVex(G,v2); i=LocateVex(G,v1); s=(ArcNode *)malloc(sizeof(ArcNode); /生成边表结点 s->adjvex=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;v<G.vexnum;v+) visitedv=false; for(v=0;v<G.vexnum;v+) if(!visitedv) DFS(G,v); /队列 typedef struct QNode int data; struct QNode *next; QNode,*QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue; void InitQueue(LinkQueue &Q) /构造一个空队列 Q Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode); Q.front->next=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;v<G.vexnum;v+) visited1v=false; LinkQueue Q; InitQueue(Q); for(v=0;v<G.vexnum;v+) if(!visited1v) visited1v=true; printf("%c ",G.adjlistv.vertex); EnQueue(Q,v); int u; ArcNode *w; while(Q.front!=Q.rear) DeQueue(Q,u); for(w=G.adjlistu.firstarc;w!=NULL;w=w->nextarc) 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; for(i=0;i<G.vexnum;i+) if(G.adjlisti.firstarc!=NULL) printf("%c->",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"); */