資源描述:
《利用鄰接表存儲(chǔ)無(wú)向圖,并深度遍歷和廣度遍歷圖》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、利用鄰接表存儲(chǔ)無(wú)向圖,并深度遍歷和廣度遍歷圖#include#include#include#definemax20intvisited[max];intw;typedefstructarcnode{?intadjvex;//該弧指向的頂點(diǎn)的位置?structarcnode*nextarc;//弧尾相同的下一條弧?char*info;//該弧信息}arcnode;typedefstructvnode{?chardata;//結(jié)點(diǎn)信息?arcnode*firstarc;//指想第一條依附該結(jié)點(diǎn)的弧的指針}vnod
2、e,adjlist;typedefstruct{?adjlistvertices[max];?intvexnum,arcnum;?intkind;}algraph;typedefstructqnode{?intdata;?structqnode*next;}qnode,*queueptr;typedefstruct{?queueptrfront;?queueptrrear;}linkqueue;voiddfs(algraphgra,inti);intcreatadj(algraph&gra)//用鄰接表存儲(chǔ)圖{?inti,n,m;?charcha;?cout<<"輸如結(jié)點(diǎn)
3、個(gè)數(shù):";?cin>>n;?cout<<"輸如弧個(gè)數(shù):";?cin>>m;?arcnode*arc,*tem;?for(i=0;i>gra.vertices[i].data;??gra.vertices[i].firstarc=NULL;?}?for(i=0;i>cha;???if(cha=='y')????{?????arc=(arcnode*)malloc(sizeof(arcnode));????cin>>arc->
4、adjvex;????????gra.vertices[i].firstarc=arc;????cout<<"是否還有出度:";????cin>>cha;????while(cha=='y')????{????tem=(arcnode*)malloc(sizeof(arcnode));????cin>>tem->adjvex;????????arc->nextarc=tem;????arc=tem;????cout<<"是否還有出度:";????cin>>cha;????}????arc->nextarc=NULL;????}???if(cha=='n')????cont
5、inue;?}?gra.vexnum=n;?gra.arcnum=m;?return1;}intfirstadjvex(algraphgra,vnodev)//返回依附頂點(diǎn)V的第一個(gè)點(diǎn)?????????//即以V為尾的第一個(gè)結(jié)點(diǎn){?returnv.firstarc->adjvex;}intnextadjvex(algraphgra,vnodev,intw)//返回依附頂點(diǎn)V的相對(duì)于W的下一個(gè)頂點(diǎn){?arcnode*p;?p=v.firstarc;?while(p!=NULL)?{??if(p->adjvex!=w)???p=p->nextarc;??if(p->adjve
6、x==w&&p->nextarc!=NULL)???returnp->nextarc->adjvex;??elsereturn0;?}}intinitqueue(linkqueue&q)//初始化隊(duì)列{?q.rear=(queueptr)malloc(sizeof(qnode));?q.front=q.rear;?if(!q.front)??return0;?q.front->next=NULL;?return1;}intenqueue(linkqueue&q,inte)//入隊(duì){?queueptrp;?p=(queueptr)malloc(sizeof(qnode));
7、?if(!p)??return0;?p->data=e;?p->next=NULL;?q.rear->next=p;?q.rear=p;?return1;}intdequeue(linkqueue&q,int&e)//出隊(duì){?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