数据结构C语言实现图的建立-图的广度-深度遍历.doc

图的建立，图的广度，深度遍历#include stdio.h#define maxsize 1000 # define n 100 typedef struct char vexsn ; int arcsnn ; int num ; G;typedef struct int datamaxsize; int front,rear; V;void GInit(G *L) L-num=0;int GVexs(G *L) return(L-num);void GCreate(G *L) int i,j; GInit(L); printf(请输入顶点数目：n); scanf(%d,&L-num); printf(请输入各顶点：n); for(i=0;inum;i+) fflush(stdin); scanf(%c,&L-vexsi); printf(请输入各顶点边的关系（1是有关0是无关）：n); for(i=0;inum;i+) for(j=0;jnum;j+) scanf(%d,&L-arcsij); void GOut(G L) int i,j; printf(n图的顶点数目为：%d,L.num); printf(n图的各顶点的信息为：n); for(i=0;iL.num;i+) printf(%7c,L.vexsi); printf(n); for(i=0;iL.num;i+) for(j=0;jL.num;j+) printf(%7d ,L.arcsij); printf(n); void DFS(G g,int qidian,int mark) int v1; markqidian=1; printf(%c ,g.vexsqidian); for(v1=0;v1g.num;v1+) if(g.arcsqidianv1!=0&markv1=0) DFS(g,v1,mark); void GDFS(G g) int qidian,v,v1,markmaxsize; printf(n深度遍历：); printf(n请输入起点的下标：); scanf(%d,&qidian) getchar(); for(v=0;vg.num;v+) markv=0; for(v=qidian;vfront=0; sq-rear=0;int QueueIsEmpty(V sq) if (sq.rear=sq.front) return(1); else return(0); int QueueFront(V sq, int *e) if (QueueIsEmpty(sq) printf(queue is empty!n);return 0; else *e=sq.data(sq.front); return 1;int QueueIn (V *sq, int x)/ if (sq-front=(sq-rear+1)%maxsize) printf(queue is full!n); return 0; else sq-datasq-rear=x; sq-rear=(sq-rear+1)%maxsize; return(1); int QueueOut(V *sq) if (QueueIsEmpty(*sq) printf(queue is empty!n); return 0; else sq-front=(sq-front+1)%maxsize; return 1; void BFS(G g,int v,int mark) int v1,v2; V q; QueueInit(&q); QueueIn(&q,v); markv=1; printf(%c ,g.vexsv); while(QueueIsEmpty(q)=0) QueueFront(q,&v1); QueueOut(&q); for(v2=0;v2g.num;v2+) if(g.arcsv1v2!=0&markv2=0) QueueIn(&q,v2); markv2=1; printf(%c ,g.vexsv2); void GBFS(G g) int qidian,v,v1,markmaxsize; printf(n广度遍历：); printf(n); scanf(%d,&qidian); for(v=0;vg.num;v+) markv=0; for(v=qidian;vg.num+qidian;v+) v1=v%g.num; if(markv1=0) BFS(g,v1,mark); void main() G tu; GCreate(&tu); GOut(tu); GDFS(tu); GBFS(tu);