数据结构实验：图二.doc

《数据结构实验：图二.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验七（二）图的应用实验目的：1、熟悉的图的两种存储方式：邻接矩阵和邻接表；2、通过实验，掌握图的应用：求最小生成树、最短路径、关键路径、拓扑排序；实验要求：1、在vc++或tc环境下实现基本功能；2、先完成基本功能，基本功能为必做内容，有多余时间的同学可以做选做的内容；3、独自完成实验操作，并给出相关的数据；4、每次实验后，撰写实验报告，并在下星期四由学习委员收集并按学号整理好后，交任课教师。实验内容及步骤：必做题：1、构造一个网（有向或无向）；2、求该网的prim算法生成的最小生成树或森林；3、求一个源点到其余顶点的最短路径；；选

2、做：1、求该网的拓扑排序和逆拓扑排序；参考程序：2、求该网的prim算法生成的最小生成树或森林#includetypedefintInfoType;#defineMAXV100//最大顶点个数//以下定义邻接矩阵类型typedefstruct{intno;//顶点编号InfoTypeinfo;//顶点其他信息}VertexType;//顶点类型typedefstruct//图的定义{intedges[MAXV][MAXV];//邻接矩阵intvexnum,arcnum;//顶点数，弧数VertexTypevexs[M

3、AXV];//存放顶点信息}MGraph;//图的邻接矩阵类型//以下定义邻接表类型typedefstructANode//弧的结点结构类型{intadjvex;//该弧的终点位置structANode*nextarc;//指向下一条弧的指针InfoTypeinfo;//该弧的相关信息,这里用于存放权值}ArcNode;typedefintVertex;typedefstructVnode//邻接表头结点的类型{Vertexdata;//顶点信息ArcNode*firstarc;//指向第一条弧}VNode;typedefVNodeA

4、djList[MAXV];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;//图中顶点数n和边数e}ALGraph;//图的邻接表类型#defineINF32767//用32767表示∞voidDispMat(MGraphg)//输出邻接矩阵g{inti,j;for(i=0;i

5、ges[i][j]);printf("");}}voidprim(MGraphg,intv){intlowcost[MAXV],min,n=g.vexnum;intclosest[MAXV],i,j,k;for(i=0;i

6、0&&lowcost[j]

7、[11];g.vexnum=6;g.arcnum=10;for(i=0;i

8、