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

《利用邻接表存储无向图,并深度遍历和广度遍历图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、利用邻接表存储无向图,并深度遍历和广度遍历图#include#include#include#definemax20intvisited[max];intw;typedefstructarcnode{ intadjvex;//该弧指向的顶点的位置 structarcnode*nextarc;//弧尾相同的下一条弧 char*info;//该弧信息}arcnode;typedefstructvnode{ chardata;//结点信息 arcnode*firs

2、tarc;//指想第一条依附该结点的弧的指针}vnode,adjlist;typedefstruct{ adjlistvertices[max]; intvexnum,arcnum; intkind;}algraph;typedefstructqnode{ intdata; structqnode*next;}qnode,*queueptr;typedefstruct{ queueptrfront; queueptrrear;}linkqueue;voiddfs(algraphgra,inti);intcreatadj

3、(algraph&gra)//用邻接表存储图{ inti,n,m; charcha; cout<<"输如结点个数："; cin>>n; cout<<"输如弧个数："; cin>>m; arcnode*arc,*tem; for(i=0;i>gra.vertices[i].data;  gra.vertices[i].firstarc=NULL; } for(i=0;i>

4、cha;   if(cha=='y')    {     arc=(arcnode*)malloc(sizeof(arcnode));    cin>>arc->adjvex;        gra.vertices[i].firstarc=arc;    cout<<"是否还有出度：";    cin>>cha;    while(cha=='y')    {    tem=(arcnode*)malloc(sizeof(arcnode));    cin>>tem->adjvex;        arc->next

5、arc=tem;    arc=tem;    cout<<"是否还有出度：";    cin>>cha;    }    arc->nextarc=NULL;    }   if(cha=='n')    continue; } gra.vexnum=n; gra.arcnum=m; return1;}intfirstadjvex(algraphgra,vnodev)//返回依附顶点V的第一个点         //即以V为尾的第一个结点{ returnv.firstarc->adjvex;}intnextadjve

6、x(algraphgra,vnodev,intw)//返回依附顶点V的相对于W的下一个顶点{ arcnode*p; p=v.firstarc; while(p!=NULL) {  if(p->adjvex!=w)   p=p->nextarc;  if(p->adjvex==w&&p->nextarc!=NULL)   returnp->nextarc->adjvex;  elsereturn0; }}intinitqueue(linkqueue&q)//初始化队列{ q.rear=(queueptr)malloc(s

7、izeof(qnode)); q.front=q.rear; if(!q.front)  return0; q.front->next=NULL; return1;}intenqueue(linkqueue&q,inte)//入队{ queueptrp; p=(queueptr)malloc(sizeof(qnode)); if(!p)  return0; p->data=e; p->next=NULL; q.rear->next=p; q.rear=p; return1;}intdequeue(linkqueue&q

8、,int&e)//出队{ queueptrp; if(q.front==q.rear)  return0; p=q.front->next; e=p->data; q.front->next=p->next; if(q.rear==p)  q.rear=q.front; free(p); return1;}intqueueempt