实验报告：图.doc

（实验七）第 13 页 / 共 13 页
分数： 批阅老师： 2010年 月 日
（实验七）第 1 页 / 共 13 页
肇庆学院 计算机学院/软件学院
实 验 报 告（实验七）
专业 班级 姓名 学号 课程名称 数据结构
学年2009 --2010 学期 1□ / 2□ 课程类别 专业必修□ 限选□ 任选□ 实践□
实验内容： 实验时间：2010年 7月2日
，采用邻接矩阵表示法，构造一个无向网。
，实现从键盘输入数据，建立一个有向图的邻接表。
，输出该邻接表。
，采用邻接表存储实现无向图的深度优先非递归遍历。
，采用邻接表存储实现无向图的广度优先遍历。
，在主函数中设计一个简单的菜单，分别调试上述算法。
实验目的及要求：

、广度优先遍历算法思想及其程序实现

方法与步骤：
详见从第2页开始的源代码
实验结果：
小结：
（实验七）第 2 页 / 共 13 页
分数： 批阅老师： 2010年 月 日
（实验七）第 1 页 / 共 13 页
肇庆学院 计算机学院/软件学院
实验报告（附页）
源代码：
#include<>
#include<>
#include<>
#define MAX_VERTEX_NUM 10 //顶点最大个数
#define STACK_INIT_SIZE 100
//邻接矩阵的类型定义
#define INFINITY 888 /* 用888代替∞ */
typedef struct ArcCell
{
int adj;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
int vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
//构造无向网
MGraph *CreateUDN(MGraph *N)
{
int i,j,k,w;
int v1,v2;
printf("输入顶点的个数:");
scanf("%d",&N->vexnum);
printf("输入边数:");
scanf("%d",&N->arcnum);
printf("输入%d个顶点的元素:",N->vexnum);
for(i=0;i<N->vexnum;i++)
{
scanf("%d",&N->vexs[i]);
}
for(i=0;i<N->vexnum;i++)
for(j=0;j<N->vexnum;j++)
N->arcs[i][j].adj=INFINITY;
for(k=0;k<N->arcnum;k++)
{
（实验七）第 3 页 / 共 13 页
分数： 批阅老师： 2010年 月 日
（实验七）第 1 页 / 共 13 页
printf("输入第%d条边所依附的顶点:",k+1);
scanf("%d%d",&v1,&v2);
printf("输入权值:");
scanf("%d",&w);
for(i=0;i<N->vexnum;i++)
if(v1==N->vexs[i])
break;
for(j=0;j<N->vexnum;j++)
if(v2==N->vexs[j])
break;
N->arcs[i][j].adj=w;
N->arcs[j][i]=N->arcs[i][j];
}
printf(" ");
for(i=0;i<N->vexnum;i++)
printf(" v%d",N->vexs[i]);
printf("\n");
for(i=