-
数据结构课程设计
--
历和生成树求解
图的遍
图的遍历和生成树求解
摘要：
图是一种比线形表和树更为复杂的数据结构。在图形结构中，节点之
间
的关系可以是任意的，图中任意两个数据元素之间都可能相关。本程序是采
用邻接矩阵、
邻接表结构存储来实现对图的存储。采用邻接矩阵即为数组表示
法，邻接表是图的一种链
式存储结构。对图的遍历分别采用了广度优先遍历和
深度优先遍历。图的最小生成树基于
图的两种存储结构，采用
Prim
算法和
Kruskal
算法对图的最小生成树进行求解。
关键词：
图；存储结构；遍历
；最小生成树
目
录
1.
设计
背景
………………………………………………………
1
1.1
课程设计目的………………………………………………
1
1.2
题目要求………………………………
……………………
1
2.
设计方案<
/p>
………………………………………………………
1
2.1
设计方法……………………………………………………
1
2.2
方法实现………………………………………
……………
2
3.
方案实施
………………………………………………………
3
3.1
采用的数据结构说明及类型的定义…………………
……
3
3.2
函数功能描述及相关函
数的实现…………………………
5
3.3
程序中需说明的地方，
如用到的宏及代表的意义………
16
4.
结果与结论
…………………………………………………
17
4.1
测
试
数
据
及
测
试
结
果………………………………………
17
4.2
实
验
结
论……………………………………………………
19
5.
收获与致谢
…………………………………………………
19
6.
参
考
文
献
………………………………………………
……
20
图的遍历和生成树求解
1.
设计背景
1.1
课程设计目的
通过本课程设计，加深对《面向对象程序设计
C++
》
课程所学知识的理解，
熟练掌握和巩固
C++
< br>语言的基本知识和语法规范
,
掌握使用面向对象程序设计
语
言
C++
，或面向对象开发平台
Visual C++
等
,
培养调查研究、查阅技术文献、资
料、手册以及编写技术文献的能力。学会编制
结构清晰、风格良好的
C++
语言程
序
，从而具备利用计算机编程分析解决综合性实际问题的初步能力。
1.2
题目要求
课程设计是培养学生综合运用所学知识
,
发现
,
提出
,
分析和解决实际问
题
,
锻炼实践能力的重要环节
,
是对学生实际工作能力的具体训练和考察过程
.
通
过课程设计，巩固和加深对队列以及图等理论知识的理解；掌握现实复杂问题
的分析建模和解决方法，掌握包括问题描述、系统分析、设计建模、代码实现、
结果分析等的方法；提高利用计算机分析解决综合性实际问题的基本能力；锻
炼个人动手能力，历练自身素质。
2.
设计方案
2.1
设计方法
2.1.1
问题的分析和结构的设计思路
1
）
图的遍
历和生成树求解所有功能：图的生成、图的遍历、最小生成树求
解。
2
）
需要创建所有图的存储结构
(
邻接矩阵存储结构和邻接表存储结
构
)
。
3
）程序设计的目的是通过屏幕上输出的提示语句，进行相应的操作
。
4
）选择适当的算法，实现图的遍
历和最小生成树的求解等功能。
5
）
选择适当的变量，来表示图相应的顶点、边、边的权值等信息。
6
）当输入的信息出错时，程序应给错误信息提示，使程序设计得全面
周密。
2.1.2
图的遍历
和生成树求解的算法思想及设计
-
1 -
图的遍历和生成树求解
1
）
由于图
的存储结构不同，故采用邻接矩阵和邻接表两种存储结构建
立图。
2
）对图的深度遍历基于邻接矩阵，广度遍历基于邻接表。
<
/p>
3
）基于邻接矩阵存储结构，用
prim
算法求图的最小生成树。
4
）基于邻接表存储结构，用
Kruskal
算法求图的最小生成树。
5
）综合<
/p>
1
、
2
、
3
三点因素，可以采用队列来实现对图的广度优先遍历的
算法，其示意图如下：
Q.f
ne
da
ne
其中：
1.
Q
.front
为
队
头
指
针
,
为队尾指针
2.
d
ata
域存图的边权值和顶
Q.r
da
ne
6
）图遍历和生成树求解的总体结构框图如下：
图
的
遍
历
和
生
建立邻接矩
阵
输出邻接矩阵
BFS
遍历
建立邻接表
输出邻接表
DFS
遍历
Prim
求最小生成
Kruskal
求
最小
- 2 -
图的遍历和生成树求解
2.2
方法实现
2.2.1
创建结点
1
）建立队列
LinkQueue
，以及队头指针
front
、队尾指针
rear
。
2)
建立图的存储类型
MGraph,
以及顶点向量
vexs[]
。
3
)
建立图的邻接矩阵
AdjMatrix[][]
，以及边的权值。
4)
建
立图的邻接表
ALGraph,
以及邻接表头结点的类型
AdjList[]
，弧的结
点结构类型
ArcNode
。
2.2.2
编写函数
建立具体的功能实现函数，如初始化、录入、输出等。
1.
基于邻接矩阵创建图
CreateUDN
(MGraph &G,AdjMatrix &GA)
2.
基于邻接表建立图
CreateALGraph(ALGraph &G)
3.
邻接矩阵的输出
Display(MGra
ph G,AdjMatrix GA)
4.
邻接表的输出<
/p>
DisplayG(ALGraph G)
5.
基于邻接矩阵图进行深度优先遍历
DFS1(MGraph G,int
n,int v)
6.
对结点队列初始化
InitQueue (LinkQueue &Q)
7.
判断队列是否为空
QueueEmpty (LinkQueue Q)
8.
顶点信息入队
EnQueue
(LinkQueue &Q,int e)
9.
顶点信息出队
DeQueue
(LinkQueue &Q,int &e)
10.
基于邻
接表对图进行广度优先遍历
BFS(ALGraph G,int v)
求生成树
MiniSpanTree_PRIM(M
Graph G,AdjMatrix GA,VertexType u)
l
求生成树
Kruskal(ALGraph G)
13.
求
顶
点
在
图
中
位<
/p>
置
LocateVex(MGraph
G,VertexType
u)
，<
/p>
LocateVexG(ALGraph
G
,vertexType e)
14.
主函数
main()
3.
方案实施
3.1
采用的数据结构说明及类型的定义
1
．邻接矩阵的存储表示如下
typedef struct ArcCell
{
- 3 -
图的遍历和生成树求解
VRType adj;
//VR
Type
是顶点关系类型，对无权图，用
0
和
1
；对有权图，
则为权值类型<
/p>
InfoType *info;
//
该弧相关信息的指针
(
可无
)
}ArcCell,AdjMatrix[MAX_VERTEX
_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType
vexs[MAX_VERTEX_NUM];//
顶点向量
AdjMatrix
arcs;//
邻接矩阵
int
vexnum,arcnum;//
图的当前顶点数和弧数
GraphKind
kind;//
图的种类标志
}MGraph;
2
．邻接表的存储表示如下
typedef struct ArcNode{
//
弧的结点结构类型
int
adjvex;//
该弧所指向的顶点的位置
int
weight;/*
该弧的权重
*/
struct ArcNode
*nextarc;//
指向下一条弧的指针
InfoType
*info;/
/
该弧相关信息的指针
(
可无
)
}ArcNode;
typedef struct
VNode{//
邻接表头结点的类型
vertexType
data;//
顶点信息
ArcNode
*firstarc;//
指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef
struct{//
邻接表
AdjList vertices;
int
vexnum,arcnum;//
图的当前顶点数和弧数
}ALGraph
- 4 -
图的遍历和生成树求解
3
．队列的存储结构
typedef struct QNode
{
TElemType data;
QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr
front;//
队头指针
QueuePtr
rear;//
队尾指针
}LinkQueue;
4
．
Prim
算法辅助数组存储结构
typedef struct
//
辅助数组存储结构
{
VertexType adjvex;
VRType lowcost;
}Closedge[ MAX_VERTEX_NUM];
3.2
函数功能描述及相关函数的实现
1.
基于邻接矩阵创建图
Create
UDN(MGraph &G,AdjMatrix &GA)
Status
CreateUDN(MGraph &G
,AdjMatrix &GA)
{//
用邻接矩阵表示法，构造无向网
G
，以及表示出其邻接矩阵
GA
int i,j,k,w;
VertexType
v1,v2;
printf(
请输入无向网
< br>G
的顶点数
,
边数
:n
scanf(
.vexnum,&G
.arcnum,);
printf(
请输入<
/p>
%d
个顶点的值
:n
.vexnum);
for(i=1;i<=G
.vexnum;++i)
- 5 -
图的遍历和生成树求解
scanf(
.vexs[i]);
//
构造顶点向量
getchar();
for(i=1;i<=G
.vexnum;i++)
{
}
printf(
请
输
入
%d
< br>条
边
的
顶
点
1
顶
点
2
和
权
值
(
以
空
格
作
为
间
for(j=1;j<=G
.vexnum;j++)
//
初始化邻接矩阵
{
}
GA[i][j].adj=INFINITY;
GA[i][j].info=NULL;
隔
):n
.arcnum);
}
2.
基
于邻接表建立图
CreateALGraph(ALGraph &G)
Status
CreateALGraph(ALGraph &G)
{//
用邻接表表示法，构建无向网
G
int i,j,k,w;
ArcNode *s,*p;
p
rintf(
请输入顶点数和边数
(
输
入格式为
:
顶点数
,
< br>边数
)
：
n
scanf(
.vexnum),&(G
.arcnum));
vertexType v1,v2;
for(k=1;k<=G
.arcnum;k++)
{
}
return OK;
scanf(
输入一条边依附的顶点和权值
i=LocateVex(G
,v1);
j=LocateVex(G
,v2);
//
确定
v1
和
v2
在
G
中的位置
GA[i][j].adj=GA[j][i].adj=w; //
< br>弧
的权值
和
的对称弧
- 6 -
图的遍历和生成树求解
printf(
请输入顶点信息：
n
for (
i=1;i<=G
.vexnum;i++)
{
scanf(
.vertices[i].data));
//
初始化邻接表的头结点
G
.vertices[i].firstarc=NULL;
}
<
/p>
printf(
请输入边的信息
(
输入格式为
:v1,v2,w)
：
n
for
(k=1;k<=G
.arcnum;k++)
{
sc
anf(
输入一条边依附的顶点和权值
j=
LocateVexG(G
,v2);
i=
LocateVexG(G
,v1); //
确定
v1
和
v2
在
G
中的位置
s=(ArcNode*)malloc(sizeof(ArcNode));
s->adjvex=j;
s->weight=w;
s->nextarc=G
.vertices[i].first
arc;
G
.vertices[i].firstarc=s;//
将下标为
j
的结点连接在下标为
i
的结
点后面
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
p->weight=w;
p->nextarc=G
.vertices[j].first
arc;
G
.vertices[j].firstarc=p; //
将下标为
i
的结点连接在下标为
j
的结点后面
}
return OK;
}
3.
邻
接矩阵的输出
Display(MGraph G,AdjMatrix GA)
void Display(MGraph
G
,AdjMatrix GA)
{
//
邻接矩阵的输出
int i,j;
for(i=1;i<=G
.vexnum;i++)
- 7
-
图的遍历和生成树求解
pri
ntf(
.vexs[%d]=%cn
.vexs[i]);
//
输出顶点向量
printf(<
/p>
邻接矩阵
:n
for(i=1;i<=G
.vexnum;i++)
{
}
for(j=1;j<=G
.vexnum;j++)
printf(
printf(
}
4.
邻接表的输出
DisplayG(
ALGraph G)
void DisplayG(ALGraph G)
{//
邻接表的输出
int i;
ArcNode
*p;
for(i=1; i<=G
.vexnum;
i++)
{
p=G
.vertices[i].firstarc;
printf(
.vertices[i].data);
while(p)
{
if(p->nextarc)
printf(
.vertices
[p->adjvex].data,p->weight);
else
printf(
< br>.vertices[p->adjvex].data,p->weight);
p=p->nextarc;
}
printf(
}
- 8 -
-
-
-
-
-
-
-
-
-
上一篇：在领导面前自我介绍
下一篇：图的邻接矩阵和邻接表相互转换