数据结构实验报告-图的遍历.pdf
数 据 结 构实实 验验 报报 告告实验：图的遍历实验：图的遍历一、实验目的：一、实验目的：1、理解并掌握图的逻辑结构和物理结构邻接矩阵、邻接表2、掌握图的构造方法3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法4、掌握图的深度优先遍历和广度优先原理二、实验内容：二、实验内容：1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图3、深度优先遍历第一步中构造的图 G，输出得到的节点序列4、广度优先遍历第一部中构造的图 G，输出得到的节点序列三、实验要求：三、实验要求：1、无向图中的相关信息要从终端以正确的方式输入；2、具体的输入和输出格式不限；3、算法要具有较好的健壮性，对错误操作要做适当处理；4、程序算法作简短的文字注释。四、程序实现及结果：四、程序实现及结果：1 1、邻接矩阵、邻接矩阵：#include#include#define VERTEX_MAX 30#define MAXSIZE 20typedef struct intelseif(i=j|i=n|j=n)printf(输入错误,请重新输入！n);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;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 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,*qq;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(qq-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)实验过程中，总体来说还算顺畅，但在编写过程中，要养成良好的编程习惯，以免出错后浪费大量的时间在查错上。
