图的基本操作实现（数据结构实验） |
您所在的位置：网站首页 › 邻接矩阵表示法创建无向图实验报告 › 图的基本操作实现（数据结构实验） |
|
课程名称：数据结构 实验项目名称：图结构基本操作的实现 实验目的： 1．掌握图的基本操作—遍历。 实验要求： 1、 分别用DFS和BFS的方法实现一个无向图的遍历。 实验过程： 1、 创建一个图（可用邻接矩阵或邻接表的方式进行存储）； 2、 输入选项：0或1，0为DFS，1为BFS。 3、 分别输出DFS和BFS两种遍历序列； 实验报告中给出DFS和BFS两种遍历的算法代码。 实验结果： 1、输入顶点集：1 2 3 4 5 6 7 8 2、输入边的集合： 1 2 1 3 2 4 2 5 4 8 5 8 3 6 3 7 6 7 输入：0（DFS） 输出：DFS遍历序列为：12485367 输入：1（BFS） 输出：BFS遍历序列为：12345678 实验分析： 1.简单分析DFS与BFS实现时用到的方法（DFS通过递归函数实现，用到栈的数据结构，BFS用到队列的数据结构）； 2.列举调试运行过程中出现的错误并分析原因。 要求： (1) 程序要添加适当的注释，程序的书写要采用缩进格式。 (2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。 (3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。
(4) 上传源程序到课堂派。顺序表的源程序保存为TraversalGraph.cpp。 #include #include using namespace std; #define MaxInt 32767 //表示极大值 #define MVNum 100 //最大定点数 #define OK 1 #define MAXQSIZE 100 typedef char VerTexType; //假设顶点的数据类型为字符型 typedef int ArcType; //假设边的权值类型为整型 typedef struct { VerTexType vexs[MVNum]; //定点表 ArcType arcs[MVNum][MVNum]; //邻接矩阵 int vexnum,arcnum; //图的当前点和边数 }AMGraph; AMGraph G; typedef struct { int *base; int front,rear; }SqQueue; int InitQueue(SqQueue &Q) {//构造一个空队列Q Q.base=new int[MAXQSIZE]; //为队列分配一个最大容量为MAXQSIZE的数组空间 if(!Q.base) exit(0); //存储分配失败 Q.front=Q.rear=0; //头指针和尾指针为零，队列为空 return OK; } int EnQueue(SqQueue &Q,int e) {//插入元素e为Q的新的队尾元素 if((Q.rear+1)%MAXQSIZE==Q.front) //尾指针在循环意义上加1后等于头指针，表明队满 return 0; Q.base[Q.rear]=e; //新元素插入队尾 Q.rear=(Q.rear+1)%MAXQSIZE; //队尾指针加1 return OK; } int DeQueue(SqQueue &Q,int &e) {//删除Q的队头元素，用e返回其值 if(Q.front==Q.rear) return 0; //队空 e=Q.base[Q.front]; //保存队头元素 Q.front=(Q.front+1)%MAXQSIZE; //队头指针加1 return OK; } int QueueEmpty(SqQueue &Q) { if (Q.front==Q.rear) return OK; else return 0; } int LocateVex(AMGraph G,int b) { int a; for(a=0;a>G.vexnum; //输入总顶点数 cout>G.arcnum; //输入总边数 int i,j,k,v1,v2,w; coutG.vexs[i]; for(i=0;i>v1>>v2; //输入一条边依附的顶点及权值 // i=LocateVex(G,v1); // j=LocateVex(G,v2); //确定v1和v2在G中的位置，及顶点数组的下标 // G.arcs[i][j]=w; //变的初值置为w // G.arcs[j][i]=G.arcs[i][j]; //置的对称边的权值为w G.arcs[v1][v2]=1; G.arcs[v2][v1]=1; } return OK; } bool visited[MVNum]; //访问标志数组，其初值为“false” void DFS_AM(AMGraph G,int v) {//从第V个定点出发递归的深度优先遍历图G cout |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |