图结构的操作.docx
《图结构的操作.docx》由会员分享，可在线阅读，更多相关《图结构的操作.docx（8页珍藏版）》请在冰点文库上搜索。
图结构的操作
《数据结构与算法分析》
课程实验报告
项目名称：
图结构的操作
学生姓名：
学生学号：
指导教师：
完成日期：
【实验目的】
1.理解图形结构的逻辑和存储特点。
2.掌握图形结构遍历递归算法。
【实验内容】
1.用邻接矩阵或者邻接表存储一个图形结构。
2.采用深度或者广度优先搜索算法，遍历一个图，并输出遍历结果。
【实验方式】
个人实验。
【实验设备与环境】
PC机，WindowsXP操作系统，VC++6.0开发环境。
【数据结构及函数定义】
（1）类的定义：
类的数据成员，成员函数
．．．．．．．．．．．．．．．．．．．
（2）主函数main（）实现初始化操作，完成对子函数的调用
．．．．．．．．．．．．．．．．．．．
（3）子函数
．．．．．．．．．．．．．．．．．．．
。
【测试数据与实验结果】
（请用截图的方式展示实验结果，并辅以必要的文字说明）
【源程序清单】
（请附上源程序）
#include
//#include
#defineINFINITY32767
#defineMAX_VEX20//最大顶点个数
#defineQUEUE_SIZE（MAX_VEX+1）//队列长度
usingnamespacestd;
bool*visited;//访问标志数组
//图的邻接矩阵存储结构
typedefstruct{
char*vexs;//顶点向量
intarcs[MAX_VEX][MAX_VEX];//邻接矩阵
intvexnum,arcnum;//图的当前顶点数和弧数
}Graph;
//队列类
classQueue{
public:
voidInitQueue（）{
base=（int*）malloc（QUEUE_SIZE*sizeof（int））;
front=rear=0;
}
voidEnQueue（inte）{
base[rear]=e;
rear=（rear+1）%QUEUE_SIZE;
}//进队
voidDeQueue（int&e）{
e=base[front];
front=（front+1）%QUEUE_SIZE;
}//出队
public:
int*base;
intfront;
intrear;
};
//图G中查找元素c的位置
intLocate（GraphG,charc）{
for（inti=0;iif（G.vexs[i]==c）returni;
return-1;
}
//创建无向网
voidCreateUDN（Graph&G）{
inti,j,w,s1,s2;
chara,b,temp;
printf（"输入顶点数和弧数:
"）;
scanf（"%d%d",&G.vexnum,&G.arcnum）;
temp=getchar（）;//接收回车
G.vexs=（char*）malloc（G.vexnum*sizeof（char））;//分配顶点数目
printf（"输入%d个顶点.\n",G.vexnum）;
for（i=0;iprintf（"输入顶点%d:
",i）;
scanf（"%c",&G.vexs[i]）;
temp=getchar（）;//接收回车
}
for（i=0;ifor（j=0;jG.arcs[i][j]=INFINITY;
printf（"输入%d条弧.\n",G.arcnum）;
for（i=0;iprintf（"输入弧%d:
",i）;
scanf（"%c%c%d",&a,&b,&w）;//输入一条边依附的顶点和权值
temp=getchar（）;//接收回车
s1=Locate（G,a）;
s2=Locate（G,b）;
G.arcs[s1][s2]=G.arcs[s2][s1]=w;
}
}
//图G中顶点k的第一个邻接顶点
intFirstVex（GraphG,intk）{
if（k>=0&&kfor（inti=0;iif（G.arcs[k][i]!
=INFINITY）returni;
}
return-1;
}
//图G中顶点i的第j个邻接顶点的下一个邻接顶点
intNextVex（GraphG,inti,intj）{
if（i>=0&&i=0&&jfor（intk=j+1;kif（G.arcs[i][k]!
=INFINITY）returnk;
}
return-1;
}
//深度优先遍历
voidDFS（GraphG,intk）{
inti;
if（k==-1）{//第一次执行DFS时,k为-1
for（i=0;iif（!
visited[i]）DFS（G,i）;//对尚未访问的顶点调用DFS
}
else{
visited[k]=true;
printf（"%c",G.vexs[k]）;//访问第k个顶点
for（i=FirstVex（G,k）;i>=0;i=NextVex（G,k,i））
if（!
visited[i]）DFS（G,i）;//对k的尚未访问的邻接顶点i递归调用DFS
}
}
//广度优先遍历
voidBFS（GraphG）{
intk;
QueueQ;//辅助队列Q
Q.InitQueue（）;
for（inti=0;iif（!
visited[i]）{//i尚未访问
visited[i]=true;
printf（"%c",G.vexs[i]）;
Q.EnQueue（i）;//i入列
while（Q.front!
=Q.rear）{
Q.DeQueue（k）;//队头元素出列并置为k
for（intw=FirstVex（G,k）;w>=0;w=NextVex（G,k,w））
if（!
visited[w]）{//w为k的尚未访问的邻接顶点
visited[w]=true;
printf（"%c",G.vexs[w]）;
Q.EnQueue（w）;
}
}
}
}
//主函数
voidmain（）{
inti;
GraphG;
CreateUDN（G）;
visited=（bool*）malloc（G.vexnum*sizeof（bool））;
printf（"\n广度优先遍历:
"）;
for（i=0;ivisited[i]=false;
DFS（G,-1）;
printf（"\n深度优先遍历:
"）;
for（i=0;ivisited[i]=false;
BFS（G）;
printf（"\n程序结束.\n"）;
}
上课纪律（20%）
实验过程及结果（40%）
实验报告质量（40%）
总分：
教师签字：
升级会员 