《数据结构》实验报告.doc

《数据结构》实验报告.doc实验三——图
实验目的
掌握图的基本概念;
掌握图的存储结构及其建立算法;
熟练掌握图的两种遍历算法及其应用.
实验内容
对给定的图G,设计算法输出从V0出发深(广)度遍历图G的深(广)度优先搜索序列;
设计算法输出给定图G的连通分量个数及边(或弧)的数目.
实验预****内容
在实验中要用到这几个函数:typedef struct 邻接矩阵的创建,Locate函数去查找,create函数创建图,定义两个指针firstadj,nextadj找寻临接点和下一个临接点,void dfs函数从某一点开始遍历,void dfsgraph进行图的遍历算法,然后就是main 函数.
上机实验
实验源程序.
#include<>
#define max 80
int num1=0,num2=0;
bool visited[max]; //标记数组
typedef struct //邻接矩阵
{
char vexs[max];
int arcs[max][max];
int vexnum,um;
} graph;
int locate(graph G,char v) //定位
{
int i;
for(i=0;i<;i++)
if([i]==v)
return i;
if(i==)
return -1;
}
void creat(graph &G) //创建图
{
int i,j,k;
char v1,v2;
cout<<"Please input the vexnum and the um:";
cin>>>>;
cout<<"Please iput the chars in sequence:";
for(i=0;i<;i++) //读数
cin>>[i];
for(i=0;i<;i++) //二维数组初始化
for(j=0;j<;j++)
[i][j]=0;
cout<<"Create the relationship between chars:\n";
for(k=1;k<=;k++) //创建关系
{
cout<<"input v1 and v2:";
cin>>v1>>v2;
i=locate(G,v1);
j=locate(G,v2);
[i][j]=[j][i]=1;
}
}
int firstadj(graph G,int v) //第一个邻接点
{
int i;
for(i=0;i<;i++)
if([v][i])
return i;
if(i==)
return -1;
}
int nextadj(graph G,int v,int w) //下一个邻接点
{
int i;
for(i=w+1;i<;i++)
if([v][i])
return i;
if(i==