利用鄰接表存儲無向圖,并深度遍歷和廣度遍歷圖

1、利用鄰接表存儲無向圖 ,并深度遍歷和廣度遍歷圖#include <stdio.h>#include <iostream.h>#include <malloc.h>#define max 20int visitedmax;int w;typedef struct arcnodeint adjvex;/該弧指向的頂點的位置struct arcnode *nextarc;/ 弧尾相同的下一條弧 char *info;/ 該弧信息arcnode;typedef struct vnodechar data;/ 結(jié)點信息arcnode *firstarc;/指想第一條依

2、附該結(jié)點的弧的指針vnode,adjlist;typedef structadjlist verticesmax;int vexnum,arcnum;int kind;algraph;typedef struct qnodeint data;struct qnode *next; qnode,*queueptr;typedef structqueueptr front;queueptr rear;linkqueue;void dfs(algraph gra,int i);int creatadj(algraph &gra)/用鄰接表存儲圖int i,n,m;char cha;cout&

3、lt;<" 輸如結(jié)點個數(shù)： " cin>>n;cout<<" 輸如弧個數(shù)： "cin>>m; arcnode *arc,*tem;for(i=0;i<n;i+)cout<<" 輸如結(jié)點信息： "cin>>gra.verticesi.data;gra.verticesi.firstarc=NULL;for(i=0;i<n;i+)cout<<" 結(jié)點 "<<i<<" 是否有出度： "ci

4、n>>cha;if(cha='y') arc=(arcnode *)malloc(sizeof(arcnode);cin>>arc->adjvex;gra.verticesi.firstarc=arc;cout<<" 是否還有出度： " cin>>cha;while(cha='y')tem=(arcnode *)malloc(sizeof(arcnode); cin>>tem->adjvex;arc->nextarc=tem;arc=tem;cout<<

5、" 是否還有出度： " cin>>cha; arc->nextarc=NULL; if(cha='n') continue;gra.vexnum=n;gra.arcnum=m;return 1;int firstadjvex(algraph gra,vnode v)/ 返回依附頂點 V 的第一個點/即以 V 為尾的第一個結(jié)點return v.firstarc->adjvex;返回依附頂點V的相對于W的int nextadjvex(algraph gra,vnode v,int w)/ 下一個頂點 arcnode *p; p=v.fir

6、starc; while(p!=NULL) if(p->adjvex!=w) p=p->nextarc; if(p->adjvex=w&&p->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

7、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->

8、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,vnode v)/ 廣度優(yōu)先遍歷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;cout<

9、<gra.verticesi.data;enqueue(q,i);while(!queueempty(q)dequeue(q,e);for(w=firstadjvex(gra,gra.verticese);w>0;w=nextadjvex(gra,gra.ve rticese,w)if(!visitedw)visitedw=1;cout<<gra.verticesw.data;enqueue(q,w);深度優(yōu)先遍歷int dfstra(algraph gra,vnode v)/ int i;for(i=0;i<gra.vexnum;i+)visitedi=0;for(i=0;i<gra.vexnum;i+)if(!visitedi)dfs(gra,i);return 1;void dfs(algraph gra,int i)visitedi=1;cout<<gra.verticesi.data;for(w=firstadjvex(gra,gra.verticesi);w>0;w=nextadjvex(gra,gra.vert icesi,w)if(!visitedw)dfs(gra,w);void main()algraph