当前位置：文档之家› 数据结构实验五---图的遍历及其应用实现

数据结构实验五---图的遍历及其应用实现

实验五图的遍历及其应用实现

一、实验目的

1．熟悉图常用的存储结构。

2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。

3．会用图的遍历解决简单的实际问题。

二、实验内容

[题目] ：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。

三、实验步骤

（一）、数据结构与核心算法的设计描述：

本实验主要在于图的基本操作，关键是图的两种遍历，仔细分析图的遍历的特点，不难发现，其符合递归的特点，因此可以采用递归的方法遍历。本实验图的存储结构主要采用邻接表，总共分为四个模块：图的创建、位置的查找、深度优先遍历、广度优先遍历。

以下是头文件中数据结构的设计和相关函数的声明：

#include

#nclude

#define OVERFLOW -2

#define MAX_VERTEX_NUM 50 //最大顶点数

#define MAXQSIZE 100

# define OK 1

typedef int VRType;

typedef int InfoType;

typedef int QElemType;

typedef enum{DG,DN,UDG,UDN}GraphKind;

typedef struct ArcNode // 弧结点

{

int adjvex; //邻接点域，存放与Vi邻接的点在表头数组中的位置

struct ArcNode *nextarc; //链域指向vi的下一条边或弧的结点，

InfoType *info; //定义与弧相关的权值，无权则为0 }ArcNode;

typedef struct VNode //表头结点

{

char vexdata; //存放顶点信息

struct ArcNode *firstarc; //指示第一个邻接点

}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct

{ //图的结构定义

AdjList vertices; //顶点向量

int vexnum, arcnum; //vexnum为顶点数arcnum为弧或边的个数GraphKind kind; // 图的种类标志}MGraph;

typedef struct Queue //构建循环队列

{

QElemType *base;

int front;

int rear;

}Queue;

void CreateGraph(MGraph &G); //图的创建

void DFSTraverse(MGraph &G) ; //深度优先遍历

void BFSTraverse(MGraph &G); //广度优先遍历

int LocateVex(MGraph &G, char &v);//查找顶点v的位置

（二）、函数调用及主函数设计

void main()

{

int x;

MGraph G;

CreateGraph(G);

cout<<"创建图成功!"<

cout<<"1 深度优先搜索"<

cin>>x;

if(x==1)

{

DFSTraverse(G);

cout<<"深度优先搜索结束!"<

}

else if(x==2)

{

BFSTraverse(G);

cout<<"广度优先搜索结束!"<

}

else

cout<<"输入有误!"<

}

（三）、实验总结

由于图的基本操作在图这一章节中起着很主要的作用，所以在实验前就对实验做了充分的准备，实验的成功核心在于两种遍历的实现，因此只有充分理解遍历算法的精髓，才能更好的做好实验。尽管实验过程中不同模块遇到了不同程度的困难，但是经过详细的设计和反复的测试、调试，实验最终结果达到了实验的预期结果。

四、主要算法流程图及程序清单

1、主要算法流程图：

DFS（BFS同DFS类似，故不再列举）

2、程序清单

图的创建模块：

void CreateGraph(MGraph &G)

{ // 生成图G的存储结构-邻接表

int i=0,j=0,k; cout<<"\n请输入顶点的数目、边的数目" cin>>G.vexnum>>G.arcnum>>m; // 输入顶点数、边数和图类 cout<<"\t\t请依次输入各个顶点的数值:";

for(i=0;i

{

cin>>G.vertices[i].vexdata;

G.vertices[i].firstarc=NULL;

}

char sv,tv;

cout<<"\t\t请依次输入各边的始点和终点："<

for (k=0; k

cout<<"请输入第"<

cin>>sv;

cout<<"请输入第"<

cin>>tv;

i=LocateVex(G, sv);

cout<<"请输入第"<

j=LocateVex(G, tv);

cout<<"请输入第"<

ArcNode *p;

p=(ArcNode *)malloc(sizeof(ArcNode));

if(!p)

{

cout<<"Overflow!";

}

p->adjvex=j;

p->nextarc=G.vertices[i].firstarc;

p->info=NULL;

G.vertices[i].firstarc=p;

if(G.vertices[i].firstarc==NULL)

cout<<"error!";

}

◆查找位置模块：

int LocateVex(MGraph &G, char &v)

{

int m;

for(m=0; m

if(G.vertices[m].vexdata==v)

return m;

}

◆深度优先遍历模块：

void DFS(MGraph &G,int v,int *visited); //函数的声明

void DFSTraverse(MGraph &G) // 对图 G 作深度优先遍历{

int v;

int visited[MAX_VERTEX_NUM];

for (v=0; v

visited[v] =0; // 访问标志数组初始化

for (v=0; v

if (!visited[v])

DFS(G,v,visited); // 对尚未访问的顶点调用DFS }

void DFS(MGraph &G,int v,int *visited)

{

int w;

char z;

visited[v]=1;

cout<";

for(z=G.vertices[v].vexdata;G.vertices[v].firstarc!=NULL;

w=G.vertices[v].firstarc->adjvex,

G.vertices[v].firstarc=G.vertices[v].firstarc->nextarc) if(visited[v]==0)

DFS(G,w,visited);

}

广度优先遍历模块：

int InitQueue(Queue &Q) //队列的初始化

{

Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));

if(!Q.base)

{ cout<

Q.front=Q.rear=0;

return (OK);

}

int EnQueue(Queue &Q,QElemType e) //入队

{

if((Q.rear+1)%MAXQSIZE==Q.front)

{ cout<<"队满!"<

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE;

return (OK);

}

int DeQueue(Queue &Q,QElemType &e) //出队

{

if(Q.front==Q.rear)

{ cout<<"队满!"<

e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;

return (e);

}

int QueueEmpty(Queue &Q) //判断队列是否为空

{

if(Q.front==Q.rear) return (OK);

else return (0);

}

void BFSTraverse(MGraph &G)

{

int v,w,u; int visited[MAX_VERTEX_NUM];

Queue Q;

InitQueue(Q);

for(v=0;v

if(visited[v]==0)

{

visited[v]=1;

cout<";

EnQueue(Q,v);

while(!QueueEmpty(Q))

{

DeQueue(Q,u);

if(!visited[u])

{

visited[u]=1;

cout<";

}

ArcNode* p;

p=G.vertices[u].firstarc;

for(w=u;p!=NULL;w=p->adjvex,p=p->nextarc)

{

if(!visited[w])

EnQueue(Q,w);

}

实验五图的存储与遍历

实验四图的存储、遍历与应用 1、实验目的 1）熟悉图的邻接矩阵和邻接表的两种常用存储结构 2）掌握两种常用存储方式下深度优先遍历(dfs)和广度优先遍历（BFS）操作的实现及其应用。 3）进一步掌握递归算法的设计方法。 2、实验内容 1）图的两种存储结构实现：（1）邻接矩阵存储：用一个一维数组来存储顶点信息，用一个二维数组存储用于表示顶点间相邻的关系（边）（2）邻接表存储：用一个一维数组来存储顶点信息，用一个链表表示与顶点相连的边。表示法类似于树的孩子链表表示法。 2）图的遍历（1）对以邻接矩阵为存储结构的图进行 DFS和 BFS遍历：建立一个图的邻接矩阵表示，输出以某顶点为起始点的DFS和BFS序列。实现提示：图的DFS遍历可通过递归调用或用栈来实现。其思想是：只要当前结点未访问过，就访问该结点，沿着其一条分支深入下去，每深入一个未访问过的结点，就访问这个结点，然后从这个结点继续进行DFS遍历。在这一过程中，若深入时遇到一个已访问过的结点，则查找是否有与这个结点相邻的下一个未访问过的结点。若有则继续深人，否则将退回到这个结点的前一个结点，再找下一个相邻的本访问过的结点，……如此进行下去，直到所有的结点都被访问过。BFS 遍历可利用队列来帮助实现，也可以用栈。实现方法与二叉树的层次遍历类似。（2）对以邻接表为存储结构的图进行DFS和BFS遍历：以邻接表为存储结构，实现图的DFS和BFS遍历，输出以某顶点为起始点的DFS和BFS序列。实现提示：以邻接表为存储结构的图的DFS和BFS算法的实现思想与以邻接矩阵为存储结构的实现是一样的。只是由于图的存储形式不同。而具体到取第一个邻接点和下一个邻接点的语句表示上有所差别而已。（3）测试数据：自己设计测试用的图，给出其邻接矩阵存储表示。也可以用如下图作为测试数据。

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

数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码: 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)

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

数据结构实验五矩阵的压缩存储与运算学习资料

数据结构实验五矩阵的压缩存储与运算

第五章矩阵的压缩存储与运算【实验目的】 1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现； 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算； 3. 加深对线性表的顺序存储和链式结构的理解。第一节知识准备矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。一、特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。问题已经转化为：已知二维矩阵A[i，j]，如图5-1，我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里： k=i(i+1)/2+j (i≥j) 图5-1 下三角矩阵 a00 a10 a11 a20 … an-1,0 … an-1,n-1

k= 0 1 2 3 …n(n- 1)/2 …n(n+1)/2-1 图5-2下三角矩阵的压缩存储反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum= > k的最小整数），j= 。 2. 三对角矩阵在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。图5-3 三对角矩阵A 与下三角矩阵的存储一样，我们也可以用一个一维数组ma[0..3n-2]来存放三对角矩阵A，其对应关系见图5-4。 a00 a01 a10 a11 a12 … an-1,n-2 an-1,n-1 k= 0 1 2 3 4 … 3n-3 3n-2 图5-4下三角矩阵的压缩存储 A中的一对下标(i,j)与ma中的下标k之间有如下的关系：公式中采用了C语言的符号，int()表示取整，‘%’表示求余。

图的遍历实验报告

实验四：图的遍历题目：图及其应用——图的遍历班级：姓名：学号：完成日期：一.需求分析 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;

数据结构实验五图子系统

数据结构实验五图子系统实验五实验题目:图子系统指导老师:王春红专业班级:计算机科学与技术系1105班姓名:李慧2011100521杜丽20111005122 白莹2011100523王媛2011100529 2013年 5月23日实验类型综合实验室_软件实验室一__ 一、实验题目 1 图子系统二、实验目的和要求 ,(掌握图的存储思想及其存储实现 ,(掌握图的深度、广度优先遍历算法思想及其程序实现 ,(掌握图的常见应用算法的思想及其程序实现。三、实验内容实验内容二:所有顶点对的最短路径 1(设置4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。现在要求从这4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。 2(设计分析

用有向加权图表示的交通图中，有向边表示第i个村庄和第j个村庄之间有道路，边上的权表示这条道路的长度。该问题的实质是求解任意两顶点间的最短路径问题。即求出每个顶点到其他顶点的最短路径的最大值，最大值最小的顶点作为医院所在村庄。 3(结构类型定义 typedef char vextype;/*顶点数据类型*/ typedef int edgetype;/*边数据类型*/ typedef struct { vextype vex[maxsize]; edgetype arc[maxsize][maxsize]; int vexnum,arcnum; }Mgraph; 小组分工: 组长:王媛定义结构体和主函数组员:李慧 void juzhen(Mgraph *G) 白莹、杜丽void panduan(Mgraph *G) 四、实验步骤程序如下: #include #include #define max 100 #define min 0 typedef int edgetype;

数据结构实验---图的储存与遍历

学号：姓名：实验日期： 2016.1.7 实验名称：图的存贮与遍历一、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。二、实验内容与实验步骤题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。测试数据：如图所示题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。测试数据：如图所示 V0 V1 V2 V3 V4 三、附录：在此贴上调试好的程序。 #include #include #include V0 V1 V4 V3 V2 ??? ? ??? ? ????????=010000000101010 1000100010A 1 0 1 0 3 3 4

#define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;in;i++) scanf("%s",&(GA->vex[i][0]),&(GA->vex[i][1])); for (i = 0;in;i++) for (j = 0;jn;j++) GA->edge[i][j] = 0; for (k = 0;ke;k++) { printf ("请输入第%d条边的顶点位置(i,j)和权值(用逗号隔开)：",k+1); scanf ("%d,%d,%d",&i,&j,&w); GA->edge[i][j] = w; } return(GA); } void dfs(Graph *GA, int v) { int i; printf("%c%c\n",GA->vex[v][0],GA->vex[v][1]); visited[v]=1;

数据结构实验报告5(电大)

实验报告五查找（学科：数据结构）姓名单位班级学号实验日期成绩评定教师签名批改日期实验名称：实验五查找 5.1 折半查找【问题描述】某班学生成绩信息表中，每个学生的记录已按平均成绩由高到低排好序，后来发现某个学生的成绩没有登记到信息表中，使用折半查找法把该同学的记录插入到信息表中，使信息表中的记录仍按平均成绩有序。【基本信息】（1）建立现有学生信息表，平均成绩已有序。（2）输入插入学生的记录信息。（3）用折半查找找到插入位置，并插入记录。【测试数据】自行设计。【实验提示】（1）用结构数组存储成绩信息表。（2）对记录中的平均成绩进行折半查找。【实验报告内容】设计程序代码如下: #include #include #define N 5 struct student{ char name[10]; float avg; } void insort(struct student s[],int n) { int low,hight,mid,k; char y[10]; float x;

low=1; hight=n; strcpy(y,s[0].name ); x=s[0].avg ; while(low<=hight) { mid=(low+hight)/2; if(x>s[mid].avg ) hight=mid-1; else low=mid+1; } for(k=0;k

数据结构图的遍历

#include"stdlib.h" #include"stdio.h" #include"malloc.h" #define INFINITY 32767 #define MAX_VERTEX_NUM 20 typedef enum{FALSE,TRUE}visited_hc; typedef enum{DG,DN,UDG,UDN}graphkind_hc; typedef struct arccell_hc {int adj; int*info; }arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {char vexs[MAX_VERTEX_NUM]; adjmatrix_hc arcs; int vexnum,arcnum; graphkind_hc kind; }mgraph_hc; typedef struct arcnode_hc {int adjvex; struct arcnode_hc *nextarc; int*info; }arcnode_hc; typedef struct vnode_hc {char data; arcnode_hc *firstarc; }vnode_hc,adjlist_hc[MAX_VERTEX_NUM]; typedef struct {adjlist_hc vertices; int vexnum,arcnum; graphkind_hc kind; }algraph_hc; int locatevex_hc(mgraph_hc*g,char v) {int i,k=0; for(i=0;ivexnum;i++) if(g->vexs[i]==v){k=i;i=g->vexnum;} return(k);}

数据结构实验——查找算法的实现

实验五查找算法实现

1、实验目的熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法，比较它们的平均查找长度。 2、问题描述查找表是数据处理的重要操作，试建立有100个结点的二叉排序树进行查找，然后用原数据建立AVL树，并比较两者的平均查找长度。 3、基本要求（1）以链表作为存储结构，实现二叉排序树的建立、查找和删除。（2）根据给定的数据建立平衡二叉树。 4、测试数据随即生成 5、源程序 #include<> #include<> #include<> #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)>(b)) typedef int Keytype; typedef struct { Keytype key; //关键字域 }ElemType; typedef struct BSTnode { ElemType data; int bf; struct BSTnode *lchild,*rchild; }BSTnode,*BSTree; void InitBSTree(BSTree &T) {T=NULL; } void R_Rotate(BSTree &p) {BSTnode *lc; lc=p->lchild; p->lchild=lc->rchild; lc->rchild=p; p=lc; } void L_Rotate(BSTree &p) {BSTnode *rc; rc=p->rchild; p->rchild=rc->lchild;

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

##大学数据结构课程设计报告题目：图的遍历和生成树求解院（系）：计算机工程学院学生: 班级：学号: 起迄日期: 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