数据结构图实验报告.doc

一、实验目的和要求（1）掌握图的相关概念，包括图，有向图，无向图，完全图，子图，连通图，度，入度，出度，简单回路和环等定义。（2）重点掌握图的各种存储结构，包括邻接矩阵和邻接表等。（3）重点掌握图的基本运算，包括创建图，输出图，深度优先遍历，广度优先遍历等。（4）掌握图的其他运算 ，包括最小生成树，最短路径，拓扑排序和关键路径等算法。（5）灵活运用图这种数据结构解决一些综合应用问题。二、实验内容和方法(1)实验内容：1、编写一个程序algo8-1.cpp，实现不带权图和带权图的邻接矩阵与邻接表的相互转换算法、输出邻接矩阵与邻接表的算法，并在此基础上设计一个程序exp8-1.cpp实现如下功能：建立如图1所示的有向图G的邻接矩阵，并输出；由有向图G的邻接矩阵产生邻接表，并输出；再由的邻接表产生对应的邻接矩阵，并输出。1569758453015243图12、编写一个程序algo8-2.cpp，实现图的遍历运算，并在此基础上设计一个程序exp8-2.cpp完成如下功能：输出图1所示的有向图G从顶点0开始的深度优先遍历序列（递归算法）；输出图1所示的有向图G从顶点0开始的深度优先遍历序列（非递归算法）；输出图1所示的有向图G从顶点0开始的广度优先遍历序列。3、设计一个程序exp8-3.cpp,采用邻接表存储图，并输出图8.1（a）中从指定顶点1出发的所有深度优先遍历序列。(2)实验方法：1、综合运用课本所学的知识，用不同的算法实现在不同的程序功能。2、结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。3、根据实验内容，编译程序。三、实验环境：Windows 7，Visual C+6.0三、实验过程描述文件graph.h中定义了图的邻接矩阵表示类型和邻接表表示类型，该头文件在以下三个实验中都会使用到。其代码如下：#ifndef GRAPH_H_INCLUDED#define GRAPH_H_INCLUDEDtypedef int InfoType;#define MAXV 100 /最大顶点个数#define INF 32767 /INF表示无限大/以下定义邻接矩阵类型typedef struct int no; InfoType info;VertexType;typedef struct int edgesMAXVMAXV; int n,e; VertexType vexsMAXV;MGraph;/以下定义邻接表类型typedef struct ANode int adjvex; struct ANode* nextarc; InfoType info;ArcNode;typedef int Vertex;typedef struct VNode Vertex data; ArcNode* firstarc;VNode;typedef VNode AdjListMAXV;typedef struct AdjList adjlist; int n,e;ALGraph;#endif / GRAPH_H_INCLUDED VertexType vexsMAXV;MGraph;/以下定义邻接表类型typedef struct ANode int adjvex; struct ANode* nextarc; InfoType info;ArcNode;typedef int Vertex;typedef struct VNode Vertex data; ArcNode* firstarc;VNode;typedef VNode AdjListMAXV;typedef struct AdjList adjlist; int n,e;ALGraph;#endif / GRAPH_H_INCLUDED实验源程序。一、输入如下所示程序；/文件名：exp8-1.cpp#include #include #include graph.hextern void MatToList1(MGraph, ALGraph* &);extern void ListToMat1(ALGraph*, MGraph&);extern void DispMat1(MGraph);extern void DispAdj1(ALGraph*);int main() int i,j; MGraph g,g1; ALGraph *G; int AMAXV6 = 0,5,INF,7,INF,INF,INF,0,4,INF,INF,INF, 8,INF,0,INF,INF,9,INF,INF,5,0,INF,6, INF,INF,INF,5,0,INF,3,INF,INF,INF,1,0; g.n = 6; g.e = 10; for(i=0; ig.n; i+) for(j=0; jg.n; j+) g.edgesij = Aij; printf(有向图G的邻接矩阵：n); DispMat1(g); G = (ALGraph*)malloc(sizeof(ALGraph); printf(图G的邻接矩阵转换成邻接表：n); MatToList1(g,G); DispAdj1(G); printf(图G的邻接表转换成邻接矩阵：n); ListToMat1(G,g1); DispMat1(g1); return 0;/文件名：algo8-1.cpp#include #include #include graph.h/不带权图的算法void MatToList(MGraph g, ALGraph *&G) int i,j; ArcNode *p; G = (ALGraph*)malloc(sizeof(ALGraph); for(i=0; i=0; j-) if(g.edgesij!=0) p = (ArcNode*)malloc(sizeof(ArcNode); p-adjvex = j; p-nextarc = G-adjlisti.firstarc; G-adjlisti.firstarc = p; G-n = g.n; G-e = g.e;void ListToMat(ALGraph *G,MGraph &g) int i,j; ArcNode *p; for(i=0; in; i+) for(j=0; jn; j+) g.edgesij = 0; for(i=0; in; i+) p = G-adjlisti.firstarc; while(p!=NULL) g.edgesip-adjvex = 1; p = p-nextarc; g.n = G-n; g.e = G-e;void DispMat(MGraph g) int i,j; for(i=0; ig.n; i+) for(j=0; jg.n; j+) printf(%3d,g.edgesij); printf(n); void DispAdj(ALGraph *G) int i; ArcNode *p; for(i=0; in; i+) p = G-adjlisti.firstarc; printf(%3d:,i); while(p!=NULL) printf(%3d,p-adjvex); p = p-nextarc; printf(n); /带权图的算法void MatToList1(MGraph g, ALGraph *&G) int i,j; ArcNode *p; G = (ALGraph*)malloc(sizeof(ALGraph); for(i=0; iadjlisti.firstarc = NULL; for(i=0; i=0; j-) if(g.edgesij!=0 & g.edgesij!=INF) p = (ArcNode*)malloc(sizeof(ArcNode); p-adjvex = j; p-info = g.edgesij; p-nextarc = G-adjlisti.firstarc; G-adjlisti.firstarc = p; G-n = g.n; G-e = g.e;void ListToMat1(ALGraph *G, MGraph &g) int i,j; ArcNode *p; for(i=0; in; i+) for(j=0; jn; j+) if(i=j) g.edgesij = 0; else g.edgesij = INF; for(i=0; in; i+) p = G-adjlisti.firstarc; while(p!=NULL) g.edgesip-adjvex = p-info; p = p-nextarc; g.n = G-n; g.e = G-e;void DispMat1(MGraph g) int i,j; for(i=0; ig.n; i+) for(j=0; jg.n; j+) if(g.edgesij = INF) printf(%3s,); else printf(%3d,g.edgesij); printf(n); void DispAdj1(ALGraph *G) int i; ArcNode *p; for(i=0; in; i+) p = G-adjlisti.firstarc; printf(%3d:,i); while(p!=NULL) printf(%3d(%d),p-adjvex,p-info); p = p-nextarc; printf(n); void DispAdj1(ALGraph *G) int i; ArcNode *p; for(i=0; in; i+) p = G-adjlisti.firstarc; printf(%3d:,i); while(p!=NULL) printf(%3d(%d),p-adjvex,p-info); p = p-nextarc; printf(n); 二、编译并链接程序； 三、运行程序，结果如下图： 实验源程序一、输入如下所示程序；/文件名：exp8-2.cpp#include #include #include graph.hextern void MatToList1(MGraph, ALGraph *&);extern void DispAdj1(ALGraph *G);extern void DFS(ALGraph *G,int v);extern void DFS1(ALGraph *G,int v);extern void DFS2(ALGraph *G,int v);extern void BFS(ALGraph *G,int v);int main() int i,j; MGraph g; ALGraph *G; int AMAXV6 = 0,5,INF,7,INF,INF,INF,0,4,INF,INF,INF, 8,INF,0,INF,INF,9,INF,INF,5,0,INF,6, INF,INF,INF,5,0,INF,3,INF,INF,INF,1,0; g.n = 6; g.e = 10; for(i=0; ig.n; i+) for(j=0; jg.n; j+) g.edgesij = Aij; G = (ALGraph*)malloc(sizeof(ALGraph); MatToList1(g,G); printf(图G的邻接表：n); DispAdj1(G); printf(从顶点0开始的DFS（递归算法）：n); DFS(G,0); printf(n); printf(从顶点0开始的DFS（非递归算法）：n); DFS1(G,0); printf(n); printf(从顶点0开始的BFS：n); BFS(G,0);printf(n);returne 0；/文件名：algo8-2.cpp#include #include #include graph.hint visitedMAXV;void DFS(ALGraph *G,int v) /递归深度优先遍历 ArcNode *p; visitedv = 1; printf(%3d,v); p = G-adjlistv.firstarc; while(p!=NULL) if(visitedp-adjvex=0) DFS(G,p-adjvex); p = p-nextarc; void DFS1(ALGraph *G,int v) /非递归深度优先遍历 ArcNode *p; ArcNode *StMAXV; int top = -1,w,i; for(i=0; in; i+) visitedi = 0; printf(%3d,v); visitedv = 1; top+; Sttop = G-adjlistv.firstarc; while(top-1) p = Sttop; top-; while(p!=NULL) w = p-adjvex; if(visitedw=0) printf(%3d,w); visitedw = 1; top+; Sttop = G-adjlistw.firstarc; break; p = p-nextarc; printf(n);void BFS(ALGraph *G,int v) ArcNode *p; int queueMAXV,front = 0,rear = 0; int visitedMAXV; int w,i; for(i=0;in;i+) visitedi = 0; printf(%3d,v); visitedv = 1; rear = (rear+1) % MAXV; queuerear = v; while(front!=rear) front = (front+1)%MAXV; w = queuefront; p = G-adjlistw.firstarc; while(p!=NULL) if(visitedp-adjvex=0) printf(%3d,p-adjvex); visitedp-adjvex = 1; rear = (rear+1) % MAXV; queuerear = p-adjvex; p = p-nextarc; printf(n);void MatToList1(MGraph g, ALGraph *&G) int i,j; ArcNode *p; G = (ALGraph*)malloc(sizeof(ALGraph); for(i=0; iadjlisti.firstarc = NULL; for(i=0; i=0; j-) if(g.edgesij!=0 & g.edgesij!=INF) p = (ArcNode*)malloc(sizeof(ArcNode); p-adjvex = j; p-info = g.edgesij; p-nextarc = G-adjlisti.firstarc; G-adjlisti.firstarc = p; G-n = g.n; G-e = g.e;void DispAdj1(ALGraph *G) int i; ArcNode *p; for(i=0; in; i+) p = G-adjlisti.firstarc; printf(%3d:,i); while(p!=NULL) printf(%3d(%d),p-adjvex,p-info); p = p-nextarc; printf(n); top+; Sttop = G-adjlistw.firstarc; break; p = p-nextarc; printf(n);void BFS(ALGraph *G,int v) ArcNode *p; int queueMAXV,front = 0,rear = 0; int visitedMAXV; int w,i; for(i=0;in;i+) visitedi = 0; printf(%3d,v); visitedv = 1; rear = (rear+1) % MAXV; queuerear = v; while(front!=rear) front = (front+1)%MAXV; w = queuefront; p = G-adjlistw.firstarc; while(p!=NULL) if(visitedp-adjvex=0) printf(%3d,p-adjvex); visitedp-adjvex = 1; rear = (rear+1) % MAXV; queuerear = p-adjvex; p = p-nextarc; printf(n);void MatToList1(MGraph g, ALGraph *&G) int i,j; ArcNode *p; G = (ALGraph*)malloc(sizeof(ALGraph); for(i=0; iadjlisti.firstarc = NULL; for(i=0; i=0; j-) if(g.edgesij!=0 & g.edgesij!=INF) p = (ArcNode*)malloc(sizeof(ArcNode); p-adjvex = j; p-info = g.edgesij; p-nextarc = G-adjlisti.firstarc; G-adjlisti.firstarc = p; G-n = g.n; G-e = g.e;void DispAdj1(ALGraph *G) int i; ArcNode *p; for(i=0; in; i+) p = G-adjlisti.firstarc; printf(%3d:,i); while(p!=NULL) printf(%3d(%d),p-adjvex,p-info); p = p-nextarc; printf(n); void MatToList1(MGraph g, ALGraph *&G) int i,j; ArcNode *p; G = (ALGraph*)malloc(sizeof(ALGraph); for(i=0; iadjlisti.firstarc = NULL; for(i=0; i=0; j-) if(g.edgesij!=0 & g.edgesij!=INF) p = (ArcNode*)malloc(sizeof(ArcNode); p-adjvex = j; p-info = g.edgesij; p-nextarc = G-adjlisti.firstarc; G-adjlisti.firstarc = p; G-n = g.n; G-e = g.e;void DispAdj1(ALGraph *G) int i; ArcNode *p; for(i=0; in; i+) p = G-adjlisti.firstarc; printf(%3d:,i); while(p!=NULL) printf(%3d(%d),p-adjvex,p-info); p = p-nextarc; printf(n); 二、对程序进行编译链接；三、运行该程序，结果如图实验源程序。一、输入如下所示程序；#include #include #include graph.hextern void MatToList(MGraph,ALGraph *&);extern void DispAdj(ALGraph *);int visitedMAXV;void DFSALL(ALGraph *G,int v,int path,int d) ArcNode *p; visitedv = 1; pathd = v; d+; if(d=G-n) for(int k=0;kadjlistv.firstarc; while(p!=NULL) if(visitedp-adjvex=0) DFSALL(G,p-adjvex,path,d); p = p-nextarc; visitedv = 0;int main() int pathMAXV,i,j,v=1; MGraph g; ALGraph *G; g.n = 5; g.e = 8; int AMAXVMAXV = 0,1,0,1,1,1,0,1,1,0,0,1,0,1,1, 1,1,1,0,1,1,0,1,1,0; for(i=0;ig.n;i+) for(j=0;jg.n;j+) g.edgesij = Aij; MatToList(g,G); for (i=0;ig.n;i+) visitedi = 0; printf(图G的邻接表： n); DispAdj(G); printf(从顶点%d出发的所有深度优先序列：n,v); DFSALL(G,v,path,0); printf(n); return 0;void MatToList(MGraph g, ALGraph *&G) int i,j; ArcNode *p; G = (ALGraph*)malloc(sizeof(ALGraph); for(i=0; iadjlisti.firstarc = NULL; for(i=0; i=0; j-) if(g.edgesij!=0) p = (ArcNode*)malloc(sizeof(ArcNode); p-adjvex = j; p-nextarc = G-adjlisti.firstarc; G-adjlisti.firstarc = p; G-n = g.n; G-e = g.e;void DispAdj(ALGraph *G) int i; ArcNode *p; for(i=0; in; i+) p = G-adjlisti.firstarc; printf(%3d:,i); while(p!=NULL) printf(%3d,p-adjvex); p = p-nextarc; printf(n); if(visitedp-adjvex=0) DFSALL(G,p-adjvex,path,d); p = p-nextarc; visitedv = 0;int main() int pathMAXV,i,j,v=1; MGraph g; ALGraph *G; g.n = 5; g.e = 8; int AMAXVMAXV