利用邻接表存储无向图,并深度遍历与广度遍历图.doc

利用邻接表存储无向图,并深度遍历和广度遍历图 #include stdio.h#include iostream.h#include malloc.h#define max 20 int visited[max];int w;typedef struct arcnode{?int adjvex;//该弧指向的顶点的位置?struct arcnode *nextarc;//弧尾相同的下一条弧?char *info;//该弧信息}arcnode;typedef struct vnode{?char data;//结点信息?arcnode *firstarc;//指想第一条依附该结点的弧的指针}vnode,adjlist;typedef struct{?adjlist vertices[max];?int vexnum,arcnum;?int kind;}algraph; typedef struct qnode{?int data;?struct qnode *next; }qnode,*queueptr; typedef struct{?queueptr front;?queueptr rear; }linkqueue; void dfs(algraph gra,int i); int creatadj(algraph gra)//用邻接表存储图{?int i,n,m;?char cha;?cout输如结点个数：;?cinn;?cout输如弧个数：;?cinm;?arcnode *arc,*tem;?for(i=0;in;i++)?{??cout输如结点信息：;??cingra.vertices[i].data;??gra.vertices[i].firstarc=NULL;?}?for(i=0;in;i++)?{???cout结点i是否有出度：;???cincha;???if(cha==y)????{?????arc=(arcnode *)malloc(sizeof(arcnode));????cinarc-adjvex;????????gra.vertices[i].firstarc=arc;????cout是否还有出度：;????cincha;????while(cha==y)????{????tem=(arcnode *)malloc(sizeof(arcnode));????cintem-adjvex;????????arc-nextarc=tem;????arc=tem;????cout是否还有出度：;????cincha;????}????arc-nextarc=NULL;????}???if(cha==n)????continue;?}?gra.vexnum=n;?gra.arcnum=m;?return 1;}int firstadjvex(algraph gra,vnode v)//返回依附顶点V的第一个点?????????//即以V为尾的第一个结点{?return v.firstarc-adjvex; }int nextadjvex(algraph gra,vnode v,int w)//返回依附顶点V的相对于W的下一个顶点{?arcnode *p;?p=v.firstarc;?while(p!=NULL)?{??if(p-adjvex!=w)???p=p-nextarc;??if(p-adjvex==wp-nextarc!=NULL)???return p-nextarc-adjvex;??else return 0;?}}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.