图的遍历源代码.doc

#includestdio.h #includemalloc.h typedef struct linknode{ int adjvecx; struct linknode *next; }linknode; typedef struct vnode{ char data; linknode *first; }vnode,adjlist[100]; typedef struct{ int n; adjlist vertices; }graph; int visited[10]; struct queue{ int rear,front; int node[100]; }; //队的初始化 void initqueue(queue Q){ Q.rear=-1; Q.front=-1; for(int i=0;i100;i++) Q.node[i]=0; } //判断队是否为空 int isEmpty(queue Q){ if(Q.rear==Q.front) return 0; else return 1; } //入队 void enqueue(queue Q,int e){ Q.rear=(Q.rear+1)%100; Q.node[Q.rear]=e; // Q.rear=(Q.rear+1)%100; } //出队 int dequeue(queue Q){ int v; if(isEmpty(Q)==0){ printf(该队列为空\n); } Q.front=(Q.front+1)%100; v=Q.node[Q.front]; return v; // for(int i=0;i100;i++){ // Q.node[n+1]=Q.node[n]; // } } //构建链表 void creatlinknode(graph *g,int k){ linknode *p,*q;int a,b,j; // p=G.vertices[k].first; printf(请输入第%d个顶点所指向的顶点的个数：,k+1); scanf(%d,a); if(a!=0) { printf(输入其所指向的第1个定点的位置:); scanf(%d,b); q=(struct linknode*)malloc(sizeof(struct linknode)) ; q-adjvecx=b;q-next=NULL; g-vertices[k].first=q; p=q; for( j=0;ja-1;j++) { printf(输入其所指向的第%d个定点的位置:,j+2); scanf(%d,b); q=(struct linknode*)malloc(sizeof(struct linknode)) ; q-adjvecx=b;q-next=NULL; p-next=q;p=p-next; } } else {g-vertices[k].first=NULL;} } //构建 void creatgraph(graph *g){ //int a; //int A[10]; printf(请输入顶点的个数:); scanf(%d,g-n); printf(请输入顶点的值：); for(int i=0;ig-n;i++){ getchar(); scanf(%c,g-vertices[i].data); } for(int k=0;kg-n;k++){ creatlinknode(g, k); } } //深度遍历 void dfsal(graph *g,int i){ int w;//linknode *p; // p=(struct linknode*)malloc(sizeof(struct linknode)) ; // for(int j=0;jg-n;j++) visited[j]=0; printf(%5c,g-vertices[i].data); visited[i]=1; for(linknode *p=g-vertices[i].first;p;p=p-next){ w=p-adjvecx; if(visited[w]==0) dfsal(g,w); } } //广度遍历 void bfsal(graph *g,int i){ queue Q;int w,e; int v; linknode *p; for(int j=0;jg