《利用邻接表存储无向图,并深度遍历和广度遍历图.doc》由会员分享，可在线阅读，更多相关《利用邻接表存储无向图,并深度遍历和广度遍历图.doc（5页珍藏版）》请在金锄头文库上搜索。
1、利用邻接表存储无向图,并深度遍历和广度遍历图#include #include #include #define max 20int visitedmax;int w;typedef struct arcnodeint adjvex;/该弧指向的顶点的位置struct arcnode *nextarc;/弧尾相同的下一条弧char *info;/该弧信息arcnode;typedef struct vnodechar data;/结点信息arcnode *firstarc;/指想第一条依附该结点的弧的指针vnode,adjlist;typedef structadjlist verticesm
2、ax;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;coutn;coutm;arcnode *arc,*tem;for(i=0;in;i+)coutgra.verticesi.da
3、ta;gra.verticesi.firstarc=NULL;for(i=0;in;i+)cout结点icha;if(cha=y)arc=(arcnode *)malloc(sizeof(arcnode);cinarc-adjvex;gra.verticesi.firstarc=arc;coutcha;while(cha=y)tem=(arcnode *)malloc(sizeof(arcnode);cintem-adjvex;arc-nextarc=tem;arc=tem;coutcha;arc-nextarc=NULL;if(cha=n)continue;gra.vexnum=n;gra.
4、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=w&p-nextarc!=NULL)return p-nextarc-adjvex;else return 0;int
5、 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 &
6、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,vnode v)/广度优先遍历int i,e;linkqueue q;for(i=0;igra.vexnum;i+)visitedi=0;
7、initqueue(q);for(i=0;igra.vexnum;i+)if(!visitedi)visitedi=1;cout0;w=nextadjvex(gra,gra.verticese,w)if(!visitedw)visitedw=1;coutgra.verticesw.data;enqueue(q,w);int dfstra(algraph gra,vnode v)/深度优先遍历int i;for(i=0;igra.vexnum;i+)visitedi=0;for(i=0;igra.vexnum;i+)if(!visitedi)dfs(gra,i);return 1;void dfs(algraph gra,int i)visitedi=1;cout0;w=nextadjvex(gra,gra.verticesi,w)if(!visitedw)dfs(gra,w);void main()algraph gra;vnode v;creatadj(gra);cout广度优先遍历：;bfstra(gra,v);coutendl;cout深度优先遍历：;dfstra(gra,v);coutendl;
