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

数据结构实验报告图的邻接表示和Prim算法生成MST1问题的描述使用邻接表来表示图，支持通过输入的方法来构造图，使用Prim算法生成最小生成树。2.算法的基本思想2.1图的邻接表表示对于G中的每个顶点vi，把所有邻接（于）vi的顶点vj链成一个单链表（称为关于vi的邻接表）。邻接表中每个表顶点都有两个域：其一是邻接点域adjvex，用以存放与vi相邻顶点的序号；其二是链域next，用来将邻接表的所有表点链在一起；另外若要表示边上的信息如（权值）,则在表顶点中还应增加一个数据域cost再为每个顶点vi的邻接表设置一个表头顶点，头顶点包含两个域，其一是顶点域vextex，用来存放顶点vi的信息，另一个是指针域firstedge，它是vi的邻接表的头指针。（为了便于随机访问任意顶点的邻接表，）将所有头顶点顺序存储在一个数组中, 这样就构成了图的邻接表表示，(但有时为了增加对图中顶点，边数等属性的描述可将邻接表和这些属性放在一起描述图的存储结构)在无向图的邻接表中，一条边（ Vi ， Vj ）在邻接表中出现两次：一次在关于Vi 的邻接表中；一次在关于Vj的邻接表中.2.2Prim最小生成树算法输入：连通的加权无向图（无向网）G=(V, E)，其中V=(1,2, ,n).输出：G的最小生成树要点引入集合U和T。U存放生成树的顶点，T存放生成树的边集。初值U=1，T=。选择有最小权的边( u, v)，uU, v(V-U),将v加入U,（u,v）加入T。重复这一过程，直到U=V。 void Prim( G, T ) T = ;U = 1 ;while ( ( U V ) != ) 设( u, v ) 是使uU与v(V-U)且权最小的边；T = T ( u, v ) ;U = U v ; 3.主要数据结构3.1图的数据类型：templatestruct graphNodeTypeType info;/邻接表节点附加信息，可不使用int num;/边的终止顶点double weight;/边的权重graphNodeType* link;struct graphEdgeint start;/起始顶点int end;/终止顶点double weight;/边的权重;templateclass graphTypepublic:bool isEmpty();/判断图是否为空bool isConnected();/判断图是否连通int getVertexNum();/获取顶点个数int getEdgeNum();/获取边个数void printGraph();/打印图graphEdge* extractEdge();/输出图的所有边(有向图)graphEdge* extractEdgeND();/输出图的所有边(无向图)double* adjMatrix();/输出图的邻接矩阵graphEdge* primMST(int from, int* tVertex);/Prim算法生成MSTvoid 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;/边个数graphNodeType* adjList;/邻接表int findMinCost(int* tVertex, graphEdge* gEdge, int* newVertex);/寻找最小代价边;3.2链表队列数据类型：templatestruct queueNodeTypeType info;queueNodeType* link;templateclass linkedQueueTypepublic:const linkedQueueType& operator=(const linkedQueueType&);/重载=运算符bool isEmptyQueue();/判断栈是否为空bool isFullQueue();/判断栈是否已满void destroyQueue();/销毁栈void initializeQueue();/初始化链栈Type front();/获取队首元素Type back();/获取队尾元素void addQueue(const Type& queueElement);/将元素加到队尾void deleteQueue();/删除队首节点queueNodeType* getFront();/获取队首元素queueNodeType* getRear();/获取队尾元素linkedQueueType();linkedQueueType(const linkedQueueType& otherQueue);linkedQueueType();private:queueNodeType* queueFront;/队首节点queueNodeType* queueRear;/队尾节点void copyQueue(const linkedQueueType &otherQueue);4.主要函数功能4.1图的构造有关函数bool addEdge(int u, int v, double weight);基本思想：第一步：判断要增加的边起点和终点以及权重是否合法，若不合法则返回false第二步：在邻接表的第u-1个列表中加入一个节点，终点为v，权重为weightbool deleteEdge(int u, int v);基本思想：第一步：判断要增加的边起点和终点以及权重是否合法，若不合法则返回false第二步：在邻接表的第u-1个列表寻找终点为v的节点并删除并返回true，若未找到则返回falsebool fixEdge(int u, int v, double weight);基本思想：第一步：删除边(u,v)第二步：若删除成功，添加边(u,v)，权重为weightprimMST(int from, int* tVertex)基本思想：第一步：判断算法起始顶点是否合法，若不合法则返回第二步：判断图是否连通，若不连通则返回第三步：获取图的所有边gEdge，所有顶点gVertex第四步：初始化树的边tEdge和树的顶点tVertex，把起始顶点放入tVertex第五步：寻找连接tVertex和gVertex中权值最小的边，并把它放入tEdge中第六步：在gEdge中把刚放入tEdge中的那个边设为无穷大第七步：若tVertex中的元素少于图的顶点数，重复执行第五、六步若tVertex中的元素等于图的顶点数，算法结束4.2用户界面图绘制函数void PaintGraph();基本思想：第一步：把绘图区域用白色填充，获取其长宽，取小的作为圆形半径，计算中心点坐标第二步：判断图是否为空，若为空直接返回第三步：获取图的节点个数，在圆周上等距画出各顶点第四步：获取图的邻接矩阵M，只要Mij不是INF，便为第i个和第j个顶点连线void PaintTreeEdge(int u, int v);基本思想：第一步：获取绘图区域长宽，取小的作为圆形半径，计算中心点坐标第二步：为第u个和第v个顶点连线void TranslateCommand(CString CmdStr);基本思想：第一步：使用判断语句比较输入指令的前几位，看是否与已有指令相同第二步：后面几位为输入参数，获取并执行响应函数5.算例编译环境：VS2008 项目类型：MFC应用程序输入指令：Example，显示一个算例输入指令：PrimMST 1，程序给出了从顶点1计算出的最小生成树输入指令：RefreshGraph 4，图变为一个四顶点无边图输入指令：Add 1 2 3，顶点1、2间添加了一条权重为3的边输入指令