数据结构图实验报告-(2).doc

一、实验目得与要求（1)掌握图得相关概念，包括图,有向图,无向图，完全图，子图,连通图,度,入度，出度,简单回路与环等定义.（2）重点掌握图得各种存储结构，包括邻接矩阵与邻接表等。(3）重点掌握图得基本运算，包括创建图,输出图,深度优先遍历,广度优先遍历等.（4）掌握图得其她运算,包括最小生成树,最短路径，拓扑排序与关键路径等算法。(5)灵活运用图这种数据结构解决一些综合应用问题。二、实验内容与方法（1）实验内容:、编写一个程序alo8-1、cpp，实现不带权图与带权图得邻接矩阵与邻接表得相互转换算法、输出邻接矩阵与邻接表得算法，并在此基础上设计一个程序exp8、cp实现如下功能:建立如图1所示得有向图G得邻接矩阵,并输出;由有向图得邻接矩阵产生邻接表,并输出;再由得邻接表产生对应得邻接矩阵,并输出。1569758453015243图12、编写一个程序lgo82、cpp，实现图得遍历运算,并在此基础上设计一个程序xp82、cpp完成如下功能：输出图1所示得有向图从顶点0开始得深度优先遍历序列（递归算法）；输出图所示得有向图G从顶点0开始得深度优先遍历序列（非递归算法);输出图1所示得有向图G从顶点0开始得广度优先遍历序列。、设计一个程序exp83、cpp,采用邻接表存储图，并输出图8、1(a）中从指定顶点1出发得所有深度优先遍历序列。(2)实验方法:1、综合运用课本所学得知识，用不同得算法实现在不同得程序功能.2、结合指导老师得指导，解决程序中得问题，正确解决实际中存在得异常情况，逐步改善功能。3、根据实验内容，编译程序。三、实验环境：Winows7,VisulC+6、0三、实验过程描述文件raph、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 <stdio、h>#include <malloc、h>#include "graph、h"extern 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; i<g、n; i+) for(j=0; j<g、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 <stdio、h>#include <malloc、h>#include "graph、h"/不带权图得算法void MatToList(MGraph g, ALGraph *&G) int i,j; ArcNode *p; G = (ALGraph*)malloc(sizeof(ALGraph); for(i=0; i<g、n; i+) for(j = g、n-1; j>=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; i<G->n; i+) for(j=0; j<G->n; j+) g、edgesij = 0; for(i=0; i<G->n; 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; i<g、n; i+) for(j=0; j<g、n; j+) printf("%3d",g、edgesij); printf("n"); void DispAdj(ALGraph *G) int i; ArcNode *p; for(i=0; i<G->n; 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; i<g、n;i+) G->adjlisti、firstarc = NULL; for(i=0; i<g、n; i+) for(j=g、n-1; j>=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; i<G->n; i+) for(j=0; j<G->n; j+) if(i=j) g、edgesij = 0; else g、edgesij = INF; for(i=0; i<G->n; 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; i<g、n; i+) for(j=0; j<g、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; i<G->n; 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; i<G->n; 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 <stdio、h>#include <malloc、h>#include "graph、h"extern 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; i<g、n; i+) for(j=0; j<g、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 <stdio、h>#include <malloc、h>#include "graph、h"int 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; i<G->n; 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;i<G->n;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; i<g、n;i+) G->adjlisti、firstarc = NULL; for(i=0; i<g、n; i+) for(j=g、n-1; j>=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; i<G->n; 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;i<G->n;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; i<g、n;i+) G->adjlisti、firstarc = NULL; for(i=0; i<g、n; i+) for(j=g、n-1; j>=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; i<G->n; 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; i<g、n;i+) G->adjlisti、firstarc = NULL; for(i=0; i<g、n; i+) for(j=g、n-1; j>=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; i<G->n; i+) p = G->adjlisti、firstarc; printf("%3d:",i); while(p!=NULL) printf("%3d(%d)",p->adjvex,p->info); p = p->nextarc; printf("n"); 二、对程序进行编译链接；三、运行该程序,结果如图实验源程序。一、输入如下所示程序;#include <stdio、h>#include <malloc、h>#include "graph、h"extern 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;k<d;k+) printf("%2d",pathk); printf("n"); p = G->adjlistv、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;i<g、n;i+) for(j=0;j<g、n;j+) g、edgesij = Aij; MatToList(g,G); for (i=0;i<g、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; i<g、n; i+) G->adjlisti、firstarc = NULL; for(i=0; i<g、n; i+) for(j = g、n-1; j>=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; i<G->n; 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; visi