数据结构实验报告--图实验

图实验 一，邻接矩阵的实现

1. 实验目的

（1） 掌握图的逻辑结构

（2） 掌握图的邻接矩阵的存储结构

（3） 验证图的邻接矩阵存储及其遍历操作的实现 2. 实验内容

（1） 建立无向图的邻接矩阵存储 （2） 进行深度优先遍历 （3） 进行广度优先遍历 3．设计与编码 MGraph.h

#ifndef MGraph_H #define MGraph_H

const int MaxSize = 10;

template class MGraph {

public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; };

#endif

MGraph.cpp

#include using namespace std; #include \

extern int visited[MaxSize];

template

MGraph::MGraph(DataType a[], int n, int e)

{ int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << \ cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } }

template

void MGraph::DFSTraverse(int v) { cout << vertex[v]; visited[v] = 1; for(int j = 0; j < vertexNum; j++) if(arc[v][j] == 1 && visited[j] == 0) DFSTraverse(j); }

template

void MGraph::BFSTraverse(int v) { int Q[MaxSize]; int front = -1, rear = -1; cout << vertex[v]; visited[v] = 1; Q[++rear] = v; while(front != rear) { v = Q[++front]; for(int j = 0;j < vertexNum; j++) if(arc[v][j] == 1 && visited[j] == 0){ cout << vertex[j]; visited[j] = 1;

Q[++rear] = j; } } }

MGraph_main.cpp

#include using namespace std; #include \

extern int visited[MaxSize];

template

MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << \ cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } }

template

void MGraph::DFSTraverse(int v) { cout << vertex[v]; visited[v] = 1; for(int j = 0; j < vertexNum; j++) if(arc[v][j] == 1 && visited[j] == 0) DFSTraverse(j); }

template

void MGraph::BFSTraverse(int v) { int Q[MaxSize]; int front = -1, rear = -1; cout << vertex[v]; visited[v] = 1; Q[++rear] = v; while(front != rear) { v = Q[++front]; for(int j = 0;j < vertexNum; j++) if(arc[v][j] == 1 && visited[j] == 0){ cout << vertex[j]; visited[j] = 1; Q[++rear] = j; } } }

4. 运行与测试

5. 总结与心得

通过该实验的代码编写与调试，熟悉了邻接矩阵在图结构中的应用，在调试过程中遇到很多的问题，在解决问题过程中也使我的写代码能力得到提升

二，邻接表的实现

1. 实验目的

（1） 掌握图的逻辑结构

（2） 掌握图的邻接表存储结构

（3） 验证图的邻接表存储及其遍历操作的实现 2. 实验内容

（1） 建立一个有向图的邻接表存储结构 （2） 对建立的有向图进行深度优先遍历 （3） 对建立的有向图进行广度优先遍历 3. 设计与编码

ALGraph.h

#ifndef ALGraph_H #define ALGraph_H const int MaxSize = 10;

struct ArcNode {

int adjvex;

ArcNode * next; };

template struct VertexNode {

DataType vertex; ArcNode * firstedge; };

template class ALGraph {

public:

ALGraph(DataType a[], int n, int e); ~ALGraph();

void DFSTraverse(int v); void BFSTraverse(int v); private:

VertexNode adjlist[MaxSize]; int vertexNum, arcNum; }; #endif

ALGraph.cpp