当前位置：文档库 › 图的遍历及最小生成树实验报告

图的遍历及最小生成树实验报告

实验三最小生成树问题

班级：计科1101班

学号：05

姓名：杜茂鹏

2013年5月23日

一、实验目的

掌握图的存储表示和以及图的最小生成树算法。

二、实验内容

1.实现图的存储，并且读入图的内容。

2.利用普里姆算法求网络的最小生成树。

3.实现构造生成树过程中的连通分量抽象数据类型。

4.以文本形式输出对应图的最小生成树各条边及权值。

三、实验要求

1．在上机前写出全部源程序；

2．能在机器上正确运行程序；

3．用户界面友好。

四、概要设计、

首先采用图的邻接矩阵存储结构，然后从终端输入图的顶点名称、弧以及弧的权值建立邻接矩阵，并将图存储在文件中。

然后利用已经建好的图，分别对其进行深度、广度优先遍历，一次输出遍历的顶点

最后建立此图的最小生成树，并将对应的边及权值写入文件中。

六、详细设计

实验内容(原理、操作步骤、程序代码)

#include<>

#define INFINITY INT_MAX owcost!=0&&mini>cld[i].lowcost)

{

mini=cld[i].lowcost;

s1=i;

}

return s1;

}

void CreateUDN(MGraph &G)

{

int IncInfo;

printf("请分别输入顶点数/弧数/以及弧所含信息:");

scanf("%d %d %d",&,&,&IncInfo);

getchar();

for(int i=0;i<;i++){ dj=INFINITY;

[i][j].info=NULL;

}

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

{

char v1,v2;

int w,i,j;

printf("输入一条边依附的顶点及权值:"); dj=w;

if(IncInfo)

*[i][j].info=IncInfo;

[j][i]=[i][j];

getchar();

}

dj!=INFINITY)

DFS(G,j);

}

void BFSTraverse(MGraph G,void(*Visit)(MGraph G,int v))

{

LinkQueue Q;

for(int v=0;v<;v++)

visited[v]=0;

InitQueue(Q);

for(int v=0;v<;v++)

if(!visited[v])

{

visited[v]=1;

Visit(G,v);

EnQueue(Q,[v]);

while(!QueueEmpty(Q))

{

DeQueue(Q);

for(int j=0;j<;j++)

if(!visited[j]&&[v][j].adj!=INFINITY)

{

visited[j]=1;

Visit(G,j);

EnQueue(Q,[j]);

}

void MiniSpanTree_PRIM(MGraph G,char u)

{

FILE *IN;

if((IN=fopen("","w+"))==NULL)

{

printf("file open error!");

exit(1);

}

int k=LocateVex(G,u);

for(int j=0;j<;j++)

if(j!=k){

[j].adjvex=u;

[j].lowcost=[k][j].adj;

}

[k].lowcost=0;

for(int i=1;i<;i++){

k=minimum(G,;

printf("%c%c",[k].adjvex,[k]);

int m=LocateVex(G,[k].adjvex);

printf("%d\n",[m][k].adj);

fprintf(IN,"%c,%c,%d",[k].adjvex,[k],[m][k].adj);

fputs("\n",IN);

[k].lowcost=0;

for(int j=0;j<;j++)

if[k][j].adj<[j].lowcost)

{

[j].adjvex=[k];

[j].lowcost=[k][j].adj;

}

fclose(IN);

}

void menu()

{

printf("1.生成无向网G\n");

printf("2.最小生成树\n");

printf("3.深度遍历\n");

printf("4.广度遍历\n");

printf("0.退出\n");

}

int main(void)

{

MGraph G;

int m;

{

menu();

printf("输入你想要进行的操作的序号:");

scanf("%d",&m);

getchar();

switch(m)

{

case 1:

CreateUDN(G);

break;

case 2:

char u;

u=GetVex(G,0);

MiniSpanTree_PRIM(G,u);

break;

case 3:

DFSTraverse(G,Visit);

break;

case 4:

BFSTraverse(G,Visit);

break;

case 0:

break;

default:

break;

}

}while(m);

}

七、测试结果(截图)

主界面

八、实验心得

1拼写错误节应该避免

2尽量用通俗易懂的标示符定义函数、变量

3变量应该先定义再使用

4应该从使用者的角度考虑，做出简洁的主界面

5编好一个函数时应该加注释方便以后阅读时好理解

图的遍历操作实验报告

. .. . .. .. 实验三、图的遍历操作一、目的掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。二、要求采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS 和BFS操作。三、DFS和BFS 的基本思想深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，……，Vt；再依次访问与V1，V2，……，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。四、示例程序 1．邻接矩阵作为存储结构的程序示例

#include"stdio.h" #include"stdlib.h" #define MaxVertexNum 100 //定义最大顶点数 typedef struct{ char vexs[MaxVertexNum]; //顶点表 int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表int n,e; //图中的顶点数n和边数e }MGraph; //用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) { int i,j,k; char a; printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数 scanf("%c",&a); printf("Input Vertex string:"); for(i=0;in;i++) { scanf("%c",&a); G->vexs[i]=a; //读入顶点信息，建立顶点表 }

数据结构课程设计图的遍历和生成树求解

数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码: 6014389 题目: 图的遍历和生成树求解实现年级/专业/班: 学生姓名: 学号: 开始时间: 2012 年 12 月 09 日完成时间: 2012 年 12 月 26 日课程设计成绩：指导教师签名：年月日

目录摘要 (3) 引言 (4) 1 需求分析 (5) 1.1任务与分析 (5) 1.2测试数据 (5) 2 概要设计 (5) 2.1 ADT描述 (5) 2.2程序模块结构 (7) 软件结构设计： (7) 2.3各功能模块 (7) 3 详细设计 (8) 3.1结构体定义 (19) 3.2 初始化 (22) 3.3 插入操作（四号黑体） (22) 4 调试分析 (22) 5 用户使用说明 (23) 6 测试结果 (24) 结论 (26)

摘要《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词：计算机；图；算法。

最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)

算法设计与分析课程设计报告学院计算机科学与技术专业计算机科学与技术年级2011 姓名XXX 学号 2013年5 月19 日

题目：最小生成树问题的算法实现及复杂度分析摘要：该程序操作简单，具有一定的应用性。数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法，最小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛，如邮递员送信、公路造价等问题。本设计以Visual Studio 2010作为开发平台，C/C++语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小生成树算法。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。引言：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。

图的遍历和生成树求解实现_课程设计报告

中北大学数据结构课程设计说明书 2011年12月19日

1设计目的：《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 2设计内容和要求设计内容： (1)采用合适的存储结构来创建图，并实现图的遍历；（2）计算图的最小生成树，求联通分量设计要求：（1）先任意创建一个图；（2) 图的DFS,BFS的递归和非递归算法的实现（3) 最小生成树（两个算法）的实现，求连通分量的实现（4) 要求用邻接矩阵、邻接表、十字链表多种结构存储实现 3．本设计所采用的数据结构：本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。 4.1 详细设计思想这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和

图的遍历实验报告

实验四：图的遍历题目：图及其应用——图的遍历班级：姓名：学号：完成日期：一.需求分析 1.问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。 2.基本要求：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 3.测试数据：教科书图7.33。暂时忽略里程，起点为北京。 4.实现提示：设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制，注意，生成树的边是有向边，端点顺序不能颠倒。 5.选作内容：（1）.借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。（2）.以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。二.概要设计 1.为实现上述功能，需要有一个图的抽象数据类型。该抽象数据类型的定义为： ADT Graph { 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R： R={VR} VR={ | v，w v且P(v，w)，表示从v到w得弧，谓词P(v，w)定义了弧的意义或信息} } ADT Graph 2.此抽象数据类型中的一些常量如下： #define TRUE 1 #define FALSE 0 #define OK 1 #define max_n 20 //最大顶点数 typedef char VertexType[20]; typedef enum{DG, DN, AG, AN} GraphKind; enum BOOL{False,True}; 3.树的结构体类型如下所示：

数据结构实验报告-图的遍历

数据结构实验报告实验：图的遍历一、实验目的： 1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表 2、掌握图的构造方法 3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法 4、掌握图的深度优先遍历和广度优先原理二、实验内容： 1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。 2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图 3、深度优先遍历第一步中构造的图G，输出得到的节点序列 4、广度优先遍历第一部中构造的图G，输出得到的节点序列三、实验要求： 1、无向图中的相关信息要从终端以正确的方式输入； 2、具体的输入和输出格式不限； 3、算法要具有较好的健壮性，对错误操作要做适当处理； 4、程序算法作简短的文字注释。四、程序实现及结果： 1、邻接矩阵： #include #include #define VERTEX_MAX 30 #define MAXSIZE 20 typedef struct { int arcs[VERTEX_MAX][VERTEX_MAX] ; int vexnum,arcnum; } MGraph; void creat_MGraph1(MGraph *g) { int i,j,k; int n,m; printf("请输入顶点数和边数:"); scanf("%d%d",&n,&m); g->vexnum=n; g->arcnum=m; for (i=0;iarcs[i][j]=0;

数据结构课程设计-图的遍历和生成树的求解实现说明书

******************* 实践教学 ******************* 兰州理工大学计算机与通信学院 2012年春季学期算法与数据结构课程设计题目：图的遍历和生成树的求解实现专业班级：计算机科学与技术姓名：*** 学号：1234567 指导教师：**** 成绩：

目录摘要 (3) 前言 (4) 正文 (5) 1.问题描述： (5) 2.采用类C语言定义相关的数据类型 (5) 3．各模块流程图及伪码算法 (6) 4．函数的调用关系图 (8) 5．调试分析 (9) 1.调试中遇到的问题及对问题的解决方法 (9) 2.算法的时间复杂度和空间复杂度 (9) 6.测试结果 (10) 参考文献 (14)

图是一种复杂的非线性数据结构，一个图G（Grah）由两个集合V和E 构成，图存在两种遍历方式，深度优先遍历和广度优先遍历，广度优先遍历基本思路是假设从图中某顶点U出发，在访问了顶点U之后依次访问U的各个未访问的领接点，然后分别从这些领接点出发依次访问他们的领接点，并使先访问的顶点的领接点先于后访问的顶点被访问。直至所有领接点被访问到。深度优先的基本思路是从某个顶点出发，访问此顶点，然后依次从V的未被访问的领接点出发深度优先检索土。直至图中所有顶点都被访问到。PRIM算法—KRUSKAL算法；可以对图形进行最小生成树的求解。主要问题是：（1）当给出一个表达式时，如何创建图所表达的树，即相应的逻辑结构和存储结构？（2）表达式建立好以后，如何求出其遍历？深度优先和广度优先遍历。（3）计算它的最小生成树？主要是prim算法和kruscal算法两种形式。

数据结构实验报告图实验

邻接矩阵的实现 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; } }

图的深度优先遍历实验报告

一．实验目的熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。二．实验原理深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有与v有路径相通的顶点都被访问到；若此时图有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。图的邻接表的存储表示： #define MAX_VERTEX_NUM 20 #define MAXNAME 10 typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc;

}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 三．实验容编写LocateVex函数，Create函数，print函数，main函数，输入要构造的图的相关信息，得到其邻接表并输出显示。四。实验步骤 1）结构体定义,预定义，全局变量定义。 #include"stdio.h" #include"stdlib.h" #include"string.h" #define FALSE 0 #define TRUE 1 #define MAX 20 typedef int Boolean; #define MAX_VERTEX_NUM 20

数据结构课程设计之图的遍历和生成树求解

##大学数据结构课程设计报告题目：图的遍历和生成树求解院（系）：计算机工程学院学生: 班级：学号: 起迄日期: 2011.6.20 指导教师:

2010—2011年度第 2 学期一、需求分析 1.问题描述：图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。 2.基本功能 1) 先任意创建一个图； 2) 图的DFS,BFS的递归和非递归算法的实现 3) 最小生成树（两个算法）的实现，求连通分量的实现 4) 要求用邻接矩阵、邻接表等多种结构存储实现 3.输入输出

输入数据类型为整型和字符型，输出为整型和字符二、概要设计 1.设计思路： a.图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用1表示，无边用0表示；有全图的边为权值表示，无边用∞表示。 b.图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。 c.图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。 d.图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。 e.图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。 2.数据结构设计： ADT Queue{ 数据对象：D={a i | a i ∈ElemSet,i=1,2,3……，n,n≥0} 数据关系：R1={| a i-1 ,a i ∈D,i=1,2,3,……，n} 基本操作： InitQueue(&Q) 操作结果：构造一个空队列Q。 QueueEmpty(Q) 初始条件：Q为非空队列。操作结果：若Q为空队列，则返回真，否则为假。 EnQueue(&Q,e) 初始条件：Q为非空队列。操作结果：插入元素e为Q的新的队尾元素。 DeQueue(&Q,e) 初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。}ADT Queue