天津理工大学数据结构实验报告4
- 格式：doc
- 大小：118.50 KB
- 文档页数：9
计算机科学与工程系
实验（四） 实验名称 图的深度优先与广度优先遍历
软件环境
Windows98/2000, VC++6.0或turbo C
硬件环境
PⅡ以上微型计算机
实验目的
理解图的逻辑特点，理解图的邻接矩阵或邻接表存储结构，掌握图的深度优先遍历、广度优先遍历算法。
实验内容（应包括实验题目、实验要求、实验任务等）
图的遍历
利用邻接矩阵或邻接表作为存储结构建立一个无向图，每个顶点中存放一种水果名(例如apple、orange、banana等，并要求从键盘输入)，顶点数不少于5个。要求分别以深度优先搜索(DFS)和广度优先搜索(BFS)进行遍历，输出遍历结果。
计算机科学与工程系
2 实验过程与实验结果（可包括实验实施的步骤、算法描述、流程、结论等）
实验步骤及算法描述和流程：
1. 无向图的邻接矩阵存储结构
1.1 创建无向图的边的结构，由该边的信息指针和组成该边的两个顶点的位置以及指向与两个顶点相连的下一条边构成
1.2 创建无向图的顶点结构，由顶点所存储的信息和指向依附该顶点的边的指针构成
1.3 创建无向图的结构，由顶点结构数组和无向图当前的顶点数和边数构成
1.4 利用单链队列作为无向图的邻接表存储结构
2. 采用邻接表存储结构，构造无向图
2.1 输入无向图的相关信息：顶点数，边数，再输入顶点信息构造表节点链表
2.2 输入顶点间的关系，构造出无向图的邻接表
3. 深度优先遍历无向图
3.1 编写函数DFS，从顶点v出发，对v所在的连通分量进行深度优先搜索，
并利用递归，输出结点信息并对未访问的结点调用DFS函数
3.2 编写函数DFSTraverse对无向图做深度优先搜索，对已访问的结点标记，对尚未访问过得结点调用DFS
4. 广度优先遍历无向图
使用辅助队列Q和访问标志数组visite对无向图进行非递归广度优先搜索
4.1 用for循环给顶点访问标志数组置初值0
4.2 若顶点未访问
4.2.1 对要访问顶点访问标志置为1，顶点入队
4.2.2 循环当队列不为空时，队头元素出队赋给u，并将u的未访问的邻接点入队
5. 主函数
5.1 调用无向图创建函数从键盘输入数据创建无向图
5.2 调用深度优先函数，输出无向图的深度优先搜索
5.3 调用广度优先函数，输出无向图的广度优先搜索
结论：
因为程序中邻接表的出入为头插法，所以对于输入无向图的关系时，邻接表的生成总与输入时的顺序相反，在做深度与广度优先搜索时，对于结点a，首先访问的结点，是输入边的关系时最后输入的 计算机科学与工程系
3 附录（可包括源程序清单或其它说明）
#include
#include
#define MAX_NAME 10
#define MAX_INFO 80
typedef char InfoType;
typedef char VertexType[MAX_NAME]; // 字符串类型
#define MAX_VERTEX_NUM 20
typedef enum{unvisited,visited}VisitIf;
typedef struct EBox{
VisitIf mark; // 访问标记
int ivex,jvex; // 该边依附的两个顶点的位置
struct EBox *ilink,*jlink; // 分别指向依附这两个顶点的下一条边
InfoType *info; // 该边信息指针
}EBox;
typedef struct{
VertexType data;
EBox *firstedge; // 指向第一条依附该顶点的边
}VexBox;
typedef struct{
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum,edgenum; // 无向图的当前顶点数和边数
}AMLGraph;
typedef int QElemType;
typedef struct QNode{// 单链表的链式存储结构
QElemType data; //数据域
struct QNode *next; //指针域
}QNode,*QueuePtr;
typedef struct{
QueuePtr front,//队头指针，指针域指向队头元素
rear; //队尾指针，指向队尾元素
}LinkQueue;
// 若G中存在顶点u,则返回该顶点在无向图中位置;否则返回-1
int LocateVex(AMLGraph G,VertexType u){
int i;
for(i=0;i
if(strcmp(u,G.adjmulist[i].data)==0)
return i;
return -1;
}
int CreateGraph(AMLGraph *G){ // 采用邻接表存储结构,构造无向图G
int i,j,k,l,IncInfo; 计算机科学与工程系
4 char s[MAX_INFO];
VertexType va,vb;
EBox *p;
printf("请输入无向图G的顶点数,边数: ");
scanf("%d,%d",&(*G).vexnum,&(*G).edgenum);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i){ // 构造顶点向量
scanf("%s",(*G).adjmulist[i].data);
(*G).adjmulist[i].firstedge=NULL;
}
printf("请顺序输入每条边的两个端点(以空格作为间隔):\n");
for(k=0;k<(*G).edgenum;++k){// 构造表结点链表
scanf("%s%s%*c",va,vb); // %*c吃掉回车符
i=LocateVex(*G,va); // 一端
j=LocateVex(*G,vb); // 另一端
p=(EBox*)malloc(sizeof(EBox));
p->mark=unvisited; // 设初值
p->ivex=i;
p->jvex=j;
p->info=NULL;
p->ilink=(*G).adjmulist[i].firstedge; // 插在表头
(*G).adjmulist[i].firstedge=p;
p->jlink=(*G).adjmulist[j].firstedge; // 插在表头
(*G).adjmulist[j].firstedge=p;
}
return 1;
}
VertexType* GetVex(AMLGraph G,int v){ // 返回v的值
if(v>=G.vexnum||v<0)
exit(0);
return &G.adjmulist[v].data;
}
// 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1
int FirstAdjVex(AMLGraph G,VertexType v){
int i;
i=LocateVex(G,v);
if(i<0)
return -1;
if(G.adjmulist[i].firstedge) // v有邻接顶点
if(G.adjmulist[i].firstedge->ivex==i)
return G.adjmulist[i].firstedge->jvex;
else
return G.adjmulist[i].firstedge->ivex;
else 计算机科学与工程系
5 return -1;
}
// 返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个邻接点,则返回-1
int NextAdjVex(AMLGraph G,VertexType v,VertexType w){
int i,j;
EBox *p;
i=LocateVex(G,v); // i是顶点v的序号
j=LocateVex(G,w); // j是顶点w的序号
if(i<0||j<0) // v或w不是G的顶点
return -1;
p=G.adjmulist[i].firstedge; // p指向顶点v的第1条边
while(p)
if(p->ivex==i&&p->jvex!=j) // 不是邻接顶点w(情况1)
p=p->ilink; // 找下一个邻接顶点
else if(p->jvex==i&&p->ivex!=j) // 不是邻接顶点w(情况2)
p=p->jlink; // 找下一个邻接顶点
else // 是邻接顶点w
break;
if(p&&p->ivex==i&&p->jvex==j){ // 找到邻接顶点w(情况1)
p=p->ilink;
if(p&&p->ivex==i)
return p->jvex;
else if(p&&p->jvex==i)
return p->ivex;
}
if(p&&p->ivex==j&&p->jvex==i){ // 找到邻接顶点w(情况2)
p=p->jlink;
if(p&&p->ivex==i)
return p->jvex;
else if(p&&p->jvex==i)
return p->ivex;
}
return -1;
}
int visite[MAX_VERTEX_NUM]; // 访问标志数组(全局量)
int(*VisitFunc)(VertexType v);
void DFS(AMLGraph G,int v){
int j;
EBox *p;
VisitFunc(G.adjmulist[v].data);
visite[v]=1;
p=G.adjmulist[v].firstedge;
while(p){
