数据结构实验报告图实验

1、图实验一， 邻接矩阵的实现1. 实验目的（1） 掌握图的逻辑结构（2） 掌握图的邻接矩阵的存储结构（3） 验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容（1） 建立无向图的邻接矩阵存储（2） 进行深度优先遍历（3） 进行广度优先遍历3设计与编码MGraph.h#ifndef MGraph_H#define MGraph_Hconst int MaxSize = 10;template<class DataType>class MGraphpublic:MGraph(DataType a, int n, int e);MGraph()void DFSTraverse(int v

2、);void BFSTraverse(int v);private:DataType vertexMaxSize;int arcMaxSizeMaxSize;int vertexNum, arcNum;#endifMGraph.cpp#include<iostream>using namespace std;#include "MGraph.h"extern int visitedMaxSize;template<class DataType>MGraph<DataType>:MGraph(DataType a, int n, int e

3、)int i, j, k;vertexNum = n, arcNum = 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 < arcNum; k+)cout << "Please enter two vertexs number of edge: "cin >> i >> j;arcij = 1;arcji = 1;t

4、emplate<class DataType>void MGraph<DataType>:DFSTraverse(int v)cout << vertexv;visitedv = 1;for(int j = 0; j < vertexNum; j+)if(arcvj = 1 && visitedj = 0)DFSTraverse(j);template<class DataType>void MGraph<DataType>:BFSTraverse(int v)int QMaxSize;int front = -

5、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;MGraph_main.cpp#include<iostream>using namespace std;#include "MGraph.h"ext

6、ern int visitedMaxSize;template<class DataType>MGraph<DataType>:MGraph(DataType a, int n, int e)int i, j, k;vertexNum = n, arcNum = 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 < arcNum; k+)cout &l

7、t;< "Please enter two vertexs number of edge: "cin >> i >> j;arcij = 1;arcji = 1;template<class DataType>void MGraph<DataType>:DFSTraverse(int v)cout << vertexv;visitedv = 1;for(int j = 0; j < vertexNum; j+)if(arcvj = 1 && visitedj = 0)DFSTravers

8、e(j);template<class DataType>void MGraph<DataType>: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

9、 = 1;Q+rear = j;4. 运行与测试5. 总结与心得通过该实验的代码编写与调试，熟悉了邻接矩阵在图结构中的应用，在调试过程中遇到很多的问题，在解决问题过程中也使我的写代码能力得到提升二， 邻接表的实现1. 实验目的（1） 掌握图的逻辑结构（2） 掌握图的邻接表存储结构（3） 验证图的邻接表存储及其遍历操作的实现2. 实验内容（1） 建立一个有向图的邻接表存储结构（2） 对建立的有向图进行深度优先遍历（3） 对建立的有向图进行广度优先遍历3. 设计与编码ALGraph.h#ifndef ALGraph_H#define ALGraph_Hconst int MaxSize = 10;

10、struct ArcNodeint adjvex;ArcNode * next;template<class DataType>struct VertexNodeDataType vertex;ArcNode * firstedge;template<class DataType>class ALGraphpublic:ALGraph(DataType a, int n, int e);ALGraph();void DFSTraverse(int v);void BFSTraverse(int v);private:VertexNode<DataType>

11、adjlistMaxSize;int vertexNum, arcNum;#endifALGraph.cpp#include<iostream>using namespace std;#include"ALGraph.h"extern int visitedMaxSize;template<class DataType>ALGraph<DataType>:ALGraph(DataType a, int n, int e)ArcNode * s;int i, j, k;vertexNum = n; arcNum = e;for(i = 0;

12、 i < vertexNum; i+)adjlisti.vertex = ai;adjlisti.firstedge = NULL;for(k = 0; k < arcNum; k+)cout << "Please enter the edge of the serial number of two vertices: "cin >> i >> j;s = new ArcNode; s->adjvex = j;s->next = adjlisti.firstedge;adjlisti.firstedge = s;t

13、emplate<class DataType>ALGraph<DataType>:ALGraph()ArcNode * p = NULL;for(int i = 0; i < vertexNum; i+)p = adjlisti.firstedge;while(p != NULL)adjlisti.firstedge = p->next;delete p;p = adjlisti.firstedge;template<class DataType>void ALGraph<DataType>:DFSTraverse(int v)Arc

14、Node * p = NULL; int j;cout << adjlistv.vertex;visitedv = 1;p = adjlistv.firstedge;while(p != NULL)j = p->adjvex;if(visitedj = 0) DFSTraverse(j);p = p->next;template<class DataType>void ALGraph<DataType>:BFSTraverse(int v)int QMaxSize;int front = -1, rear = -1;ArcNode * p = N

15、ULL;cout << adjlistv.vertex; visitedv = 1; Q+rear = v;while(front != rear)v = Q+front;p = adjlistv.firstedge;while(p != NULL)int j = p->adjvex;if(visitedj = 0)cout << adjlistj.vertex; visitedj = 1; Q+rear = j;p = p->next;ALGraph_main.cpp#include<iostream>using namespace std;#include"ALGraph.cpp"int visitedMaxSize = 0;int main()char ch = 'A','B','C','D','E'int i;ALGraph<char> ALG(ch, 5, 6);for(i = 0; i < MaxSize; i+)visitedi = 0;cout << "Depth-first tra