图的遍历(邻接表结构).doc

#include #include using namespace std; #define int_max 10000 #define inf 9999 #define max 20 /邻接矩阵定义 typedef struct ArcCell int adj; / char *info; ArcCell,AdjMatrix2020; typedef struct char vexs20; AdjMatrix arcs; int vexnum,arcnum; MGraph_L; / int localvex(MGraph_L G,char v)/返回V的位置 int i=0; while(G.vexsi!=v) +i; return i; int creatMGraph_L(MGraph_L &G)/创建图用邻接矩阵表示 char v1,v2; int i,j,w; cout创建无向图endl请输入图G顶点和弧的个数:(4 6)不包括“()”G.vexnumG.arcnum; for(i=0;i!=G.vexnum;+i) cout输入顶点iG.vexsi; for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) G.arcsij.adj=0; /G.=NULL; for(int k=0;k!=G.arcnum;+k) cout输入一条边依附的顶点和权:(a b 3)不包括“()”v1v2w;/输入一条边依附的两点及权值 i=localvex(G,v1);/确定顶点V1和V2在图中的位置 j=localvex(G,v2); G.arcsij.adj=1；/G.arcsij.adj=w; G.arcsji.adj=1；/G.arcsji.adj=w; return G.vexnum; void ljjzprint(MGraph_L G)/输出图的邻接矩阵 int i,j; for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) coutG.arcsij.adj ; coutadjvex=j; gra.verticesi.firstarc=arc; arc-nextarc=NULL; p=arc; +j; while(G.arcsij.adj!=int_max&j!=G.vexnum) tem=(arcnode *)malloc(sizeof(arcnode); tem-adjvex=j; gra.verticesi.firstarc=tem; tem-nextarc=arc; arc=tem; +j; -j; else if(G.arcsij.adj!=int_max&j!=G.vexnum) arc=(arcnode *)malloc(sizeof(arcnode); arc-adjvex=j; p-nextarc=arc; arc-nextarc=NULL; p=arc; gra.vexnum=G.vexnum; gra.arcnum=G.arcnum; /*for(i=0;i!=gra.vexnum;+i) arcnode *p; couti ; p=gra.verticesi.firstarc; while(p!=NULL) coutadjvex; p=p-nextarc; coutendl; */ cout图G邻接表创建成功！endl; return 1; void adjprint(algraph gra) 输出图的邻接矩阵 int i; for(i=0;i!=gra.vexnum;+i) arcnode *p; couti ; p=gra.verticesi.firstarc; while(p!=NULL) coutadjvex; p=p-nextarc; coutadjvex; int nextadjvex(algraph gra,vnode v,int w)/返回依附顶点V相对于W的下一个顶点 arcnode *p; p=v.firstarc; while(p!=NULL&p-adjvex!=w) p=p-nextarc; if(p-adjvex=w&p-nextarc!=NULL) p=p-nextarc; return p-adjvex; if(p-adjvex=w&p-nextarc=NULL) return -10; int initqueue(linkqueue &q)/初始化队列 q.rear=(queueptr)malloc(sizeof(qnode); q.front=q.rear; if(!q.front) return 0; q.front-next=NULL; return 1; int enqueue(linkqueue &q,int e)/入队 queueptr p; p=(queueptr)malloc(sizeof(qnode); if(!p) return 0; p-data=e; p-next=NULL; q.rear-next=p; q.rear=p; return 1; int dequeue(linkqueue &q,int &e)/出队 queueptr p; if(q.front=q.rear) return 0; p=q.front-next; e=p-data; q.front-next=p-next; if(q.rear=p) q.rear=q.front; free(p); return 1; int queueempty(linkqueue q)/判断队为空 if(q.front=q.rear) return 1; return 0; void bfstra(algraph gra)/广度优先遍历 int i,e; linkqueue q; for(i=0;i!=gra.vexnum;+i) visitedi=0; initqueue(q); for(i=0;i!=gra.vexnum;+i) if(!visitedi) visitedi=1; coutgra.verticesi.data; enqueue(q,i); while(!queueempty(q) dequeue(q,e); / cout e=0;we=nextadjvex(gra,gra.verticese,we) if(!visitedwe) visitedwe=1; coutgra.verticeswe.data; enqueue(q,we); int dfs(algraph gra,int i);/深度优先遍历 int dfstra(algraph gra) int i,j; for(i=0;i!=gra.vexnum;+i) visitedi=0; for(j=0;j!=gra.vexnum;+j) if(visitedj=0) dfs(gra,j); return 0; int dfs(algraph gra,int i) visitedi=1; int we1; cout=0;we=nextadjvex(gra,gra.verticesi,we) we1=we; if(visitedwe=0) dfs(gra,we); we=we1; return 12; void main() algraph gra; MGraph_L G; int i,d,g2020; char a=a; d=creatMGraph_L(G); creatadj(gra,G); vnode v; cout菜单endlendl; cout1、广度优先遍历endl; cout2、深度优先遍历endl; int s; char y=y; while(y=y) cout请选择菜单：s; switc