1、上堂課要點(diǎn)回顧中序線索二叉樹結(jié)點(diǎn)類ThreadBiTreeNode線索二叉樹類ThreadBiTreecurrent、 pleteEndOfNext()、ThreadOrder()中序線索二叉樹類InThreadBiTreeThread()First()、Next()森林與二叉樹的轉(zhuǎn)換樹轉(zhuǎn)換為二叉樹二叉樹轉(zhuǎn)換為樹森林轉(zhuǎn)換為二叉樹二叉樹轉(zhuǎn)換為森林森林的遍歷先根深度優(yōu)先遍歷后根深度優(yōu)先遍歷習(xí)題講解第三章作業(yè)4、5第 十三 次 課閱讀： 朱戰(zhàn)立，第199-209頁習(xí)題：作業(yè)12數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容Chapter 8 圖8.1 圖的定義及ADT8.2-3 存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)8.4 圖的遍歷深度優(yōu)先搜索廣度優(yōu)先

2、搜索8.5 最小生成樹prim算法kruskul算法8.6 最短路徑dijkstra算法補(bǔ)充圖的應(yīng)用：1、拓?fù)渑判?、關(guān)鍵路徑圖的應(yīng)用領(lǐng)域電路網(wǎng)絡(luò)分析交通運(yùn)輸管理線路的鋪設(shè)印刷電路板與集成電路的布線工作的分配工程進(jìn)度的安排課程表的制訂關(guān)系數(shù)據(jù)庫的設(shè)計(jì)8.1 圖的定義及抽象數(shù)據(jù)類型8.1.1 圖(graph)的基本概念定義 圖G由兩個(gè)集合V(G)和E(G)所組成，記作 G=(V, E)。 其中，V(G)是圖中頂點(diǎn)vertex(即圖的數(shù)據(jù)元素) 的有限集合， E(G)是圖中邊edge(即兩個(gè)頂點(diǎn)之間的關(guān) 系)的有限集合。分類 (1) 有向圖(directed graph)：每條邊是頂點(diǎn)的有序偶對

3、有向圖中的邊也稱為弧。用尖括號(hào)表示頂點(diǎn) 的有序?qū)?，如，vi稱為弧尾，vj稱為弧頭，并 稱它們互為鄰接點(diǎn)(adjacent)。 例：132G1V(G1)=V1,V2,V3,E(G1)=, (2) 無向圖(undirected graph)：每條邊是頂點(diǎn)的無序偶對。用圓括號(hào)表示頂點(diǎn)的無序?qū)?，如（Vi,Vj），其中Vi和Vj為此邊的起點(diǎn)和終點(diǎn)，并稱它們互為鄰接點(diǎn)(adjacent)。 例：3124G24217536G3V(G2)=V1, V2, V3, V4E(G2)=(V1, V2), (V1, V3), (V1, V4), (V2, V3), (V2, V4), (V3, V4)樹圖無向完全圖，

4、有向完全圖 設(shè)n為圖的頂點(diǎn)數(shù)，e為邊或弧的數(shù)目，假設(shè)不考慮頂點(diǎn)到其自身的邊或弧。 具有n個(gè)頂點(diǎn)、n(n-1)條邊的有向圖，稱為有向完全圖(directed complete graph) 。 具有n個(gè)頂點(diǎn)、 條邊的無向圖，稱為無向完全圖(undirected complete graph)。 當(dāng)一個(gè)圖接近完全圖時(shí)，則稱它為稠密圖(dense graph)，相反地，當(dāng)一個(gè)圖中含有較少的邊或弧時(shí)，則稱它為稀疏圖(sparse graph)。網(wǎng) 若圖的邊或弧上附帶有數(shù)據(jù)信息,這些附帶的數(shù)據(jù)信息稱為稱為權(quán)。 這種帶權(quán)的圖(weighted graph)稱作網(wǎng)。子圖 假設(shè)有兩個(gè)圖G和G，且滿足條件： V

5、(G)V(G)，E(G) E(G)，則稱G是G的子圖。例： G1的一些子圖：1132132132G1G1的一些子圖G2的一些子圖：312412431213124G2G2的一些子圖度、入度和出度 (1) 度(無向圖中) 頂點(diǎn)vi的度(total degree) ：是和vi相關(guān)聯(lián)的邊的數(shù)目，記作TD(vi)。 (2) 入度、出度、度(有向圖中) 頂點(diǎn)vi的入度(in degree)：是以頂點(diǎn)vi為頭(終端點(diǎn))的弧的數(shù)目，記作ID(vi)。 頂點(diǎn)vi的出度(out degree)：是以頂點(diǎn)vi為尾(初始點(diǎn))的弧的數(shù)目，記作OD(vi)。 頂點(diǎn)vi的度(total degree)：入度和出度之和，記作

6、TD(vi) ，TD(vi)=ID(vi)+OD(vi)。路徑、回路 (1) 路徑(path) 在無向圖G中，從頂點(diǎn)vp到頂點(diǎn)vq的一條路徑是 頂點(diǎn)的序列，且 (vp,vi1), (vi1,vi2), , (vin,vq)都是E(G)中的邊。 路徑上邊的數(shù)目稱為該路徑的長度(path length) 。 對于有向圖，其路徑也是有向的，其頂點(diǎn)序列 為，且, , , 都是E(G)中的弧。 路徑上弧的數(shù)目稱為該路徑的長度。 (2) 回路( cycle, 環(huán)) 第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為 回路或環(huán)。 簡單路徑(simple path)：序列中各頂點(diǎn)不重復(fù)出現(xiàn)的路徑。 簡單回路：第一個(gè)頂點(diǎn)和

7、最后一個(gè)頂點(diǎn)相同的簡單 路徑稱為簡單回路(simple cycle)。 例：圖G2中， (v1, v2, v4, v3)是一條簡單路徑； (v1, v2, v4, v3 , v1)是一條簡單回路； (v1, v2, v4, v3 , v2 , v1)是一條回路。3124G2連通圖、連通分量和生成樹 (1) 在無向圖G中，若V(G)中的每一對不同的頂點(diǎn)vi和vj都是連通的，則稱G為連通圖(connected graph)。 在無向圖G中，最大的連通子圖稱為G的連通分量(connect compoent)。 例：3124G2的連通分量：312423154G4的連通分量：231(1)54(2)(2)

8、 在有向圖G中，若對于V(G)中每一對不同頂點(diǎn)vi和 vj 之間，都存在從vi到vj以及從vj到vi的路徑，則稱 G為強(qiáng)連通圖。 有向圖中最大的強(qiáng)連通子圖稱為它的強(qiáng)連通分量。 例：132G1的強(qiáng)連通分量：12(1)3(2)(3) 生成樹 一個(gè)連通圖的極小連通子圖稱作該圖的生成樹，它含有圖中全部頂點(diǎn)n，但只有足以構(gòu)成一棵樹的n-1條邊。 例：圖G2 的一棵生成樹為： 或312431243124G2 8.1.2 圖的抽象數(shù)據(jù)類型ADT Graph 數(shù)據(jù)：由一個(gè)結(jié)點(diǎn)集合vi和一個(gè)邊集合ej組成（網(wǎng)則 是一個(gè)邊權(quán)集合(ej,wj) ）。 操作：設(shè)G為 Graph 型 Initiate(G) /初始化圖

9、G；IsVertex(G,vertex) /判斷vertex是否是圖G的頂點(diǎn)（增加）；InsertVertex(G, vertex) /在圖G中插入頂點(diǎn)vertex； IsEdge(G,v1,v2) /判斷邊是否是圖G的邊（增加）； InsertEdge(G,v1,v2,weight) /*在圖G中插入邊，邊 的權(quán)值為weight ；*/ DeleteEdge(G,v1,v2) /在圖G中刪除邊； DeleteVertex(G, v) /*在圖G中刪除第v個(gè)頂點(diǎn)以及與 該頂點(diǎn)相關(guān)的所有邊；*/Degree(G,v) /計(jì)算圖G中第v個(gè)頂點(diǎn)的度（增加）；GetFirstVex(G,v) /在圖G

10、尋找第v個(gè)頂點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)；GetNextVex(G,v1,v2) /*在圖G中尋找頂點(diǎn)v1的(繼鄰接頂點(diǎn)v2 之后的)下一個(gè)鄰接頂點(diǎn)；*/ Traverse(G,Visit( ) /遍歷圖G。 8.2 圖的存儲(chǔ)結(jié)構(gòu)8.2.1 鄰接矩陣(Adjecency matrix)8.2.2 鄰接表(Adjecency list)8.2 圖的存儲(chǔ)結(jié)構(gòu)8.2.1 鄰接矩陣(Adjecency matrix)定義表達(dá)頂點(diǎn)間的相鄰關(guān)系的矩陣。設(shè)G=(V，E)是有n(n0)個(gè)頂點(diǎn)的圖，則G的鄰接矩陣是按如下定義的n階方陣A， 鄰接矩陣的空間代價(jià)是O(n2)aij =1， 若(vi,vj)或E(G)0， 反之

11、例：132G13124G2特征 (1) 無向圖 對稱矩陣 存儲(chǔ)量：n(n+1)/2 頂點(diǎn)的度數(shù)：TD(Vi)= (2) 有向圖 不一定是對稱矩陣 存儲(chǔ)量：n2 頂點(diǎn)的度數(shù)：ID(Vi)= OD(Vi)= (3) 適合稠密圖（e n2 ）(4) 容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（?。?、找頂點(diǎn)的鄰接點(diǎn)等等。網(wǎng)的鄰接矩陣 定義： aij =wij，若(vi,vj)或E(G)， 否則且ij例：123457781011590， 否則且i=jAdjMWGraph.hAdjMWGraph類CreatAdjWGraph.hCreatGraph函數(shù)GraphTest.cpp8.3.1 鄰

12、接矩陣的圖類P205-208class AdjMWGraphprivate:SeqList Vertices;/頂點(diǎn)順序表WT EdgeMaxVerticesMaxVertices;/邊權(quán)值數(shù)組int numOfEdges;/邊數(shù)void DepthFirstSearch(const int v, int visited, void Visit(VT item);void BroadFirstSearch(const int v, int visited, void Visit(VT item);public:AdjMWGraph(const int sz = MaxVertices);/構(gòu)造

13、函數(shù)， 最大頂點(diǎn)個(gè)數(shù)AdjMWGraph(void);/析構(gòu)函數(shù)int NumOfVertices(void)const return Vertices.Size(); /取頂點(diǎn)個(gè)數(shù)int NumOfEdges(void)const return numOfEdges; /取邊的個(gè)數(shù)VT GetValue(const int v)const;/取頂點(diǎn)數(shù)值WT GetWeight(const int v1, const int v2)const;/取邊的權(quán)值void InsertVertex(const VT &vertex);/插入頂點(diǎn)void InsertEdge(const int v1,

14、 const int v2, WT weight);/插入邊void DeleteVertex(const int v);/刪除頂點(diǎn)void DeleteEdge(const int v1, const int v2);/刪除邊int GetFirstNeighbor(const int v)const;/取第一個(gè)鄰接頂點(diǎn)int GetNextNeighbor(const int v1, const int v2)const;/取下一個(gè)鄰接頂點(diǎn)void DepthFirstSearch(void Visit(VT item);/深度優(yōu)先遍歷void BroadFirstSearch(void

15、Visit(VT item);/廣度優(yōu)先遍歷AdjMWGraph.h實(shí)現(xiàn)鄰接矩陣的圖類/補(bǔ)充函數(shù)/int IsVertex(VT vertex)const; /判斷有向圖是否有值為vertex頂點(diǎn)int IsVertex(int v)const;/判斷第v個(gè)頂點(diǎn)是否是有向圖的頂點(diǎn)int IsEdge(int v1,int v2)const;/*判斷第v1個(gè)頂點(diǎn)到第v2個(gè)頂點(diǎn)的邊是否是有向圖的邊*/int InDegree(int v)const;/在帶權(quán)有向圖中求第v個(gè)頂點(diǎn)的入度int OutDegree(int v) const;/在帶權(quán)有向圖中求第v個(gè)頂點(diǎn)的出度int Degree(int

16、 v) const;/在帶權(quán)有向圖中求第v個(gè)頂點(diǎn)的度;AdjMWGraph:AdjMWGraph(const int sz): Vertices(sz)/構(gòu)造函數(shù)/頂點(diǎn)順序表初始化，sz取缺省值MaxVertices int i, j; for(i = 0; i sz; i+) for(j = 0; j sz; j+) if (i = j) Edgeij = 0; else Edgeij = MaxWeight; / MaxWeight定義權(quán)值的無窮大 numOfEdges = 0; /*邊的條數(shù)置為0*/時(shí)間復(fù)雜度：O(1)【圖初始化算法】int AdjMWGraph:IsVertex(VT

17、 vertex) const/*判斷有向圖是否有值為vertex的頂點(diǎn)，有則返回該頂點(diǎn)在頂點(diǎn)順序表中的序號(hào)，否則返回-1。*/int i;for (i=0;iNumOfVertices();i+)if(Vertices.GetData(i)=vertex)break;if (i=NumOfVertices()return -1;elsereturn i; /時(shí)間復(fù)雜度O(n)【判斷圖中頂點(diǎn)存在否算法（增加）】int AdjMWGraph:IsVertex(int v)const/*判斷有向圖是否有第i個(gè)頂點(diǎn)，有則返回1，沒有則返回0。*/if(v = NumOfVertices()return

18、 0;elsereturn 1; /時(shí)間復(fù)雜度O(1)【判斷圖中頂點(diǎn)存在否算法2（增加）】 void AdjMWGraph:InsertVertex(const VT &vertex)/*在帶權(quán)有向圖中插入值為vertex的頂點(diǎn)。如果圖中已經(jīng)有值為vertex的頂點(diǎn)，則圖不變。*/if (IsVertex(vertex)0)/O(n) /在頂點(diǎn)順序表的表尾插入頂點(diǎn)vertex Vertices.Insert(vertex, NumOfVertices();/時(shí)間復(fù)雜度：O(n)【圖中插入頂點(diǎn)算法】【取頂點(diǎn)的數(shù)據(jù)域值】VT AdjMWGraph:GetValue(const int v)cons

19、t/取頂點(diǎn)v的數(shù)據(jù)域數(shù)值if(IsVertex(v)=0)cout 參數(shù)v越界出錯(cuò)! endl;exit(0);return Vertices.GetData(v);/O(1)【取邊的權(quán)值】WT AdjMWGraph:GetWeight(const int v1, const int v2)const/取起始頂點(diǎn)為v1、終止頂點(diǎn)為 v2的邊的權(quán)值if(IsVertex(v1)=0 | IsVertex(v2)=0)cout 參數(shù)v1或v2越界出錯(cuò)! endl;exit(0);return Edgev1v2;/O(1) void AdjMWGraph: DeleteVertex(const in

20、t v)/*在帶權(quán)有向圖中刪除第v個(gè)頂點(diǎn)以及與該頂點(diǎn)相關(guān)的所有邊*/int i,j;if(IsVertex(v)=0)cout刪除頂點(diǎn)時(shí)參數(shù)v越界出錯(cuò)！endl; exit(0); for(i = 0; i NumOfVertices(); i+)for(j = 0; j 0 &Edgeij MaxWeight) numOfEdges-;/邊數(shù)減1 /刪除所有包含頂點(diǎn)v的邊f(xié)or( i=v; iNumOfVertices(); i+)for( j=0; jNumOfVertices(); j+)Edgeij=Edgei+1j; /刪除所有第v個(gè)頂點(diǎn)出去的邊f(xié)or( i=0; iNumOfVer

21、tices(); i+)for( j=v; jNumOfVertices(); j+)Edgeij=Edgeij+1;Vertices.Delete(v);/刪除所有指向第v個(gè)頂點(diǎn)的邊/時(shí)間復(fù)雜度：O（n2）【刪除圖中頂點(diǎn)算法】int AdjMWGraph: IsEdge(int v1,int v2)const/*判斷第v1個(gè)頂點(diǎn)到第v2個(gè)頂點(diǎn)的邊是否是有向圖G的邊，是則返回1，否則如果有頂點(diǎn)不存在返回-2，否則如果v1和v2相等返回-1，否則如果邊不存在返回0 。 */if ( IsVertex(v1)=0 | IsVertex(v2)=0 )return -2;/有頂點(diǎn)不存在if ( v1

22、=v2 )return -1;/頂點(diǎn)存在，v1和v2相等if ( Edgev1v2 = MaxWeight )return 0;/頂點(diǎn)存在，v1和v2不相等，邊不存在return 1;/邊存在/時(shí)間復(fù)雜度O(1)【判斷圖中存在邊否算法（新增加）】void AdjMWGraph:InsertEdge(const int v1, const int v2, WT weight)/* 如果v1和v2有一個(gè)不是圖中的頂點(diǎn)，則圖不變；如果v1和v2相等，則圖不變。如果圖已經(jīng)包含該邊，則邊的權(quán)值更改為新的權(quán)值。如果圖沒有包含該邊，則在帶權(quán)有向圖G中插入一條第v1個(gè)頂點(diǎn)指向第v2個(gè)頂點(diǎn)，權(quán)值為weight的

23、有向邊。 */ switch (IsEdge(v1,v2)case -2:break;case -1:break;case 0:numOfEdges+;case 1: Edgev1v2=weight;default:;/時(shí)間復(fù)雜度:O(1)【圖插入邊算法】void AdjMWGraph: DeleteEdge(const int v1,const int v2)/* 如果v1和v2有一個(gè)不是圖中的頂點(diǎn)，則圖不變；如果v1和v2相等，則圖不變。如果不是圖的邊，則圖不變，如果是圖的邊，則在帶權(quán)有向圖G中刪除一條第v1個(gè)頂點(diǎn)指向第v2個(gè)頂點(diǎn)的有向邊。*/ switch (IsEdge(v1,v2)c

24、ase -2:break;case -1:break;case 0:break;case 1:/刪除邊Edgev1v2 = MaxWeight;/*把該邊的權(quán)值置為無窮大*/numOfEdges-;default:;/時(shí)間復(fù)雜度:O(1)【圖刪除邊算法】int AdjMWGraph:GetFirstNeighbor(const int v)const/*在帶權(quán)有向圖中取第v個(gè)頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)，如果這樣的鄰接頂點(diǎn)存在，則返回該頂點(diǎn)在頂點(diǎn)順序表的序號(hào)，否則返回-1。*/int col; if(IsVertex(v)=0)cout 參數(shù)v越界出錯(cuò)! endl;exit(0); /*尋找鄰接矩陣v

25、行中從最左開始第一個(gè)值非零且非無窮大的權(quán)值對應(yīng)的頂點(diǎn)*/for(col = 0; col 0 &Edgevcol MaxWeight) return col;return -1; /時(shí)間復(fù)雜度：O(n)【圖取第一個(gè)鄰接頂點(diǎn)算法】int AdjMWGraph:GetNextNeighbor(const int v1, const int v2)const/*在帶權(quán)有向圖G中取第v1個(gè)頂點(diǎn)的繼鄰接結(jié)點(diǎn)第v2個(gè)頂點(diǎn)之后的下一個(gè)鄰接結(jié)點(diǎn)。*/ int col; if(IsVertex(v1)=0 | IsVertex(v2)=0)cout 參數(shù)v1或v2越界出錯(cuò)! endl;exit(0);/*尋找鄰

26、接矩陣v行中從第v2+1列開始的第一個(gè)值非零且非無窮大的權(quán)值對應(yīng)的頂點(diǎn)*/ for(col = v2+1; col 0 & Edgev1col MaxWeight) return col;return -1; /時(shí)間復(fù)雜度:O(n)【圖取下一個(gè)鄰接頂點(diǎn)算法】void GraphCreat(AdjMWGraph &G, VT v,int n, RowColWeight E, int e)/*創(chuàng)建有n個(gè)頂點(diǎn)V和e條邊E的帶權(quán)有向圖G。*/ int i,k; for(i=0;in;i+) G.InsertVertex(vi); for(k=0;ke;k+) G.InsertEdge(Ek.row,E

27、k.col,Ek.weight);/時(shí)間復(fù)雜度:O(n2+e)typedef struct int row; /邊的一個(gè)頂點(diǎn)的下標(biāo) int col; /邊的另一個(gè)頂點(diǎn)的下標(biāo) WT weight; /權(quán)值RowColWeight;/邊信息【創(chuàng)建圖算法】CreatAdjWGraph.h實(shí)現(xiàn)基于鄰接矩陣圖類創(chuàng)建圖#include using namespace std;#include typedef char VT;/定義鄰接矩陣圖類中的頂點(diǎn)數(shù)據(jù)域類型VTtypedef int WT;/定義邊權(quán)值類型const int MaxVertices = 100;/定義最大頂點(diǎn)個(gè)數(shù)const int Ma

28、xWeight = 10000;/定義權(quán)值的無窮大#include “AdjMWGraph.h“/包含鄰接矩陣圖類#include CreatAdjWGraph.h“/包含鄰接矩陣圖的創(chuàng)建函數(shù)void main(void)AdjMWGraph g; char a = A,B,C,D,E; int n = 5, e = 5;RowColWeight rcw=0,1,10,0,4,20,1,3,30,2,1,40,3,2,50;CreatGraph(g, a, n, rcw, e);/創(chuàng)建圖8-8cout頂點(diǎn)個(gè)數(shù)為: g.NumOfVertices()endl;cout“邊的條數(shù)為: g.NumO

29、fEdges()endl;g.DeleteEdge(0, 4);/刪除邊 g.DeleteVertex(3);/刪除頂點(diǎn)3coutendl 頂點(diǎn)個(gè)數(shù)為: g.NumOfVertices();coutendl 邊的條數(shù)為: g.NumOfEdges() endl;GraphTest.cpp實(shí)現(xiàn)測試鄰接矩陣圖類ABCED40503010208.2.2 鄰接表(adjecency list)定義：對圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表。 無向圖：第i個(gè)鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊。 有向圖：第i個(gè)鏈表中的結(jié)點(diǎn)表示從Vi 發(fā)出的所有的 弧(以Vi為尾的弧)。 邊結(jié)點(diǎn)： weightnextdest鄰接點(diǎn)域

30、鏈域權(quán)值域頭結(jié)點(diǎn)：（頂點(diǎn)） adjheaddata頂點(diǎn)數(shù)據(jù)域鏈域123012 2 1 0例：132G1例：012312342 013 013 023 123124G2特征 (1) 若無向圖G有n個(gè)頂點(diǎn)，e條邊，則鄰接表需n個(gè)表頭結(jié)點(diǎn)和2e個(gè)邊結(jié)點(diǎn)；若有向圖G有n個(gè)頂點(diǎn)，e條邊，則鄰接表需n個(gè)表頭結(jié)點(diǎn)和e個(gè)邊結(jié)點(diǎn)。空間代價(jià)O(n+e)，故空間利用率高。. (2) 無向圖：第i個(gè)鏈表中的表結(jié)點(diǎn)數(shù)為TD(vi)； 有向圖：第i個(gè)鏈表中的表結(jié)點(diǎn)數(shù)為OD(vi)，不能求ID(vi) 。為便于求ID(vi) 可另外建立有向圖的逆鄰接表。 132G11230121 1 0 G1的逆鄰接表 (4) 鄰接表多用

31、于稀疏圖的存儲(chǔ)（en2) (3) 容易尋找頂點(diǎn)的鄰接點(diǎn)，但判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對應(yīng)的單鏈表。描述： struct EdgeListNode /*邊類*/int dest; /*與該頂點(diǎn)鄰接的鄰接頂點(diǎn)的序號(hào)*/WT weight;EdgeListNode *next; /*指向下一條邊或弧結(jié)點(diǎn)*/EdgeListNode(EdgeListNode * ptr =NULL):next(ptr)EdgeListNode(int d, WT w, EdgeListNode * ptr=NULL): dest(d), weight(w), next(ptr);struct Vertex /*頂點(diǎn)類*/VT data; /*頂點(diǎn)信息*/EdgeListNode *adjhead;/*指向第一條依附該頂點(diǎn)的邊*/Vertex(EdgeListNode * ptr =NULL):adjhead(ptr)Vertex(VT d, EdgeListNode * ptr =NULL):data(d), adjhead(ptr)