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

数 据 结 构实 验 报 告实验：图的遍历一、实验目的：1、理解并掌握图的逻辑结构和物理结构邻接矩阵、邻接表2、掌握图的构造方法3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法4、掌握图的深度优先遍历和广度优先原理二、实验内容：1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图3、深度优先遍历第一步中构造的图G，输出得到的节点序列4、广度优先遍历第一部中构造的图G，输出得到的节点序列三、实验要求：1、无向图中的相关信息要从终端以正确的方式输入；2、具体的输入和输出格式不限；3、算法要具有较好的健壮性，对错误操作要做适当处理；4、程序算法作简短的文字注释。四、程序实现及结果：1、邻接矩阵：#include #include #define VERTEX_MAX 30 #define MAXSIZE 20typedef struct int arcsVERTEX_MAXVERTEX_MAX; int vexnum,arcnum; MGraph;void creat_MGraph1(MGraph *g) int i,j,k; int n,m; printf(请输入顶点数和边数:); scanf(%d%d,&n,&m); g-vexnum=n; g-arcnum=m; for (i=0;in;i+) for (j=0;jarcsij=0; while(1) printf(请输入一条边的两个顶点：n); scanf(%d%d,&i,&j);if(i=-1 | j=-1)break;else if(i=j | i=n | j=n)printf(输入错误,请重新输入！n);elseg-arcsij=1; g-arcsji=1; void printMG(MGraph *g) int i,j; for (i=0;ivexnum;i+) for (j=0;jvexnum;j+) printf( %d,g-arcsij); printf(n); printf(n);main() int i,j; int fg; MGraph *g1; g1=(MGraph *)malloc(sizeof(MGraph); printf(1:创建无向图的邻接矩阵nn); creat_MGraph1(g1); printf(n此图的邻接矩阵为：n); printMG(g1);2、邻接链表:#include#include#define MAX_SIZE 10typedef struct node int vertex; struct node *next;node,adjlistMAX_SIZE;adjlist g; int visitedMAX_SIZE+1;int queMAX_SIZE+1; void creat() int n,e; int i; int start,end; node *p,*q,*pp,*; printf(输入无向图的顶点数和边数:); scanf(%d%d,&n,&e); for(i = 1; i = n ; i+) visitedi = 0; gi.vertex = i; gi.next = NULL; printf(依次输入边:n); for(i = 1; i vertex = end; p-next = NULL; q = &gstart; while(q-next) q = q-next; q-next = p; p1=(node *)malloc(sizeof(node); p1-vertex = start; p1-next = NULL; q1 = &gend; while(-next) q1 = q1-next; q1-next = p1; void bfs(int vi)int front,rear,v;node *p;front =0; rear = 1;visitedvi = 1; que0 = vi; printf(%d ,vi);while(front != rear) v = quefront;p = gv.next;while(p) if(!visitedp-vertex)visitedp-vertex= 1;printf(%d ,p-vertex);querear+ = p-vertex;p = p-next;front+;int main()creat();bfs(1);printf(n);return 0; 五实验心得与体会：(1)通过这次实验，使我基本上掌握了图的存储和遍历，让我弄清楚了如何用邻接矩阵和邻接链表对图进行存储(2)深度优先遍历和广度优先遍历都有着各自的优点，通过程序逐步调试，可以慢慢的理解这两种遍历方法的内涵和巧妙之处。(3)实验过程中，总体来说还算顺畅，但在编写过程中，要养成良好的编程习惯，以免出错后浪费大量的时间在查错上。