实验五图的基本操作17735

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

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

3、euelist* q,int* e) 函数实现出队操作， if-else语句完成函数的具体操作void creatadjlist(graph* g)函数用来完成创建图的操作，其中使用两次 for 循环语句第一次用循环语句输入顶点，第二次建立无向图中的边和表， 流程图如图表 1 所示void dfs(graph *g,int i,int visit)函数是从第i个顶点出发递归的深度优先遍历图g 深度优先搜索：dfs() ：寻找 v 的还没有访问过的邻接点，循环找到v 的所有的邻接点，每找到一个都以该邻接点为新的起点递归调用深度优先搜索，找下一个邻接点。void dfs(vexs b,adjmat

4、 a,int v,int visited,int n) int w; coutbv ; visitedv=1; w=0; while(wn & avw=0) w+; while(wn) if(visitedw=0 & avw!=0) dfs(b,a,w,visited,n); w+; 广度优先搜索：bfs() ：设置一个队列，并设置一个变量w存放下一个邻接点的变量序号和队尾队首的指针。void bfs(vexs b,adjmat a,int v,int visited,int n) int queuemax; int w,rear,first; rear=first=0; co

5、utbv ; visitedv=1; rear+; queuerear=v; while(first!=rear) first+; v=queuefirst; w=0; while(wn) if(avw=1 & visitedw=0) coutbw ; visitedw=1; rear+; queuerear=w; w+; 查找 v 在图中位置函数：locatevex()：输入每第弧所连接的两条边时要定们v 在图中的位置。int locatevex(vexs b,char v,int n) int k,i; k=-1; for(i=0;in;+i) if(bi=v) k=i; retu

6、rn k; 主函数：main(): 定义了一些变量， 输入输出等操作， 以及深度优先， 广度优先遍历时for循环判断等。void main() int n,m,i,j,k1,k2; vexs b; adjmat a; char v1,v2; int visitedmax; coutn; for (i=0;in;+i) for (j=0;jn;+j) aij=0; / 邻接矩阵赋初值cout 请输入 n个顶点的值 n; for(i=0;ibi; coutm; cout 请依次输入各条弧 :endl; for(j=1;jm+1;+j) cout 请输入第 jv1; cinv2; k1=locate

7、vex(b,v1,n); k2=locatevex(b,v2,n); ak1k2=1; ak2k1=1; for(i=0;imax;i+) visitedi=0; cout 深度优先搜索 ; for(i=0;in;+i) if(!visitedi) dfs(b,a,i,visited,n); coutendl; for(i=0;imax;i+) visitedi=0; cout 广度优先搜索 ; for(i=0;in;+i) if(!visitedi) bfs(b,a,i,visited,n); coutb-c-d-e-f-g-h 深度优先： a-b-d-h-e-c-f-g 三程序执行及数据验

8、证按照顺序依次输入每条弧所连接的顶点：直接调用深度优先搜索和广度优先搜索：四总结此次图的遍历实验， 在与同学的合作下以及上网查阅资料重新认识到了图的基本的操作： 图的建立，图的遍历，使我对实验有了些头绪， 虽然程序相对简单，但我也是花了不少时间去进行修改，最终还是实现了程序的运行。 经过这次试验又一次提高了我的编程能力逻辑思维能力，动手能力等。三源程序#include #include #include using namespace std; #define max 10 typedef char vexsmax; typedef int adjmatmaxmax; void dfs(vex

9、s b,adjmat a,int v,int visited,int n) int w; coutbv ; visitedv=1; w=0; while(wn & avw=0) w+; while(wn) if(visitedw=0 & avw!=0) dfs(b,a,w,visited,n); w+; void bfs(vexs b,adjmat a,int v,int visited,int n) int queuemax; intw,rear,first; rear=first=0; coutbv ; visitedv=1; rear+; queuerear=v; whi

10、le(first!=rear) first+; v=queuefirst; w=0; while(wn) if(avw=1 & visitedw=0) coutbw ; visitedw=1; rear+; queuerear=w; w+; intlocatevex(vexsb,charv,int n) intk,i; k=-1; for (i=0;in;+i) if (bi=v) k=i; return k; void main() int n,m,i,j,k1,k2; vexs b; adjmat a; char v1,v2; int visitedmax; coutn; for(i=0;in;+i) for(j=0;jn;+j) aij=0; cout 请输入 n个顶点的值n; for(i=0;ibi; coutm; cout 请依次输入各条弧 :endl; for (j=1;jm+1;+j) cout 请输入第 jv1; cinv2; k1=locatevex(b,v1,n); k2=locatevex(b,v2,n); ak1k2=1; ak2k1=1; for(i=0;imax;i+) visitedi=0; cout 深度优先