数据结构图的遍历上机报告

1、成绩辽宁工程技术大学上机实验报告实验名称图的遍历院系软件学院专业软件工程班级软升本14-1姓名学号日期2014.12.26实验目的简述本次实验目的：1掌握图的邻接矩阵和邻接表存储思想及其算法的实现。2掌握图的深度、广度优先遍历算法思想及其程序实现。3掌握图的常见应用算法的思想及其程序实现。实验准备你为本次实验做了哪些准备：提前学习和掌握图的邻接表存储、建立、遍历及其应用。能够使用C语言编写程序。实验进度本次共有 5 个练习，完成 5 个。实验总结实验总结实验总结实验总结实验总结实验总结实验总结实验总结实验总结日本次实验的收获、体会、经验、问题和教训：#include <stdio.h&g

2、t; #include <stdlib.h> #include <malloc.h>#define M 20 /*定义图*/ typedef struct int VM; int RMM; int vexnum; Graph; typedef struct ArcBox int tail,head; struct ArcBox *headlink; struct ArcBox *taillink; ArcBox;/定义链元素 typedef struct VexNode int data; ArcBox *firstin; ArcBox *firstout; VexNo

3、de;/定义结点元素 typedef struct VexNode xlistM;/表向量 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->Vi=i; /*初始化R*/ for(i=1;i<=n;i+) for(j=1;j<=n;j+) g->Rij=0; /*输入R*/ printf("请输入图中边的两个顶点 (以0 0结束):n")

4、; scanf("%d%d",&r1,&r2); while(r1!=0&&r2!=0) g->Rr1r2=1; g->Rr2r1=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->Rij); printf("

5、;n"); /*全局变量：访问标志数组*/ int visitedM; /*访问顶点*/ void visitvex(Graph *g,int vex) printf("%d ",g->Vvex); /*获取第一个未被访问的邻接节点*/ int firstadjvex(Graph *g,int vex) int w,i; for(i=1;i<=g->vexnum;i+) if(g->Rvexi=1&&visitedi=0) w=i; break; else w=0; return w; /*获取下一个未被访问的邻接节点(深度

6、遍历)*/ int nextadjvex(Graph *g,int vex,int w) int t; t=firstadjvex(g,w); return t; /*深度递归遍历*/ void dfs(Graph *g,int vex) int w; visitedvex=1; visitvex(g,vex); for(w=firstadjvex(g,vex);w>0;w=nextadjvex(g,vex,w) if(!visitedw) dfs(g,w); void dfstraverse(Graph *g) int i; for(i=1;i<=g->vexnum;i+)

7、 visitedi=0; for(i=1;i<=g->vexnum;i+) if(!visitedi) dfs(g,i); /*定义队列*/ typedef struct int VM; 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(Queu

8、e *q,int e) if(q->rear+1)%M=q->front) printf("The queue is overflow!n"); return 0; else q->Vq->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->Vq->fro

9、nt; 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+) visitedi=0; initqueue(q); for(i=1;i<=g->vexnum;i+) if(!visitedi) visitedi=1; visitvex(g,g->Vi); enqueue(q,g->Vi); while(!quempty(

10、q) int u,w; u=dequeue(q); for(w=firstadjvex(g,u);w>0;w=nextadjvex(g,u,w) if(!visitedw) visitedw=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"); prin

11、tf("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("该图的深度优先遍历为:n"); dfstraverse(g); printf("n"); break; case 4