数据结构实验报告图实验

数据结构实验报告图实

验

GE GROUP system office room 【GEIHUA16H-GEIHUA GEIHUA8Q8-

图实验

一， 邻接矩阵的实现

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 \"MGraph.h\"

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 << \"Please enter two vertexs number of edge: \"; 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++) }

template

if(arc[v][j] == 1 && visited[j] == 0)

DFSTraverse(j);

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 \"MGraph.h\"

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 << \"Please enter two vertexs number of edge: \"; 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 { };

template struct VertexNode {

int adjvex; ArcNode * next;

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: }; #endif ALGraph.cpp

VertexNode adjlist[MaxSize]; int vertexNum, arcNum;

#include using namespace std; #include\"ALGraph.h\"

extern int visited[MaxSize]; template

ALGraph::ALGraph(DataType a[], int n, int e){ ArcNode * s; int i, j, k;

vertexNum = n; arcNum = e; for(i = 0; i < vertexNum; i++) { adjlist[i].vertex = a[i]; adjlist[i].firstedge = NULL;

}

for(k = 0; k < arcNum; k++)

{

cout << \"Please enter the edge of the serial number of

two vertices: \"; }

template ALGraph::~ALGraph() {

}

cin >> i >> j;

s = new ArcNode; s->adjvex = j; s->next = adjlist[i].firstedge; adjlist[i].firstedge = s;

ArcNode * p = NULL;

for(int i = 0; i < vertexNum; i++) {

p = adjlist[i].firstedge;

}

}

while(p != NULL) { }

adjlist[i].firstedge = p->next; delete p;

p = adjlist[i].firstedge;

template

void ALGraph::DFSTraverse(int v) {

ArcNode * p = NULL; int j; cout << adjlist[v].vertex; visited[v] = 1;

p = adjlist[v].firstedge; while(p != NULL)

}

{ }

j = p->adjvex;

if(visited[j] == 0) DFSTraverse(j); p = p->next;

template

void ALGraph::BFSTraverse(int v) {

int Q[MaxSize];

int front = -1, rear = -1; ArcNode * p = NULL;

cout << adjlist[v].vertex; visited[v] = 1; Q[++rear] = v; while(front != rear) {

v = Q[++front];

p = adjlist[v].firstedge; while(p != NULL) {

int j = p->adjvex; if(visited[j] == 0){

cout << adjlist[j].vertex; visited[j] = 1;

Q[++rear] = j; }

ALGraph_main.cpp #include using namespace std; #include\"ALGraph.cpp\"

}

}

}

p = p->next;

int visited[MaxSize] = {0}; int main() {

char ch[] = {'A','B','C','D','E'}; int i;

ALGraph ALG(ch, 5, 6); for(i = 0; i < MaxSize; i++)

visited[i] = 0;

cout << \"Depth-first traverse sequence is: \"; ALG.DFSTraverse(0); cout << endl;

for(i = 0; i < MaxSize; i++)

visited[i] = 0;

cout << \"Breadth-first traverse sequence is: \"; ALG.BFSTraverse(0); cout << endl;

return 0;

}

4. 运行与调试 5. 总结与心得

通过该实验，掌握了图的邻接表存储结构