数据结构图的遍历实验报告

辽宁工程技术大学上机实验报告

typedef struct { VexNode xlist[M];//表向量 int vexnum,arcnum; }OlGraph; /*创建图*/ void creatgraph(Graph *g,int n) { int i,j,r1,r2; g->vexnum=n; /*顶点用 i 表示*/ for(i=1;i<=n;i++) { g->V[i]=i; } /*初始化 R*/ for(i=1;i<=n;i++) for(j=1;j<=n;j++) { g->R[i][j]=0; } /*输入 R*/ printf("Please input R(0,0 END):\n"); scanf("%d,%d",&r1,&r2); while(r1!=0&&r2!=0) { g->R[r1][r2]=1; g->R[r2][r1]=1; scanf("%d,%d",&r1,&r2); } } /*打印图的邻接矩阵*/ void printgraph(Graph *g) { int i,j; for(i=1;i<=g->vexnum;i++) { for(j=1;j<=g->vexnum;j++) { printf("%2d ",g->R[i][j]); } printf("\n"); } }

/*全局变量：访问标志数组*/

int visited[M]; /*访问顶点*/ void visitvex(Graph *g,int vex) { printf("%d ",g->V[vex]); } /*获取第一个未被访问的邻接节点*/ int firstadjvex(Graph *g,int vex) { int w,i; for(i=1;i<=g->vexnum;i++) { if(g->R[vex][i]==1&&visited[i]==0) { w=i; break; } else { w=0; } } return w; } /*获取下一个未被访问的邻接节点(深度遍历)*/ int nextadjvex(Graph *g,int vex,int w) { int t; t=firstadjvex(g,w); return t; } /*深度递归遍历*/ void dfs(Graph *g,int vex) { int w; visited[vex]=1; visitvex(g,vex); for(w=firstadjvex(g,vex);w>0;w=nextadjvex(g,vex,w)) if(!visited[w]) { dfs(g,w); } } void dfstraverse(Graph *g) {

int i; for(i=1;i<=g->vexnum;i++) visited[i]=0; for(i=1;i<=g->vexnum;i++) if(!visited[i]) {dfs(g,i);} } /*定义队列*/ typedef struct{ int V[M]; int front; int rear; }Queue; /*初始化队列*/ void initqueue(Queue *q) { q->front=0; q->rear=0; } /*判断队列是否为空*/ int quempty(Queue *q) { if(q->front==q->rear) { return 0; } else { return 1; } } /*入队操作*/ enqueue(Queue *q,in

t e) { if((q->rear+1)%M==q->front) { printf("The queue is overflow!\n"); return 0; } else { q->V[q->rear]=e; q->rear=(q->rear+1)%M; return 1;

} } /*出队操作*/ dequeue(Queue *q) { int t; if(q->front==q->rear) { printf("The queue is empty!\n"); return 0; } else { t=q->V[q->front]; q->front=(q->front+1)%M; return t; } } /*广度遍历*/ void BESTraverse(Graph *g) { int i; Queue *q=(Queue *)malloc(sizeof(Queue)); for(i=1;i<=g->vexnum;i++) { visited[i]=0; } initqueue(q); for(i=1;i<=g->vexnum;i++) { if(!visited[i]) { visited[i]=1; visitvex(g,g->V[i]); enqueue(q,g->V[i]); while(!quempty(q)) { int u,w; u=dequeue(q); for(w=firstadjvex(g,u);w>0;w=nextadjvex(g,u,w)) { if(!visited[w]) { visited[w]=1;

visitvex(g,w); enqueue(q,w);

} } } } } } /*主程序*/ void main() { int n; char menu; int choose; OlGraph GL; Graph *g=(Graph *)malloc(sizeof(Graph)); for(;;){ printf("*************************************************************** **\n"); printf("请选择想要的操作:\n"); printf("1.键盘输入数据，建立一个有向图的邻接表。\n"); printf("2.输出该邻接表。\n"); printf("3.采用邻接表存储实现无向图的深度优先遍历。\n"); printf("4.采用邻接表存储实现无向图的广度优先遍历。\n"); printf("0.退出\n"); printf("************************************************************* *****\n"); scanf("%d",&choose); getchar(); if(choose!=0) { switch(choose) { case 1:{ printf("请输入图顶点数:\n"); scanf("%d",&n); creatgraph(g,n); } break;

case 2: { printf("该邻接矩阵表为:\n"); printgraph(g); } break; case 3:{ printf("Depth_first:\n"); dfstraverse(g); printf("\n"); } break; case 4:{ printf("Breadth_first:\n"); BESTraverse(g); printf("\n"); } break; default:printf("输入错误，请重新输入\n"); break; } } else break; } }

教师 评语