构造可以使n个城市连接的最小生成树.docx
《构造可以使n个城市连接的最小生成树.docx》由会员分享，可在线阅读，更多相关《构造可以使n个城市连接的最小生成树.docx（20页珍藏版）》请在冰点文库上搜索。
构造可以使n个城市连接的最小生成树
《数据结构》
课程设计报告
设计题目：
构造可以使n个城市连接的最小生成树
姓名：
学号：
专业：
物联网工程（嵌入式培养）
院系：
计算机技术与科学学院
班级：
1405
指导教师：
2016年01月09日
摘要
本次课程设计的要求是给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。
将该地区的城市用顶点表示，城市间的公路用边表示，公路的长度作为边的权值，最终这个问题可以归结为网图中，求顶点A到顶点B的所有路径中，边的权值之和最少的那条路径。
关键词：
最小生成树
Prim算法
C++语言源程序
Abstract
Thecurriculumdesignrequirementsisgivenaregionncity,thedistancebetweenthenetwiththePrimalgorithmtoestablishminimumspanningtree,andcalculatedthepriceofminimumspanningtree.Citiesintheregionwithvertexsaid,betweenhighwayinthecityedge,saidthelengthoftheroadastheedgeoftherightvalues,finallytheproblemcanbesummedupinnetworkdiagram,andallthepathsofvertexAtoB,theedgeoftheweightsofthesumoftheminimumpath.
Keywords:
minimumspanningtree
Primalgorithm
C++languagesourceprogram
一、问题描述4
1.1题目内容4
1.2基本要求4
二、需求分析4
三、概要设计4
3.1邻接矩阵的建立5
3.2图的建立5
3.3求最小生成树6
四、数据结构设计7
五、算法设计8
5.1算法分析8
5.2算法实现8
六、程序测试与实现9
6.1主程序9
6.2测试结果10
七、调试分析10
八、遇到的问题及解决办法10
九、心得体会10
十、附录11
一、问题描述
1．题目内容：
给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。
2．基本要求：
a）城市间的距离网采用邻接矩阵表示，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。
（要求至少10个城市，15条边）
b）最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。
二、需求分析
本程序的功能包括图的建立（采用邻接矩阵存储）和求最小生成树。
1 图的建立涉及到顶点数组data[n]和邻接矩阵Edge[n][n]，顶点数组运用顺序表完成，操作有：
顶点的插入即顺序表的插入；邻接矩阵的建立，操作有：
插入弧和对应的权值,输出邻接矩阵
2 最小生成树是通过Prim算法完成的。
Prim里涉及到候选最短边集，用数组shortEdge[n]表示候选最短边集，数组元素包括候选最短边的的邻接点（adjvex）和权值（lowcost）两个域
三、概要设计
1.邻接矩阵的建立
1 邻接矩阵的初始化，顶点自己对自己的权值为0，其余的权值均为MaxWeight（自定义的无穷大,999）
AdjMatGraph:
:
AdjMatGraph（constintsz）//sz是顶点数，有参构造函数
{
for（inti=0;ifor（intj=0;j{
if（i==j）
Edge[i][j]=0;
else
Edge[i][j]=MaxWeight;//无穷大
}
numOfEdges=0;
}
2 邻接矩阵中点与点之间有弧的，则将两个顶点之间的权值设为weight取代MaxWeight（无穷大,999）
voidAdjMatGraph:
:
InsertEdge（constintv1,constintv2,intweight）//插入弧，权为weight
{
if（v1<0||v1>Vertices.ListSize（）||v2<0||v2>Vertices.ListSize（））
{
cout<<"参数v1,v2有误2"<exit（0）;
}
Edge[v1][v2]=weight;
Edge[v2][v1]=weight;
numOfEdges++;
}
2.图的建立
structRowColWeight//边信息三元组
{
introw;
intcol;
intweight;
};
voidAdjMatCreateGraph（AdjMatGraph&G,DataTypeV[],intn,RowColWeightE[],inte）//用一个存储边权信息的三元组来生成图
{
inti;
for（i=0;iG.InsertVertex（V[i]）;//填充顶点信息
for（i=0;iG.InsertEdge（E[i].row,E[i].col,E[i].weight）;
}
3.求最小生成树
structshortEdge
{
intlowcost;
intadjvex;
};
voidAdjMatGraph:
:
Prim（）
{
intk,w,cost=0;
for（inti=1;inumOfVertices（）;i++）
{
shortEdge[i].lowcost=Edge[0][i];
shortEdge[i].adjvex=0;
}
shortEdge[0].lowcost=0;
for（inti=1;inumOfVertices（）;i++）
{
w=MaxWeight;
for（intj=1;jnumOfVertices（）;j++）
{
if（shortEdge[j].lowcost!
=0&&shortEdge[j].lowcost{
w=shortEdge[j].lowcost;
k=j;
}
}
shortEdge[k].lowcost=0;
for（intj=1;jnumOfVertices（）;j++）
{
if（Edge[k][j]{
shortEdge[j].lowcost=Edge[k][j];
shortEdge[j].adjvex=k;
}
}
}
cout<<"最小生成树为：
"<for（inti=1;inumOfVertices（）;i++）
{
cout<"<cost=cost+Edge[i][shortEdge[i].adjvex];
}
cout<<"最小生成树代价为：
"<}
四、数据结构设计
元素类型，结点类型
classSeqList
{
private:
DataTypedata[MaxListSize];
intsize;
public:
SeqList（）;
intListSize（）const;//返回元素的个数size
voidInsert（constDataType&item,intpos）;//在位置pos插入元素item
};
structRowColWeight//边信息三元组
{
introw;
intcol;
intweight;
};
structRowColWeight//边信息三元组
{
introw;
intcol;
intweight;
};
classAdjMatGraph
{
private:
SeqListVertices;//用顺序表存储结点信息
intEdge[MaxVertices][MaxVertices];//用数组存储带权或不带权的边
intnumOfEdges;//边数
shortEdgeshortEdge[MaxSize];
public:
AdjMatGraph（constintsz=MaxVertices）;//有参构造函数,sz为顶点数
intnumOfVertices（）//返回结点数目
{
returnVertices.ListSize（）;
}
intnumOfEdge（）//返回边数
{
returnnumOfEdges;
}
voidInsertVertex（constVerT&vertex）;//插入结点vertex
voidInsertEdge（constintv1,constintv2,intweight）;//插入弧，权为weight
voidprintMGraph（）;
voidPrim（）;
};
五、算法设计
1.算法分析
根据用Prim算法求最小生成树，设G=（V,E）是具有n个顶点的连通网，T=（U,TE）是G的最小生成树，T的初始状态为U={u0}（u0∈V））,TE={},重复执行下述操作：
在所有u∈U,v∈V-U的边中找一条代价最小的边（u，v）并入集合TE,同时v并入U,直至U=V0,最后计算得到的最小生成树的代价
2.算法实现
voidAdjMatGraph:
:
Prim（）
{
intk,w,cost=0;
for（inti=1;inumOfVertices（）;i++）
{
shortEdge[i].lowcost=Edge[0][i];
shortEdge[i].adjvex=0;
}
shortEdge[0].lowcost=0;
for（inti=1;inumOfVertices（）;i++）
{
w=MaxWeight;
for（intj=1;jnumOfVertices（）;j++）
{
if（shortEdge[j].lowcost!
=0&&shortEdge[j].lowcost{
w=shortEdge[j].lowcost;
k=j;
}
}
shortEdge[k].lowcost=0;
for（intj=1;jnumOfVertices（）;j++）
{
if（Edge[k][j]{
shortEdge[j].lowcost=Edge[k][j];
shortEdge[j].adjvex=k;
}
}
}
cout<<"最小生成树为：
"<for（inti=1;inumOfVertices（）;i++）
{
cout<"<cost=cost+Edge[i][shortEdge[i].adjvex];
}
cout<<"最小生成树代价为：
"<}
六、程序测试与实现
1.主程序
voidmain（）
{
AdjMatGraphg;
chara[]={'A','B','C','D','E','F','G','H','I','J'};
RowColWeightrcw[]={{0,4,1},{0,1,2},{4,5,3},{0,5,4},{1,5,5},{5,6,6},{1,2,7},{2,6,8},
{2,7,9},{2,3,10},{3,7,11},{3,9,12},{8,9,13},{7,8,14},{6,7,15}};
intn=10,e=15;//10个顶点，15条边
AdjMatCreateGraph（g,a,n,rcw,e）;
cout<<"当前的顶点个数为：
"<cout<<"当前的边的条数为：
"<g.printMGraph（）;
g.Prim（）;
}
2.测试结果（999是我自己设置的无穷大）
七、调试分析
1．图的邻接矩阵是一个n*n的矩阵，所以其空间代价是O（n2）
2．在求解最小生成树的过程中，会不断的读取任意两个顶点之间边的权值，所以采用邻接矩阵
八、遇到的问题及解决办法
在求解利用Prim求解最小生成树的过程中，算法能够看懂，但是利用C++程序去实现，还是有问题的。
最后反复看代码，构造了一个最短候选边集，即数组shortEdge[n]。
九、心得体会
本次课程设计用到了顺序表的建立与插入，图的邻接矩阵存储，最终实现了求n个城市之间的相同公路之间的最短距离，我主要学到了将实际问题转换为自己所学到的知识，做到了学以致用。
十、附录（源代码）
SeqList.h
#include
usingnamespacestd;
classSeqList
{
private:
DataTypedata[MaxListSize];
intsize;
public:
SeqList（）;
intListSize（）const;//返回元素的个数size
voidInsert（constDataType&item,intpos）;//在位置pos插入元素item
};
SeqList:
:
SeqList（）
{
size=0;
}
intSeqList:
:
ListSize（）const
{
returnsize;
}
voidSeqList:
:
Insert（constDataType&item,intpos）//在位置pos插入元素item
{
inti;
if（size==MaxListSize）
{
cout<<"顺序表已满无法插入！
"<exit
（1）;
}
if（pos<0||pos>size）//当pos等于size时表示插入在最后
{
cout<<"参数pos越界出错!
"<exit
（1）;
}
//从后向前把前一个元素迁移到后一个元素位置直到存储位置pos为止
for（i=size;i>pos;i--）
data[i]=data[i-1];
data[pos]=item;//在pos位置插入item
size++;//数据元素个数size加1
}
AdjMatGraphLib.h
structRowColWeight//边信息三元组
{
introw;
intcol;
intweight;
};
voidAdjMatCreateGraph（AdjMatGraph&G,DataTypeV[],intn,RowColWeightE[],inte）//用一个存储边权信息的三元组来生成图
{
inti;
for（i=0;iG.InsertVertex（V[i]）;//填充顶点信息
for（i=0;iG.InsertEdge（E[i].row,E[i].col,E[i].weight）;
}
AdjMatGraph.h
#include
constintMaxSize=100;
structshortEdge
{
intlowcost;
intadjvex;
};
classAdjMatGraph
{
private:
SeqListVertices;//用顺序表存储结点信息
intEdge[MaxVertices][MaxVertices];//用数组存储带权或不带权的边
intnumOfEdges;//边数
shortEdgeshortEdge[MaxSize];
public:
AdjMatGraph（constintsz=MaxVertices）;//有参构造函数,sz为顶点数
intnumOfVertices（）//返回结点数目
{
returnVertices.ListSize（）;
}
intnumOfEdge（）//返回边数
{
returnnumOfEdges;
}
voidInsertVertex（constVerT&vertex）;//插入结点vertex
voidInsertEdge（constintv1,constintv2,intweight）;//插入弧，权为weight
voidprintMGraph（）;
voidPrim（）;
};
AdjMatGraph:
:
AdjMatGraph（constintsz）//sz是顶点数，有参构造函数
{
for（inti=0;ifor（intj=0;j{
if（i==j）
Edge[i][j]=0;
else
Edge[i][j]=MaxWeight;//无穷大
}
numOfEdges=0;
}
voidAdjMatGraph:
:
InsertVertex（constVerT&vertex）//插入结点vertex
{
Vertices.Insert（vertex,Vertices.ListSize（））;
}
voidAdjMatGraph:
:
InsertEdge（constintv1,constintv2,intweight）//插入弧，权为weight
{
if（v1<0||v1>Vertices.ListSize（）||v2<0||v2>Vertices.ListSize（））
{
cout<<"参数v1,v2有误2"<exit（0）;
}
Edge[v1][v2]=weight;
Edge[v2][v1]=weight;
numOfEdges++;
}
voidAdjMatGraph:
:
printMGraph（）
{
cout<<"邻接矩阵是：
"<for（inti=0;inumOfVertices（）;i++）
{
for（intj=0;jnumOfVertices（）;j++）
{
cout<}
cout<cout<}
}
voidAdjMatGraph:
:
Prim（）
{
intk,w,cost=0;
for（inti=1;inumOfVertices（）;i++）
{
shortEdge[i].lowcost=Edge[0][i];
shortEdge[i].adjvex=0;
}
shortEdge[0].lowcost=0;
for（inti=1;inumOfVertices（）;i++）
{
w=MaxWeight;
for（intj=1;jnumOfVertices（）;j++）
{
if（shortEdge[j].lowcost!
=0&&shortEdge[j].lowcost{
w=shortEdge[j].lowcost;
k=j;
}
}
shortEdge[k].lowcost=0;
for（intj=1;jnumOfVertices（）;j++）
{
if（Edge[k][j]{
shortEdge[j].lowcost=Edge[k][j];
shortEdge[j].adjvex=k;
}
}
}
cout<<"最小生成树为：
"<for（inti=1;inumOfVertices（）;i++）
{
cout<"<cost=cost+Edge[i][shortEdge[i].adjvex];
}
cout<<"最小生成树代价为：
"<}
Main.cpp
#include
typedefcharDataType;
constintMaxListSize=100;
constintSeqQMaxSize=100;
#include"SeqList.h"
constintMaxVertices=100;
constintMaxWeight=999;
typedefcharVerT;
#include"AdjMatGraph.h"
#include"AdjMatGraphLib.h"
usingnamespacestd;
voidmain（）
{
AdjMatGraphg;
chara[]={'A','B','C','D','E','F','G','H','I','J'};
RowColWeightrcw[]={{0,4,1},{0,1,2},{4,5,3},{0,5,4},{1,5,5},{5,6,6},{1,2,7},{2,6,8},
{2,7,9},{2,3,10},{3,7,11},{3,9,12},{8,9,13},{7,8,14},{6,7,15}};
int
升级会员 