好文档 - 专业文书写作范文服务资料分享网站

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

天下 分享 时间: 加入收藏 我要投稿 点赞

.

数 据 结 构实

验 报 告

实验:图的遍历

一、实验目的:

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 20 typedef struct {

int

arcs[VERTEX_MAX][VERTEX_MAX];

int vexnum,arcnum; } MGraph;

'.

void creat_MGraph1(MGraph *g) { int i,j,k; int n,m;

printf(\请输入顶点数和边数:\ scanf(\ g->vexnum=n; g->arcnum=m;

for (i=0;iarcs[i][j]=0;

.

while(1) { printf(\请输入一条边的两个顶点:\\n\

scanf(\ if(i==-1 || j==-1) break; else if(i==j || i>=n || j>=n) { printf(\输入错误,请重新输入!\\n\ } else { g->arcs[i][j]=1; g->arcs[j][i]=1; } } }

void printMG(MGraph *g) {

int i,j;

for (i=0;ivexnum;i++) {for (j=0;jvexnum;j++) printf(\ printf(\ }

printf(\}

main() {

int i,j; int fg;

MGraph *g1; g1=(MGraph

*)malloc(sizeof(MGraph));

printf(\创建无向图的邻接矩阵\\n\\n\

creat_MGraph1(g1);

printf(\此图的邻接矩阵为:\\n\ printMG(g1); }

'.

.

2、邻接链表:

#include #include #define MAX_SIZE 10 typedef struct node{ int vertex;

struct node *next;

}node,adjlist[MAX_SIZE];

adjlist g;

int visited[MAX_SIZE+1]; int que[MAX_SIZE+1];

void creat() {

int n,e; int i;

int start,end;

node *p,*q,*pp,*qq;

printf(\输入无向图的顶点数和边数:\

scanf(\ for(i = 1; i <= n ; i++) {

visited[i] = 0; g[i].vertex = i; g[i].next = NULL; }

printf(\依次输入边:\\n\ for(i = 1; i <= e ; i++) {

scanf(\ p=(node *)malloc(sizeof(node)); p->vertex = end; p->next = NULL; q = &g[start]; while(q->next) q = q->next; q->next = p; p1=(node

*)malloc(sizeof(node));

'.

p1->vertex = start; p1->next = NULL; q1 = &g[end]; while(qq->next) q1 = q1->next; q1->next = p1; } }

void bfs(int vi) { int front,rear,v; node *p; front =0; rear = 1; visited[vi] = 1; que[0] = vi; printf(\ while(front != rear) { v = que[front]; p = g[v].next; while(p) { if(!visited[p->vertex]) { visited[p->vertex]= 1; printf(\\ que[rear++] = p->vertex; } p = p->next; } front++; } }

int main() { creat();

.

bfs(1);

printf(\ return 0; }

五.实验心得与体会:

(1)通过这次实验,使我基本上掌握了图的存储和遍历,让我弄清楚了如何用邻接矩阵和邻接链表对图进行存储

(2)深度优先遍历和广度优先遍历都有着各自的优点,通过程序逐步调试,可以慢慢的理解这两种遍历方法的内涵和巧妙之处。

(3)实验过程中,总体来说还算顺畅,但在编写过程中,要养成良好的编程习惯,以免出错后浪费大量的时间在查错上。

'.

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

.数据结构实验报告实验:图的遍历一、实验目的:1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表2、掌握图的构造方法3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法4、掌握图的深度优先遍历和广度优先原理二、实验内容:1、
推荐度:
点击下载文档文档为doc格式
6nv211eih17yogl1itk20zdc523xwm00i4e
领取福利

微信扫码领取福利

微信扫码分享