最小生成树和最短路径 数据结构实验.docVIP

实验报告

六月18

２015

姓名:陈斌学号：专业：13计算机科学与技术

数据结构第八次实验

?

学号专业计算机科学与技术姓名陈斌

实验日期2０15、０6、１８教师签字成绩

实验报告

【实验名称】最小生成树与最短路径

【实验目得】

掌握最小生成树以及最短路径得相关概念；

掌握Prim算法与Ｋruｓkal算法;

掌握Diｊkstra算法

【实验内容】

采用普里姆算法求最小生成树

编写一个算法,对于教材图7、16(a)所示得无向带权图G采用普里姆算法输出从顶点V1出发得最小生成树。图得存储结构自选。

对于上图,采用克鲁斯卡尔算法输出该图得最小生成树。（提示：ａ、先对边按权值从小到大排序,得有序边集E;为所有顶点辅设一个数组Vsｅt,标记各顶点所处得连通分量,初始时各不相同。b、依次从E中取出一条边(i,j),检查顶点ｉ与j就是否属于同一连通分量,如就是,则重取下一条边;否则,该边即为生成树得一条边,输出该边,同时将所有与j处于同一连通分量得顶点得Ｖset值都修改为与i得相同。c、重复b步直至输出n-１条边。)

?源代码:

head、h:

#ｉnclude＜sｔring、h

#iｎcludectype、h

＃includemalloｃ、h／／malｌｏｃ(）

#incｌｕdelimｉts、h//INT，MAX

#includｅstｄiｏ、h//EOＦ,NＵLＬ

＃inclｕｄe＜sｔdlｉb、h//aｔoi（)

#iｎcluｄｅio、h//eｏf（）

#includemath、h//flooｒ(）,ceil(),ａbs()

#includｅprocｅss、ｈ//eｘit()

#ｉｎclｕdeｉosｔｒｅａｍ、h//cout,cin

//函数结果状态代码

#defineＴRUE1

#dｅｆｉneＦALＳE0

#defiｎeＯK1

#defineEＲＲOR0

#ｄｅfｉｎeIＮＦEAＳIBLE－1

／/OVEＲFＬOW在ｍａｔｈ、ｈ中已定义为3

tyｐｅdｅfｉnｔStatus;

ｔypeｄｅｆintBｏolean;//布尔类型

ｍain、cpp:

＃ｉnclude＂hｅad、ｈ＂

ｔypｅdefintVRType;

typedｅｆcharInfoType;

＃defｉneMAＸ＿ＮＡMＥ3/*顶点字符串得最大长度+１*／

#defineMAＸ_ＩNＦO20/*相关信息字符串得最大长度+１*／

ｔypedefｃhaｒVｅrtexＴype[MＡX_NAME］;

/*图得数组（邻接矩阵)存储表示*/

#dｅfineＩNFINＩTYINT_MAＸ/*用整型最大值代替∞＊/

＃dｅfineMAX_ＶEＲTＥX_ＮＵM2０/*最大顶点个数*/

typeｄeｆenｕm{DG,DＮ,ＡG，AN｝GraｐhKind;/*{有向图，有向网，无向图,无向网｝*/

typｅｄefstｒｕct

{

VRTypｅａdj；/*顶点关系类型。对无权图,用１（就是)或0(否)表示相邻否;＊／

/＊对带权图,c则为权值类型*／

InfoType*info;/*该弧相关信息得指针(可无）*/

}AｒcCell,AdjMatｒｉx[MAX_ＶＥRTEX_ＮUM][MAX_VERＴEX＿NUM]；

typｅdefｓtruct

{

ＶerteｘＴyｐevｅxs［MＡX_VＥＲTEＸ_NUM];/*顶点向量*/

AdjMａｔrixａrcs;/*邻接矩阵*／

iｎtｖｅxnuｍ，arcnum;/*图得当前顶点数与弧数*/

ＧraphKiｎｄkind;／＊图得种类标志*/

}MGｒaph;

intLoｃatｅVeｘ（MGraphG,VertexTypeｕ)

{／＊初始条件:图G存在,u与G中顶点有相同特征*/

／＊操作结果：若Ｇ中存在顶点u,则返回该顶点在图中位置；否则返回-１*/

inti;

ｆor（i=０;i＜G、vｅxnｕm；++i)

if（ｓtｒcmp（u,G、veｘs[ｉ])==0）

retuｒnｉ；

rｅturn-1；

}

StatuｓCreateＡN（ＭＧraphG）

{/*