数据结构教程

上机实验报告 实验七、 图算法上机实现

一、 实验目的：

1. 了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2. 掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接

矩阵和邻接表的类型定义。

3. 掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方

法及其基本思想。 二、 实验内容：

1. 建立无向图的邻接矩阵 2. 图的深度优先搜索 3. 图的广度优先搜索

三、实验步骤及结果： 1. 建立无向图的邻接矩阵： 1) 源代码： #include \ #include \ #define MAXSIZE 30 typedef struct

{ char vertex[MAXSIZE];

irstedge=NULL; irstedge; irstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } int

visited[MAXSIZE];

ertex);

ertex=i;

irstedge;

ertex=i; irstedge=NULL;

irstedge;irstedge=p;

p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } }

typedef struct node {

int data;

struct node *next;

}QNode; ertex); irstedge;ertex); //输出这个邻接边结点的顶点信息

visited[p->adjvex]=1; //置该邻接边结点为访问过标志

In_LQueue(Q,p->adjvex); //将该邻接边结点送人队Q }

p=p->next;//在顶点j的邻接表中查找j的下一个邻接边结点 } } }

void main() {

int e,n;

VertexNode g[MAXSIZE];//定义顶点表结点类型数组g LQueue *q;

printf(\输入图中结点个数 scanf(\

printf(\输入图中边的个数 scanf(\

printf(\

CreatAdjlist(g,e,n);//建立无向图的邻接表 Init_LQueue(&q);//队列q初始化 printf(\

BFS(g,q,0); //广度优先遍历以邻接表存储的无向图 printf(\

}

1) 运行结果：