文档介绍：闽 江 学 院 电 子 系 实 验 报 告
学生姓名：
班级：
学 号：
课程：算法与数据结构
一、实验题目：：图及其应用
一、 实验地点：实验楼 A210
二、 实验目的：
. 熟练掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法
. 掌握图的基本运算及应用
. 加深对图的理解，逐步培养解决实际问题的编程能力
三、 实验内容：
. 采用邻接表或邻接矩阵方式存储图，实现图的深度遍历和广度遍历；
. 用广度优先搜索方法找出从一顶点到另一顶点边数最少的路径；
. 图的存储结构的转换。
四、 实验环境（使用的软硬件）：
Visual C++集成开发环境
五、实验步骤及操作
启动 VC++；
新建工程/Win32 Console Application，选择输入位置：输入工程的名称：tu； 按“确定”按钮，选择“An Empty Project”，再按“完成”按钮，
新建文件/C++ Source File，选中“添加到工程的复选按钮”，输入文件名“1. cpp”，按“确定”
按钮，在显示的代码编辑区内输入如下的参考程序:
#include <> #include <> #define Infinity 1000 #define MAX 20
1
typedef struct{
int vexnum; // 顶 点 数 目
int arcnum; // 弧 数 目
char vexs[MAX]; // 顶 点 向 量
int arcs[MAX][MAX]; //邻接矩阵
char kind; //图的种类：有向图 D，无向图 U
}MGraph;
//图的建立
MGraph Creat_MGraph(){
MGraph G;
int i,j,k,w;
char v1,v2;
printf("请输入图的种类（有向图（D）,无向图（U）！\n");
scanf("%c",&);
printf("请输入顶点数目和弧数目!\n");
scanf("%d%d",&,&);
getchar();
printf("请输入各个顶点（abc）!\n");
for(i=0;i<;i++)
scanf("%c",&[i]);
getchar();
for(i=0;i<;i++){
for(j=0;j<;j++)
[i][j]=Infinity;
}
for(i=0;i<;i++){
printf("请输入第 (%d) 条弧的起始点和它的权重（ccd）!\n",i+1);
scanf("%c%c%d",&v1,&v2,&w);
getchar(); j=k=0;
while([j]!=v1) j++; // 起 点
while([k]!=v2) k++; // 终 点
[j][k]=w;
if(=='U')
2
[k][j]=w;
}
return G;
}
int visited[MAX]; //标志数组，显示是否遍历
//递归深度遍历调用函数 void DFS(MGraph G,int i){
int j;
visited[i]=1;
printf(" %c ",[i]);
if(!visited[j]&&[i][j]<Infinity)
DFS(G,j);
for(j=0;j<;j++)
}
//深度遍历函数
void M_DFSTraverse(MGraph G){
int i;
printf("深度遍历图结果如下： \n");
for(i=0;i<;i++)
visited[i]=0;
for(i=0;i<;i++)
if(!visited[i])
DFS(G,i);
printf("\n");
}
//广度遍历函数
void M_BFSTraverse(MGraph G){
int i,j,k,Q[MAX],w;
j=k=0;