数据结构图的邻接矩阵,邻接表存储表示，图的深度优先搜索遍历，广度优先搜索遍历

#include <stdio.h> #include<malloc.h> #define maxvertexnum 100 #define queuesize 100 #define null 0 typedef struct{ int front,rear,count,data[queuesize]; }cirqueue; typedef int vertextype; typedef struct node{ int adjvex; struct node *next; }edgenode; typedef struct vnode{ vertextype vertex; edgenode *firstedge; }vertexnode; typedef vertexnode adjlist[maxvertexnum]; typedef struct{ adjlist adjlist; int n; int e; }algraph; typedef enum{FALSE,TRUE}boolean; boolean visited[maxvertexnum]; void createalgraph(algraph *g) { int i,j,k; int flag; edgenode *s; printf("\ncreat:\n"); printf("digraph--0\n"); printf("undigraph--1\n"); scanf("%d",&flag); printf("input n,e\n"); scanf("%d%d",&g->n,&g->e); printf("input nodes:\n"); for(i=0;i<g->n;i++){ scanf("%d",&(g->adjlist[i].vertex)); g->adjlist[i].firstedge=null; } for(k=0;k<g->e;k++){ printf("input i,j(0~n-1):\n"); scanf("%d%d",&i,&j); s=(edgenode *)malloc(sizeof(edgenode)); s->adjvex=j; s->next=g->adjlist[i].firstedge; g->adjlist[i].firstedge=s; if (flag){ s=(edgenode *)malloc(sizeof(edgenode)); s->adjvex=i; s->next=g->adjlist[j].firstedge; g->adjlist[j].firstedge=s; } } } void dfs(algraph *g,int i) { edgenode *p; printf("visit vertex:%d",g->adjlist[i].vertex); visited[i]=TRUE; p=g->adjlist[i].firstedge; while(p){ if (!visited[p->adjvex]) dfs(g,p->adjvex); p=p->next; } } void dfstraverse(algraph *g) { int i; for(i=0;i<g->n;i++) visited[i]=FALSE; for(i=0;i<g->n;i++) if(!visited[i]) dfs(g,i); printf("\n"); }//end of dfstraverse void bfs(algraph *g,int k) { int i,j; cirqueue *q; edgenode *p; q=(cirqueue *)malloc(sizeof(cirqueue)); q->rear=q->front=q->count=0; printf("visit vertex:%d",g->adjlist[k].vertex); visited[k]=TRUE; q->data[q->rear]=k;q->rear=(q->rear+1)%queuesize;q->count++; while(q->count){ i=q->data[q->front];q->front=(q->front+1)%queuesize;q->count--; p=g->adjlist[i].firstedge; while (p){ if(!visited[p->adjvex]){ printf("visit vertex:%d",g->adjlist[p->adjvex].vertex); visited[p->adjvex]=TRUE; q->data[q->rear]=p->adjvex;q->rear=(q->rear+1)%queuesize;q->count++; }//end of if p=p->next; } } } void bfstraverse(algraph *g) { int i; for(i=0;i<g->n;i++) visited[i]=FALSE; for(i=0;i<g->n;i++) if(!visited[i]) bfs(g,i); printf("\n"); } void main() { algraph *g; g=(algraph*)malloc(sizeof(algraph)); createalgraph(g); printf("the dfs is:"); dfstraverse(g); printf("the bfs is:"); bfstraverse(g); }