71抽象数据类型图的定义

《71抽象数据类型图的定义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章图7.1抽象数据类型图的定义ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R＝{VR}VR＝{

2、v,w∈V且P(v,w)，表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息}名词和术语有向图、无向图、网、子图弧头、弧尾、边完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、回路简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林、最小生成树基本操作P：结构的建立和销毁:CreateGraph(&G,V,VR);//按V和VR的定义构造图G。DestroyGraph(&

3、G);//销毁图G。对顶点的访问操作:LocateVex(G,u);//若G中存在顶点u，则返回该顶点//在图中位置；否则返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//对v赋值value。对邻接点的操作:FirstAdjVex(G,v);//返回v的第一个邻接点。若该顶点//在G中没有邻接点，则返回“空”。NextAdjVex(G,v,w);//返回v的（相对于w的）下一个//邻接点。若w是v的最后一个邻//接点，则返回“空”。插入或删除顶点InsertVex(&G,v);//在图G中增添新顶点v。DeleteVex(&G,v

4、);//删除G中顶点v及其相关的弧。插入和删除弧InsertArc(&G,v,w);//在G中增添弧，若G是无//向的，则还增添对称弧。DeleteArc(&G,v,w);//在G中删除弧，若G是无//向的，则还删除对称弧。遍历DFSTraverse(G,v,Visit());//从顶点v起深度优先遍历图//G，并对每个顶点调用函数//Visit一次且仅一次。BFSTraverse(G,v,Visit());//从顶点v起广度优先遍历图//G，并对每个顶点调用函数//Visit一次且仅一次。7.2图的存储表示一、图的数组(邻接矩阵)存储

5、表示constintMaxGraphSize=30;templateclassGraph{private:SeqListvertexList;intedge[MaxGraphSize][MaxGraphSize];intgraphsize;//methodstofindvertexandidentifypositioninlistintFindVertex(SeqList&L,constT&vertex);intGetVertexPos(constT&vertex);public://constructorGraph(void);¼¼二、图的邻接表

6、存储表示templateclassvertex{protected:Listarc;public:Tdata;intfirstAdj;intnextAdj;}templateclassGraph{private:SeqListadjList;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志Arrayvisited(MaxGraphSize);//访问标志数组intgetVexPos(constT&vertex);//确定顶点位置TgetVertex(intpos);

7、//返回第pos个顶点public:intFirstAdjVex(intvertex);intNextAdjVex(intvertex);voidDFSearch(intv,SeqList*LP);SeqList&DFSTraverse;SeqList&BFSTraverse;¼¼}//classGraph;三、有向图的十字链表存储表示classArcNode{protected:inttailvex,headvex;//该弧的尾和头顶点的位置ArcNode*hlink,*tlink;//分别为弧头相同和弧尾相同的弧的链域InfoType*info;//该弧

8、相关信息的指针public:¼¼}//classArcNode;templateclassVexNode{protected:List*inArc,*outArc;//分别为入弧和出弧的链表public:Tdata;¼¼}//classVexNode;templateclassGraph{private:SqListOrthList;intvexnum,arcnum;//图的当前顶点数和弧数¼¼}//classGraph;三、无向图的邻