实验五 的基本操作.doc

《实验五 的基本操作.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验五图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。二、实验内容本次实验提供4个题目，难度相当，学生可以根据自己的情况选做，其中题目一是必做题，其它选作！题目一：图的遍历（必做）[问题描述]　　对给定图，实现图的深度优先遍历和广度优先遍历。[基本要求]　　　以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。【测试数据】　　由学生依据软件工程的测试技术自己确定。题目二：在图G中求一条从顶点i到顶点s的简单路

2、径［测试数据］自行设计[题目三]：在图G中求一条从顶点i到顶点s且长度为K的简单路径［测试数据］自行设计三、实验前的准备工作1、掌握图的相关概念。2、掌握图的逻辑结构和存储结构。3、掌握图的两种遍历算法的实现。四、实验报告要求1、实验报告要按照实验报告格式规范书写。2、实验上要写出多批测试数据的运行结果。3、结合运行结果，对程序进行分析。一．实验内容定义结构体QueueNode，并完成队列的基本操作，利用队列先进先出的性质，在广度优先遍历时将队列作为辅助工具来完成广度优先遍历。 l void EnQueue(QueueList* Q,int e)

3、函数实现进队操作，if-else语句完成函数的具体操作 l void DeQueue(QueueList* Q,int* e)函数实现出队操作，if-else语句完成函数的具体操作 l void CreatAdjList(Graph* G)函数用来完成创建图的操作，其中使用两次for循环语句第一次用循环语句输入顶点，第二次建立无向图中的边和表，流程图如图表1所示 l void dfs(Graph *G,int i,int visit[])函数是从第i个顶点出发递归的深度优先遍历图G深度优先搜索：dfs()：寻找v的还没有访问过的邻接点，循环找到v

4、的所有的邻接点，每找到一个都以该邻接点为新的起点递归调用深度优先搜索，找下一个邻接点。 voiddfs(vexsb,adjmata,intv,intvisited[],intn)  {intw;  cout<

5、w存放下一个邻接点的变量序号和队尾队首的指针。 voidbfs(vexsb,adjmata,intv,intvisited[],intn)  { intqueue[Max]; intw,rear,first; rear=first=0;   cout<

6、  cout<

7、先遍历时for循环判断等。 void main(){  int n,m,i,j,k1,k2;   vexsb;  adjmata;  charv1,v2;  intvisited[Max];  cout<<"请输入顶点数:";  cin>>n;  for(i=0;i>b[i];  cout<<"请输入弧的条数:";  cin>>m;  cout<<"请依次

8、输入各条弧:"<