数据结构报告-图的邻接表示和Prim算法生成MST.doc

数据结构实验报告—— 图的邻接表示和Prim算法生成MST 1问题的描述 使用邻接表来表示图，支持通过输入的方法来构造图，使用Prim算法生成最小生成树。 2.算法的基本思想 2.1．图的邻接表表示 对于G中的每个顶点vi，把所有邻接（于）vi的顶点vj链成一个单链表（称为关于vi的邻接表）。邻接表中每个表顶点都有两个域：其一是邻接点域adjvex，用以存放与vi相邻顶点的序号；其二是链域next，用来将邻接表的所有表点链在一起；另外若要表示边上的信息如（权值）,则在表顶点中还应增加一个数据域cost 再为每个顶点vi的邻接表设置一个表头顶点，头顶点包含两个域，其一是顶点域vextex，用来存放顶点vi的信息，另一个是指针域firstedge，它是vi的邻接表的头指针。 （为了便于随机访问任意顶点的邻接表，）将所有头顶点顺序存储在一个数组中, 这样就构成了图的邻接表表示，(但有时为了增加对图中顶点，边数等属性的描述可将邻接表和这些属性放在一起描述图的存储结构) 在无向图的邻接表中，一条边（ Vi ， Vj ）在邻接表中出现两次：一次在关于Vi 的邻接表中；一次在关于Vj的邻接表中. 2.2．Prim最小生成树算法 输入：连通的加权无向图（无向网）G=(V, E)，其中V=(1,2, …,n). 输出：G的最小生成树 要点 引入集合U和T。U存放生成树的顶点，T存放生成树的边集。初值U={1}，T=?。选择有最小权的边( u, v)，u∈U, v∈(V-U),将v加入U,（u,v）加入T。重复这一过程，直到U=V。 void Prim( G, T ) { T = ?; U = { 1 }; while ( ( U – V ) != ?) { 设( u, v ) 是使u∈U与v∈(V-U)且权最小的边； T = T∪{ ( u, v ) } ; U = U ∪ { v }; } } 3.主要数据结构 3.1图的数据类型： templateclass Type struct graphNodeType { Type info; //邻接表节点附加信息，可不使用 int num; //边的终止顶点 double weight; //边的权重 graphNodeTypeType* link; }; struct graphEdge { int start; //起始顶点 int end; //终止顶点 double weight; //边的权重 }; templateclass Type class graphType { public: bool isEmpty(); //判断图是否为空 bool isConnected(); //判断图是否连通 int getVertexNum(); //获取顶点个数 int getEdgeNum(); //获取边个数 void printGraph(); //打印图 graphEdge* extractEdge(); //输出图的所有边(有向图) graphEdge* extractEdgeND(); //输出图的所有边(无向图) double** adjMatrix(); //输出图的邻接矩阵 graphEdge* primMST(int from, int* tVertex); //Prim算法生成MST void refreshGraph(int n); //刷新图为n个节点 bool addEdge(int u, int v, double weight); //增加边(有向图) bool deleteEdge(int u, int v); //删除边(有向图) bool fixEdge(int u, int v, double weight); //修改边(有向图) void addEdgeND(int u, int v, double weight); ////增加边(有向图) void deleteEdgeND(int u, int v); //删除边(有向图) void fixEdgeND(int u, int v, double weight); //修改边(有向图) graphType(int n = 0); //构造函数 ~graphType(); //析构函数 private: int nVertex; //顶点数 int nEdge; //边个数 graphNodeTypeType* adjList; //邻接表 int findMinCost(int* tVertex, graphEdge* gEd