《大数据结构实验报告材料-图实验.doc》由会员分享,可在线阅读,更多相关《大数据结构实验报告材料-图实验.doc(14页珍藏版)》请在三一办公上搜索。
1、word图实验一, 邻接矩阵的实现1. 实验目的(1) 掌握图的逻辑结构(2) 掌握图的邻接矩阵的存储结构(3) 验证图的邻接矩阵存储与其遍历操作的实现2. 实验内容(1) 建立无向图的邻接矩阵存储(2) 进展深度优先遍历(3) 进展广度优先遍历3设计与编码MGraph.h#ifndef MGraph_H#define MGraph_Hconst int MaxSize = 10;templateclass MGraphpublic:MGraph(DataType a, int n, int e);MGraph()void DFSTraverse(int v);void BFSTraverse
2、(int v);private:DataType vertexMaxSize;int arcMaxSizeMaxSize;int vertexNum, arum;#endif#includeusing namespace std;#include MGraph.hextern int visitedMaxSize;templateMGraph:MGraph(DataType a, int n, int e)int i, j, k;vertexNum = n, arum = e;for(i = 0; i vertexNum; i+)vertexi = ai;for(i = 0;i vertexN
3、um; i+)for(j = 0; j vertexNum; j+)arcij = 0;for(k = 0; k arum; k+)cout i j;arcij = 1;arcji = 1;templatevoid MGraph:DFSTraverse(int v)cout vertexv;visitedv = 1;for(int j = 0; j vertexNum; j+)if(arcvj = 1 & visitedj = 0)DFSTraverse(j);templatevoid MGraph:BFSTraverse(int v)int QMaxSize;int front = -1,
4、rear = -1;cout vertexv;visitedv = 1;Q+rear = v;while(front != rear)v = Q+front;for(int j = 0;j vertexNum; j+)if(arcvj = 1 & visitedj = 0)cout vertexj;visitedj = 1;Q+rear = j;#includeusing namespace std;#include MGraph.hextern int visitedMaxSize;templateMGraph:MGraph(DataType a, int n, int e)int i, j
5、, k;vertexNum = n, arum = e;for(i = 0; i vertexNum; i+)vertexi = ai;for(i = 0;i vertexNum; i+)for(j = 0; j vertexNum; j+)arcij = 0;for(k = 0; k arum; k+)cout i j;arcij = 1;arcji = 1;templatevoid MGraph:DFSTraverse(int v)cout vertexv;visitedv = 1;for(int j = 0; j vertexNum; j+)if(arcvj = 1 & visitedj
6、 = 0)DFSTraverse(j);templatevoid MGraph:BFSTraverse(int v)int QMaxSize;int front = -1, rear = -1;cout vertexv;visitedv = 1;Q+rear = v;while(front != rear)v = Q+front;for(int j = 0;j vertexNum; j+)if(arcvj = 1 & visitedj = 0)cout vertexj;visitedj = 1;Q+rear = j;4. 运行与测试5. 总结与心得通过该实验的代码编写与调试,熟悉了邻接矩阵在图
7、结构中的应用,在调试过程中遇到很多的问题,在解决问题过程中也使我的写代码能力得到提升二, 邻接表的实现1. 实验目的(1) 掌握图的逻辑结构(2) 掌握图的邻接表存储结构(3) 验证图的邻接表存储与其遍历操作的实现2. 实验内容(1) 建立一个有向图的邻接表存储结构(2) 对建立的有向图进展深度优先遍历(3) 对建立的有向图进展广度优先遍历3. 设计与编码#ifndef ALGraph_H#define ALGraph_Hconst int MaxSize = 10;struct Arodeint adjvex;Arode * next;templatestruct VertexNodeDat
8、aType vertex;Arode * firstedge;templateclass ALGraphpublic:ALGraph(DataType a, int n, int e);ALGraph();void DFSTraverse(int v);void BFSTraverse(int v);private:VertexNode adjlistMaxSize;int vertexNum, arum;#endif#includeusing namespace std;#includeALGraph.hextern int visitedMaxSize;templateALGraph:AL
9、Graph(DataType a, int n, int e)Arode * s;int i, j, k;vertexNum = n; arum = e;for(i = 0; i vertexNum; i+)adjlisti.vertex = ai;adjlisti.firstedge = NULL;for(k = 0; k arum; k+)cout i j;s = new Arode; s-adjvex = j;s-next = adjlisti.firstedge;adjlisti.firstedge = s;templateALGraph:ALGraph()Arode * p = NU
10、LL;for(int i = 0; i next;delete p;p = adjlisti.firstedge;templatevoid ALGraph:DFSTraverse(int v)Arode * p = NULL; int j;cout adjvex;if(visitedj = 0) DFSTraverse(j);p = p-next;templatevoid ALGraph:BFSTraverse(int v)int QMaxSize;int front = -1, rear = -1;Arode * p = NULL;cout adjvex;if(visitedj = 0)co
11、ut next;#includeusing namespace std;#includeALGraph.cppint visitedMaxSize = 0;int main()char ch = A,B,C,D,E;int i;ALGraph ALG(ch, 5, 6);for(i = 0; i MaxSize; i+)visitedi = 0;cout Depth-first traverse sequence is: ;ALG.DFSTraverse(0);cout endl;for(i = 0; i MaxSize; i+)visitedi = 0;cout Breadth-first traverse sequence is: ;ALG.BFSTraverse(0);cout endl;return 0;4. 运行与调试5. 总结与心得通过该实验,掌握了图的邻接表存储结构14 / 14