江苏大学数据结构C++以邻接链表的方式确定一个无向网.doc

题目3． 以邻接链表的方式确定一个无向网，完成： ⑴建立并显示出它的邻接矩阵； ⑵对该图进行广度优先遍历，显示遍历的结果，（并随时显示队列的入、出情况）； ⑶用普里姆算法构造其最小生成树，随时显示其构造的过程； 用克鲁斯卡尔算法构造其最小生成树，随时显示其构造的过程； 一、需求分析 1．运行环境： Microsoft Visual Studio 2010 2．程序所实现的功能： （1）建立并显示图的邻接矩阵； （2）广度优先遍历该图，显示遍历结果； （3）用普里姆算法构造该图的最小生成树，显示构造过程； （4）用克鲁斯卡尔算法构造该图的最小生成树，显示构造过程。 3．程序的输入，包含输入的数据格式和说明： （1）输入顶点数，及各顶点信息(数据格式为整形)； （2）输入弧以及其权值(数据格式为整形)。 4．程序的输出，程序输出的形式： （1）输出图的邻接矩阵； （2）广度优先遍历结果； （3）普里姆算法构造最小生成树的结果； （4）克鲁斯卡尔算法构造最小生成树的结果。 5．测试数据，如果输入的数据量较大，需要给出测试数据： （1）顶点个数：4 （2）各个顶点为：a b c d （3）输入所有的弧（格式为“顶点 顶点 权值”）为：a b 2 a d 4 b c 1 b d 8 c d 7 a c 6 二、设计说明 1．算法设计的思想： 建立图类，建立相关成员函数。最后在主函数中实现。具体成员函数的实现请参看源程序。 邻接链表: 邻接链表是一种链式存储结构。在邻接链表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。每个结点由3个域组成，其中邻接点域指示与顶点Vi邻接的点在图中的位置，链域指示下一条边或弧的结点；数据域存储和边或弧相关的信息，如权值等。 所以一开始必须先定义邻接链表的边结点类型以及邻接链表类型，并对邻接链表进行初始化，然后根据所输入的相关信息，包括图的顶点数、边数、是否为有向，以及各条边的起点与终点序号，建立图的邻接链表。 邻接矩阵: 图的邻接矩阵存储表示即是数组存储表示，在邻接矩阵中，我们定义两个数组分别存储数据元素的信息和数据元素之间的关系（边或弧）的信息，以二维数组表示有n个顶点的图时，需存放n个顶点信息和n的平方个弧信息的存储量。借助于邻接矩阵容易判定任意两个顶点之间是否有边或弧相连，并容易求得各个顶点的度。故在建立邻接矩阵之前，必须先定义顶点关系类型和相关指针指示弧的信息。 广度优先遍历: 假设从图总某顶点出发，在访问了v之后依次访问v的各个未曾访问到的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的邻接点”先于“后被访问的邻接点”被访问，直至图中所有已被访问的邻接点都被访问到。若此时图中尚有顶点未被访问到，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先有哪些信誉好的足球投注网站遍历图的过程是以v为起始点，由近及远，依次访问饿v有路径相通且路径长度为1,2….的顶点。和深度优先有哪些信誉好的足球投注网站类似，在遍历过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2,3…的顶点，需附设队列以存储已被访问的路径长度为1,2….的顶点。 所以要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队尾指针，同时也要定义一个标志数组以标记结点是否被访问。同样，也是从初始点出发开始访问，访问初始点，标志其已被访问，并将其入队。当队列非空时进行循环处理。当结点被访问时对其进行标志，并入队列。通过while（）循环，并以是否被访问为控制条件，访问所有结点，完成图的广度优先遍历。 普里姆算法: 假设N=(V,{E})是连通网，TE是N上最小生成数中边的集合。算法从U={U0}，TE={}开始，重复执行如下操作；在所有的边（u,v）中找一条代价最小的边（u0,v0）并入集合TE,同时V0并入U,直到U=V为止。此时TE中必有n-1条边，则，T=(V,{TE})为N 的最小生成树。 克鲁斯卡尔算法: 假设连通网N=(V,{E}),则令最小生成树的初始状态为只有n个顶点且无边的非连通图T=(V,{}),图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直到T中的所有顶点都在同一个连通分量上为止。 2．主要的数据结构设计说明： 图的邻接矩阵、邻接表的建立。图的广度优先遍历以及分别用普里姆算法和克鲁斯卡尔算法构造最小生成树。 3．程序的主要流程图： 4．程序的主要模块，要