实验8图的邻接矩阵表示及遍厉算法.doc

实验八 图的邻接矩阵表示及遍厉算法科目：数据结构实验和课程设计 班级：10信管 姓名：戴丽 学号：2010110401实验目的：熟悉C语言程序的基本结构，掌握程序中的用户头文件、文件之间的相互关系及各自的作用。熟悉图的邻接矩阵表示和遍历算法。熟悉C语言操作环境的使用以及多文件程序的输入、编辑、调试和运行的全过程。实验要求：认真阅读和掌握本实验内容所给的全部程序。保存和输出程序运行结果，并结合程序进行分析。按照你对图的邻接矩阵表示和遍历算法，编写程序代码然后运行，给出运行结果。实验设备：每人一台安装VC6.0编写软件的计算机，公用打印机。注意事项：要在硬盘上建立好自己的工作目录，专门用来存储自己所做的实验程序及相关数据，以后每次做实验最好仍采用这个目录。认真编写算法及运行结果，针对本实验的具体算法，认真写出算法分析。实验步骤：#include /无向连通图的邻接矩阵表示以及无向连通图的深度优先搜索、广度优先搜索#define n 4/图中的顶点数#define e 5/图中的边数typedef char vertype;/设置图的顶点信息为整型struct graph vertype vexsn;/图的顶点信息表 int ann;/图的邻接矩阵;/图的邻接矩阵表示结构定义graph create()/建立无向连通图g的邻接矩阵表示graph g; int i,j,k; for(k=0;kg.vexsk; for(i=0;in;i+) for(j=0;jn;j+) g.aij=0; for(k=0;kij; g.aij=g.aji=1; return g;void dfs(graph g,int i)/对以邻接矩阵表示的无向连通图，以序号为i的顶点为出发点进行深度优先搜索coutg.vexsi;int flag4=1,1,1,1;for(int j=0;j4;j+)if(g.aij!=0&!flagj)dfs(g,j);void bfs(graph g,int i)/对以邻接矩阵表示的无向连通图，以序号为i的顶点作为出发点进行广度优先搜索int j,w,flag4=0;int s100,front,rear=0;char p;coutg.vexsi;flagi=1;rear+;srear=i;while(front!=rear)front+;w=sfront;p=g.vexsw;for(j=0;j4;j+)if(g.aij!=0&!flagj)coutg.vexsj;flagj=1;rear+;srear=j;void main() graph g;/申请无向连通图g的邻接矩阵表示空间 g=create();/建立用邻接矩阵表示的无向连通图cout对无向连通图g进行深度优先搜索得到的序列是:; dfs(g,0);cout对无向连通图g进行广度优先搜索得到的序列是:; bfs(g,0);算法分析：1、 邻接矩阵是表示顶点之间相互关系的矩阵，用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有关联。2、 图的遍历是按照某种搜索方法沿着图的边访问图的所有顶点，使每个顶点仅被访问一次。