71抽象數(shù)據(jù)類型圖的定義

《71抽象數(shù)據(jù)類型圖的定義》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、第七章圖7.1抽象數(shù)據(jù)類型圖的定義ADTGraph{數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關系R：R＝{VR}VR＝{

2、v,w∈V且P(v,w)，表示從v到w的弧，謂詞P(v,w)定義了弧的意義或信息}名詞和術語有向圖、無向圖、網(wǎng)、子圖弧頭、弧尾、邊完全圖、稀疏圖、稠密圖鄰接點、度、入度、出度路徑、路徑長度、回路簡單路徑、簡單回路連通圖、連通分量、強連通圖、強連通分量生成樹、生成森林、最小生成樹基本操作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起深度優(yōu)先遍歷圖//G，并對每個頂點調用函數(shù)//Visit一次且僅一次。BFSTraverse(G,v,Visit());//從頂點v起廣度優(yōu)先遍歷圖//G，并對每個頂點調用函數(shù)//Visit一次且僅一次。7.2圖的存儲表示一、圖的數(shù)組(鄰接矩陣)存儲

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;//圖的當前頂點數(shù)和弧數(shù)intkind;//圖的種類標志Arrayvisited(MaxGraphSize);//訪問標志數(shù)組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;//圖的當前頂點數(shù)和弧數(shù)??}//classGraph;三、無向圖的鄰