北京師范大學數(shù)據(jù)結(jié)構(gòu)教學資料 第8章——圖

1、精選ppt146-146-1 1n圖的基本概念圖的基本概念n圖的存儲表示圖的存儲表示n圖的遍歷與連通性圖的遍歷與連通性 n最小生成樹最小生成樹n最短路徑最短路徑 n活動網(wǎng)絡(luò)活動網(wǎng)絡(luò)第八章第八章 圖圖精選ppt146-146-2 2圖的基本概念圖的基本概念n圖定義圖定義 圖是由頂點集合圖是由頂點集合(vertex)及頂點間的及頂點間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)： Graph( V, E ) 其中其中 V = x | x 某個數(shù)據(jù)對象某個數(shù)據(jù)對象 是頂點的有窮非空集合；是頂點的有窮非空集合； E = (x, y) | x, y V 或或 E = | x, y V &am

2、p; Path (x, y) 是頂點之間關(guān)系的有窮集合，也叫做邊是頂點之間關(guān)系的有窮集合，也叫做邊(edge)集合。集合。Path (x, y)表示從表示從 x 到到 y 的一條單向通的一條單向通路路, 它是有方向的。它是有方向的。精選ppt146-146-3 3 n有向圖與無向圖有向圖與無向圖 在有向圖中，頂點對在有向圖中，頂點對 是有序的。在無向圖中，頂點對是有序的。在無向圖中，頂點對(x, y)是無序是無序的。的。n完全圖完全圖 若有若有 n 個頂點的無向圖有個頂點的無向圖有 n(n-1)/2 條條邊邊, 則此圖為完全無向圖。有則此圖為完全無向圖。有 n 個頂點的有向個頂點的有向圖有圖有

3、n(n-1) 條邊條邊, 則此圖為完全有向圖。則此圖為完全有向圖。00001111222265433精選ppt146-146-4 4 n鄰接頂點鄰接頂點 如果如果 (u, v) 是是 E(G) 中的一條邊，中的一條邊，則稱則稱 u 與與 v 互為鄰接頂點互為鄰接頂點。n子圖子圖 設(shè)有兩個圖設(shè)有兩個圖G(V, E) 和和G(V, E)。若若V V 且且E E, 則稱圖則稱圖G是圖是圖G的子圖。的子圖。n權(quán)權(quán) 某些圖的邊具有與它相關(guān)的數(shù)某些圖的邊具有與它相關(guān)的數(shù), 稱之為權(quán)。稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。子圖子圖01230130123023精選ppt146-146-5 5n頂點

4、的度頂點的度 一個頂點一個頂點v的度是與它相關(guān)聯(lián)的邊的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作的條數(shù)。記作TD(v)。在有向圖中。在有向圖中, 頂點的度頂點的度等于該頂點的入度與出度之和。等于該頂點的入度與出度之和。n頂點頂點 v 的入度的入度是以是以 v 為終點的有向邊的條數(shù)為終點的有向邊的條數(shù), 記作記作 ID(v); 頂點頂點 v 的出度的出度是以是以 v 為始點的有向為始點的有向邊的條數(shù)邊的條數(shù), 記作記作 OD(v)。n路徑路徑 在圖在圖 G(V, E) 中中, 若從頂點若從頂點 vi 出發(fā)出發(fā), 沿沿一些邊經(jīng)過一些頂點一些邊經(jīng)過一些頂點 vp1, vp2, , vpm，到達頂，到達頂點點vj

5、。則稱頂點序列。則稱頂點序列 (vi vp1 vp2 . vpm vj) 為從頂為從頂點點vi 到頂點到頂點 vj 的路徑。它經(jīng)過的邊的路徑。它經(jīng)過的邊(vi, vp1)、(vp1, vp2)、.、(vpm, vj) 應(yīng)是屬于應(yīng)是屬于E的邊。的邊。精選ppt146-146-6 6n路徑長度路徑長度 非帶權(quán)圖的路徑長度是指此路徑上非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。邊的權(quán)之和。n簡單路徑簡單路徑 若路徑上各頂點若路徑上各頂點 v1, v2, ., vm 均不均不 互相重復互相重復, 則稱這樣的路徑為簡單路徑。則稱這

6、樣的路徑為簡單路徑。n回路回路 若路徑上第一個頂點若路徑上第一個頂點 v1 與最后一個頂與最后一個頂點點vm 重合重合, 則稱這樣的路徑為回路或環(huán)。則稱這樣的路徑為回路或環(huán)。012301230123精選ppt146-146-7 7n連通圖與連通分量連通圖與連通分量 在在無向圖無向圖中中, 若從頂點若從頂點v1到頂點到頂點v2有路徑有路徑, 則稱頂點則稱頂點v1與與v2是連通的。是連通的。如果圖中任意一對頂點都是連通的如果圖中任意一對頂點都是連通的, 則稱此圖則稱此圖是連通圖。非連通圖的極大連通子圖叫做連是連通圖。非連通圖的極大連通子圖叫做連通分量。通分量。n強連通圖與強連通分量強連通圖與強連通

7、分量 在在有向圖有向圖中中, 若對于若對于每一對頂點每一對頂點vi和和vj, 都存在一條從都存在一條從vi到到vj和從和從vj到到vi的路徑的路徑, 則稱此圖是強連通圖。非強連通圖則稱此圖是強連通圖。非強連通圖的極大強連通子圖叫做強連通分量。的極大強連通子圖叫做強連通分量。n生成樹生成樹 一個連通圖的生成樹是其極小連通一個連通圖的生成樹是其極小連通子圖，在子圖，在 n 個頂點的情形下，有個頂點的情形下，有 n-1 條邊。條邊。精選ppt146-146-8 8圖的抽象數(shù)據(jù)類型圖的抽象數(shù)據(jù)類型class Graph /對象: 由一個頂點的非空集合和一個邊集合構(gòu)成/每條邊由一個頂點對來表示。publ

8、ic: Graph();/建立一個空的圖 void insertVertex (const T& vertex); /插入一個頂點vertex, 該頂點暫時沒有入邊 void insertEdge (int v1, int v2, int weight); /在圖中插入一條邊(v1, v2, w) void removeVertex (int v); /在圖中刪除頂點v和所有關(guān)聯(lián)到它的邊 精選ppt146-146-9 9 void removeEdge (int v1, int v2); /在圖中刪去邊(v1,v2) bool IsEmpty(); /若圖中沒有頂點, 則返回true,

9、 否則返回false T getWeight (int v1, int v2); /函數(shù)返回邊 (v1,v2) 的權(quán)值 int getFirstNeighbor (int v); /給出頂點 v 第一個鄰接頂點的位置 int getNextNeighbor (int v, int w); /給出頂點 v 的某鄰接頂點 w 的下一個鄰接頂點;精選ppt146-146-1010圖的存儲表示圖的存儲表示n圖的模板基類圖的模板基類 在模板類定義中的數(shù)據(jù)類型在模板類定義中的數(shù)據(jù)類型參數(shù)表參數(shù)表 中，中，T是頂點數(shù)據(jù)的是頂點數(shù)據(jù)的類型，類型，E是邊上所附數(shù)據(jù)的類型。是邊上所附數(shù)據(jù)的類型。n這個模板基類是按

10、照最復雜的情況（即帶權(quán)這個模板基類是按照最復雜的情況（即帶權(quán)無向圖）來定義的，如果需要使用非帶權(quán)圖，無向圖）來定義的，如果需要使用非帶權(quán)圖，可將數(shù)據(jù)類型參數(shù)表可將數(shù)據(jù)類型參數(shù)表 改為改為 。n如果使用的是有向圖，也可以對程序做相應(yīng)如果使用的是有向圖，也可以對程序做相應(yīng)的改動。的改動。 精選ppt146-146-11 11圖的模板基類圖的模板基類 const int maxWeight = ; /無窮大的值(= )const int DefaultVertices = 30; /最大頂點數(shù)(=n)template class Graph /圖的類定義protected: int maxVerti

11、ces; /圖中最大頂點數(shù) int numEdges; /當前邊數(shù) int numVertices; /當前頂點數(shù) int getVertexPos (T vertex); /給出頂點vertex在圖中位置public: 精選ppt146-146-1212 Graph (int sz = DefaultVertices); /構(gòu)造函數(shù) Graph();/析構(gòu)函數(shù) bool GraphEmpty () const /判圖空否 return numEdges = 0; int NumberOfVertices () return numVertices; /返回當前頂點數(shù) int NumberOf

12、Edges () return numEdges; /返回當前邊數(shù)virtual T getValue (int i);/取頂點 i 的值 virtual E getWeight (int v1, int v2); /取邊上權(quán)值 virtual int getFirstNeighbor (int v); /取頂點 v 的第一個鄰接頂點精選ppt146-146-1313virtual int getNextNeighbor (int v, int w); /取鄰接頂點 w 的下一鄰接頂點 virtual bool insertVertex (const T vertex); /插入一個頂點ver

13、tex virtual bool insertEdge (int v1, int v2, E cost); /插入邊(v1,v2), 權(quán)為cost virtual bool removeVertex (int v); /刪去頂點 v 和所有與相關(guān)聯(lián)邊 virtual bool removeEdge (int v1, int v2); /在圖中刪去邊(v1,v2);精選ppt146-146-1414鄰接矩陣鄰接矩陣 (Adjacency Matrix)(Adjacency Matrix)n在圖的鄰接矩陣表示中，有一個記錄各個頂在圖的鄰接矩陣表示中，有一個記錄各個頂點信息的點信息的頂點表頂點表，還

14、有一個表示各個頂點之，還有一個表示各個頂點之間關(guān)系的間關(guān)系的鄰接矩陣鄰接矩陣。n設(shè)圖設(shè)圖 A = (V, E) 是一個有是一個有 n 個頂點的圖個頂點的圖, 圖的圖的鄰接矩陣是一個二維數(shù)組鄰接矩陣是一個二維數(shù)組 A.edgenn，定義：，定義： , ),( , , .否否則則或或者者如如果果01EdgeAEjiEjiji精選ppt146-146-1515n無向圖的鄰接矩陣是對稱的無向圖的鄰接矩陣是對稱的;n有向圖的鄰接矩陣可能是不對稱的。有向圖的鄰接矩陣可能是不對稱的。0101101001011010A.edge0123012000101010A.edge精選ppt146-146-1616n在

15、有向圖中在有向圖中, 統(tǒng)計第統(tǒng)計第 i 行行 1 的個數(shù)可得頂點的個數(shù)可得頂點 i 的的出度出度，統(tǒng)計第，統(tǒng)計第 j 列列 1 的個數(shù)可得頂點的個數(shù)可得頂點 j 的的入入度度。n在無向圖中在無向圖中, 統(tǒng)計第統(tǒng)計第 i 行行 (列列) 1 的個數(shù)可得頂?shù)膫€數(shù)可得頂點點i 的的度度。網(wǎng)絡(luò)的鄰接矩陣網(wǎng)絡(luò)的鄰接矩陣jiji,ji,jiji,ji,jijiji若若或或且且若若或或且且若若,)(,)(),(0EEEEWA.edge精選ppt146-146-1717068053290410A.edge863129542031用鄰接矩陣表示的圖的類定義用鄰接矩陣表示的圖的類定義template class

16、Graphmtx : public Graph friend istream& operator ( istream& in, Graphmtx& G);/輸入精選ppt146-146-1818friend ostream& operator (ostream& out, Graphmtx& G);/輸出private: T *VerticesList; /頂點表 E *Edge;/鄰接矩陣int getVertexPos (T vertex) /給出頂點vertex在圖中的位置 for (int i = 0; i = 0 & i = n

17、umVertices ? VerticesListi : NULL; E getWeight (int v1, int v2) /取邊(v1,v2)上權(quán)值 return v1 != -1 & v2 != -1 ? Edgev1v2 : 0; int getFirstNeighbor (int v); /取頂點 v 的第一個鄰接頂點精選ppt146-146-2020 int getNextNeighbor (int v, int w); /取 v 的鄰接頂點 w 的下一鄰接頂點 bool insertVertex (const T vertex); /插入頂點vertex bool in

18、sertEdge (int v1, int v2, E cost); /插入邊(v1, v2),權(quán)值為cost bool removeVertex (int v); /刪去頂點 v 和所有與它相關(guān)聯(lián)的邊 bool removeEdge (int v1, int v2); /在圖中刪去邊(v1,v2);精選ppt146-146-2121template Graphmtx:Graphmtx (int sz) /構(gòu)造函數(shù) maxVertices = sz; numVertices = 0; numEdges = 0;int i, j;VerticesList = new TmaxVertices;

19、/創(chuàng)建頂點表 Edge = (int *) new int *maxVertices;for (i = 0; i maxVertices; i+) Edgei = new intmaxVertices; /鄰接矩陣 for (i = 0; i maxVertices; i+) /矩陣初始化 for (j = 0; j maxVertices; j+) Edgeij = (i = j) ？ 0 : maxWeight; 精選ppt146-146-2222template int Graphmtx:getFirstNeighbor (int v) /給出頂點位置為v的第一個鄰接頂點的位置, /如果

20、找不到, 則函數(shù)返回-1 if (v != -1) for (int col = 0; col numVertices; col+) if (Edgevcol & Edgevcol maxWeight) return col; return -1;精選ppt146-146-2323template int Graphmtx:getNextNeighbor (int v, int w) /給出頂點 v 的某鄰接頂點 w 的下一個鄰接頂點 if (v != -1 & w != -1) for (int col = w+1; col numVertices; col+) if (Ed

21、gevcol & Edgevcol maxWeight) return col; return -1;精選ppt146-146-2424n鄰接表是鄰接矩陣的改進形式。為此需要把鄰接表是鄰接矩陣的改進形式。為此需要把鄰接矩陣的各行分別組織為一個單鏈表。鄰接矩陣的各行分別組織為一個單鏈表。n在鄰接表中，同一個頂點發(fā)出的邊鏈接在同在鄰接表中，同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，每一個鏈結(jié)點代表一條邊一個邊鏈表中，每一個鏈結(jié)點代表一條邊（邊結(jié)點），結(jié)點中有另一頂點的下標（邊結(jié)點），結(jié)點中有另一頂點的下標 dest 和指針和指針 link。對于帶權(quán)圖，邊結(jié)點中還要保。對于帶權(quán)圖，邊結(jié)點中還要

22、保存該邊的權(quán)值存該邊的權(quán)值cost。n頂點表的第頂點表的第 i 個頂點中保存該頂點的數(shù)據(jù)，個頂點中保存該頂點的數(shù)據(jù)，以及它對應(yīng)邊鏈表的頭指針以及它對應(yīng)邊鏈表的頭指針adj。 鄰接表鄰接表 (Adjacency List)(Adjacency List)精選ppt146-146-2525ABCDdata adjABCD0123dest linkdest link 130210無向圖的鄰接表無向圖的鄰接表n統(tǒng)計某頂點對應(yīng)邊鏈表中結(jié)點個數(shù)，可得該頂統(tǒng)計某頂點對應(yīng)邊鏈表中結(jié)點個數(shù)，可得該頂點的度。點的度。n某條邊某條邊(vi, vj)在鄰接表中有兩個邊結(jié)點，分別在鄰接表中有兩個邊結(jié)點，分別在第在第 i

23、 個頂點和第個頂點和第 j 個頂點對應(yīng)的邊鏈表中。個頂點對應(yīng)的邊鏈表中。精選ppt146-146-2626data adjABC012dest linkdest link 鄰接表鄰接表 (出邊表出邊表)data adjABC012dest link逆鄰接表逆鄰接表 (入邊表入邊表)102 011有向圖的鄰接表和逆鄰接表有向圖的鄰接表和逆鄰接表ABC精選ppt146-146-2727BACD69528data adjABCD0123dest cost link 1 53 62 83 21 9(出邊表出邊表)(頂點表頂點表)網(wǎng)絡(luò)網(wǎng)絡(luò) ( (帶權(quán)圖帶權(quán)圖) ) 的鄰接表的鄰接表n統(tǒng)計出邊表中結(jié)點個數(shù)

24、，得到該頂點的出度；統(tǒng)計出邊表中結(jié)點個數(shù)，得到該頂點的出度；n統(tǒng)計入邊表中結(jié)點個數(shù)，得到該頂點的入度。統(tǒng)計入邊表中結(jié)點個數(shù)，得到該頂點的入度。精選ppt146-146-2828n在鄰接表的邊鏈表中，各個邊結(jié)點的鏈入順序在鄰接表的邊鏈表中，各個邊結(jié)點的鏈入順序任意，視邊結(jié)點輸入次序而定。任意，視邊結(jié)點輸入次序而定。n設(shè)圖中有設(shè)圖中有 n 個頂點，個頂點，e 條邊，則用鄰接表表示條邊，則用鄰接表表示無向圖時，需要無向圖時，需要 n 個頂點結(jié)點，個頂點結(jié)點，2e 個邊結(jié)點；個邊結(jié)點；用鄰接表表示有向圖時，若不考慮逆鄰接表，用鄰接表表示有向圖時，若不考慮逆鄰接表，只需只需 n 個頂點結(jié)點，個頂點結(jié)點，

25、e 個邊結(jié)點。個邊結(jié)點。n當當 e 遠遠小于遠遠小于 n2 時，可以節(jié)省大量的存儲空時，可以節(jié)省大量的存儲空間。此外，把同一個頂點的所有邊鏈接在一個間。此外，把同一個頂點的所有邊鏈接在一個單鏈表中，也使得圖的操作更為便捷。單鏈表中，也使得圖的操作更為便捷。 精選ppt146-146-2929用鄰接表表示的圖的類定義用鄰接表表示的圖的類定義 template struct Edge /邊結(jié)點的定義 int dest; /邊的另一頂點位置 E cost; /邊上的權(quán)值 Edge *link; /下一條邊鏈指針 Edge () /構(gòu)造函數(shù) Edge (int num, E cost) /構(gòu)造函數(shù) :

26、 dest (num), weight (cost), link (NULL) bool operator != (Edge& R) const return dest != ; /判邊等否;精選ppt146-146-3030template struct Vertex /頂點的定義 T data; /頂點的名字Edge *adj; /邊鏈表的頭指針;template class Graphlnk : public Graph /圖的類定義friend istream& operator (istream& in, Graphlnk& G); /輸入friend

27、 ostream& operator (ostream& out, Graphlnk& G); /輸出精選ppt146-146-3131private: Vertex *NodeTable; /頂點表 (各邊鏈表的頭結(jié)點) int getVertexPos (const T vertx) /給出頂點vertex在圖中的位置 for (int i = 0; i = 0 & i NumVertices) ? NodeTablei.data : 0; E getWeight (int v1, int v2); /取邊(v1,v2)權(quán)值bool insertVertex

28、 (const T& vertex); bool removeVertex (int v); bool insertEdge (int v1, int v2, E cost);bool removeEdge (int v1, int v2); int getFirstNeighbor (int v); int getNextNeighbor (int v, int w);精選ppt146-146-3333template Graphlnk:Graphlnk (int sz) /構(gòu)造函數(shù)：建立一個空的鄰接表 maxVertices = sz; numVertices = 0; numEd

29、ges = 0; NodeTable = new VertexmaxVertices;/創(chuàng)建頂點表數(shù)組 if (NodeTable = NULL) cerr 存儲分配錯！存儲分配錯！ endl; exit(1); for (int i = 0; i maxVertices; i+) NodeTablei.adj = NULL;精選ppt146-146-3434template Graphlnk:Graphlnk() /析構(gòu)函數(shù)：刪除一個鄰接表 for (int i = 0; i numVertices; i+ ) Edge *p = NodeTablei.adj; while (p != NU

30、LL) NodeTablei.adj = p-link; delete p; p = NodeTablei.adj; delete NodeTable; /刪除頂點表數(shù)組精選ppt146-146-3535template int Graphlnk:getFirstNeighbor (int v) /給出頂點位置為 v 的第一個鄰接頂點的位置, /如果找不到, 則函數(shù)返回-1 if (v != -1) /頂點頂點v存在存在 Edge *p = NodeTablev.adj;/對應(yīng)邊鏈表第一個邊結(jié)點if (p != NULL) return p-dest;/存在, 返回第一個鄰接頂點 return

31、 -1;/第一個鄰接頂點不存在精選ppt146-146-3636template int Graphlnk:getNextNeighbor (int v, int w) /給出頂點v的鄰接頂點w的下一個鄰接頂點的位置,/若沒有下一個鄰接頂點, 則函數(shù)返回-1 if (v != -1) /頂點v存在 Edge *p = NodeTablev.adj; while (p != NULL & p-dest != w) p = p-link; if (p != NULL & p-link != NULL) return p-link-dest; /返回下一個鄰接頂點 return -

32、-1; /下一鄰接頂點不存在精選ppt146-146-3737鄰接多重表鄰接多重表 (Adjacency Multilist)(Adjacency Multilist)n在鄰接多重表中在鄰接多重表中, 每一條邊只有一個邊結(jié)點。每一條邊只有一個邊結(jié)點。為有關(guān)邊的處理提供了方便。為有關(guān)邊的處理提供了方便。n無向圖的情形無向圖的情形u邊結(jié)點的結(jié)構(gòu)邊結(jié)點的結(jié)構(gòu)n其中其中, mark 是記錄是否處理過的標記是記錄是否處理過的標記; vertex1和和vertex2是該邊兩頂點位置。是該邊兩頂點位置。path1域是鏈接域是鏈接指針指針, 指向下一條依附頂點指向下一條依附頂點vertex1的邊；的邊；pat

33、h2 是指向下一條依附頂點是指向下一條依附頂點vertex2的邊鏈接指針。的邊鏈接指針。 mark vertex1 vertex2 path1 path2精選ppt146-146-3838n需要時還可設(shè)置一個存放與該邊相關(guān)的權(quán)值的需要時還可設(shè)置一個存放與該邊相關(guān)的權(quán)值的域域 cost。u頂點結(jié)點的結(jié)構(gòu)頂點結(jié)點的結(jié)構(gòu)n頂點信息的結(jié)點表以順序表方式組織頂點信息的結(jié)點表以順序表方式組織, 每一個頂每一個頂點結(jié)點有兩個數(shù)據(jù)成員：其中，點結(jié)點有兩個數(shù)據(jù)成員：其中，data 存放與該存放與該頂點相關(guān)的信息，頂點相關(guān)的信息，F(xiàn)irstout 是指示第一條依附該是指示第一條依附該頂點的邊的指針。頂點的邊的指針

34、。n在鄰接多重表中在鄰接多重表中, 所有依附同一個頂點的邊都所有依附同一個頂點的邊都鏈接在同一個單鏈表中。鏈接在同一個單鏈表中。 data Firstout精選ppt146-146-3939mark vtx1 vtx2 path1 path2 0 10 21 3e1e2e3data FoutABCD0123e1e2e3ABCDn從頂點從頂點 i 出發(fā)出發(fā), 可以循鏈找到所有依附于該頂可以循鏈找到所有依附于該頂點的邊，也可以找到它的所有鄰接頂點。點的邊，也可以找到它的所有鄰接頂點。鄰接多重表的結(jié)構(gòu)鄰接多重表的結(jié)構(gòu)精選ppt146-146-4040n有向圖的情形有向圖的情形n在用鄰接表表示有向圖時

35、在用鄰接表表示有向圖時, 有時需要同時使用有時需要同時使用鄰接表和逆鄰接表。用有向圖的鄰接多重表鄰接表和逆鄰接表。用有向圖的鄰接多重表(十字鏈表十字鏈表)可把兩個表結(jié)合起來表示?？砂褍蓚€表結(jié)合起來表示。u邊結(jié)點的結(jié)構(gòu)邊結(jié)點的結(jié)構(gòu)n其中，其中，mark是處理標記；是處理標記；vertex1和和vertex2指指明該有向邊始頂點和終頂點的位置。明該有向邊始頂點和終頂點的位置。path1是是指向指向始頂點與該邊相同始頂點與該邊相同的下一條邊的指針；的下一條邊的指針；path2是指向是指向終頂點與該邊相同終頂點與該邊相同的下一條邊的的下一條邊的指針。需要時還可有權(quán)值域指針。需要時還可有權(quán)值域cost。

36、 mark vertex1 vertex2 path1 path2精選ppt146-146-4141u頂點結(jié)點的結(jié)構(gòu)頂點結(jié)點的結(jié)構(gòu)n每個頂點有一個結(jié)點，它相當于出邊表和入邊每個頂點有一個結(jié)點，它相當于出邊表和入邊表的表頭結(jié)點：其中，數(shù)據(jù)成員表的表頭結(jié)點：其中，數(shù)據(jù)成員data存放與該存放與該頂點相關(guān)的信息，指針頂點相關(guān)的信息，指針Firstout 指示以該頂點指示以該頂點為始頂點的出邊表的第一條邊，為始頂點的出邊表的第一條邊，F(xiàn)irstin 指示以指示以該頂點為終頂點的入邊表的第一條邊。該頂點為終頂點的入邊表的第一條邊。 data Firstin Firstout精選ppt146-146-42

37、42mark vtx1 vtx2 path1 path2 0 10 31 22 33 44 0e1e2e3e4e5e6data Fin FoutABCDE01234e1e2e3e4e5e6ABCDE鄰接多重表的結(jié)構(gòu)鄰接多重表的結(jié)構(gòu)精選ppt146-146-4343畫出在下圖所表示的有向圖中刪畫出在下圖所表示的有向圖中刪除頂點除頂點V3V3后的十字鏈表存儲結(jié)構(gòu)圖后的十字鏈表存儲結(jié)構(gòu)圖。精選ppt146-146-4444圖的遍歷與連通性圖的遍歷與連通性n從已給的連通圖中某一頂點出發(fā)，沿著一些邊從已給的連通圖中某一頂點出發(fā)，沿著一些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問訪遍圖中所有的頂點，且使每

38、個頂點僅被訪問一次，就叫做圖的遍歷一次，就叫做圖的遍歷 (Graph Traversal)。n圖中可能存在回路，且圖的任一頂點都可能與圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。沿著某些邊又回到了曾經(jīng)訪問過的頂點。n為了避免重復訪問，可設(shè)置一個標志頂點是否為了避免重復訪問，可設(shè)置一個標志頂點是否被訪問過的輔助數(shù)組被訪問過的輔助數(shù)組 visited 。精選ppt146-146-4545n輔助數(shù)組輔助數(shù)組visited 的初始狀態(tài)為的初始狀態(tài)為 0, 在圖的遍在圖的遍歷過程中歷過程中,

39、一旦某一個頂點一旦某一個頂點 i 被訪問被訪問, 就立即就立即讓讓visitedi為為 1, 防止它被多次訪問。防止它被多次訪問。n圖的遍歷的分類圖的遍歷的分類:u深度優(yōu)先搜索深度優(yōu)先搜索 DFS (Depth First Search)u廣度優(yōu)先搜索廣度優(yōu)先搜索 BFS (Breadth First Search)精選ppt146-146-4646深度優(yōu)先搜索深度優(yōu)先搜索DFSDFS (Depth First Search)(Depth First Search)n深度優(yōu)先搜索的示例深度優(yōu)先搜索的示例ACDEGBFIHACDEGBFIH123456789123456789前進回退深度優(yōu)先搜索

40、過程深度優(yōu)先搜索過程 深度優(yōu)先生成樹深度優(yōu)先生成樹精選ppt146-146-4747nDFS 在訪問圖中某一在訪問圖中某一起始頂點起始頂點 v 后后, 由由 v 出發(fā)出發(fā), 訪問它的任一訪問它的任一鄰接頂點鄰接頂點 w1; 再從再從 w1 出發(fā)出發(fā), 訪問訪問與與 w1鄰鄰 接接但還但還沒有訪問過的頂點沒有訪問過的頂點 w2; 然后再然后再從從 w2 出發(fā)出發(fā), 進行類似的訪問進行類似的訪問, 如此進行下去如此進行下去, 直至到達所有的鄰接頂點都被訪問過的頂點直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。為止。接著接著, 退回一步退回一步, 退到前一次剛訪問過退到前一次剛訪問過的頂點的頂點

41、, 看是否還有其它沒有被訪問的鄰接頂看是否還有其它沒有被訪問的鄰接頂點。點。如果有如果有, 則訪問此頂點則訪問此頂點, 之后再從此頂點出之后再從此頂點出發(fā)發(fā), 進行與前述類似的訪問進行與前述類似的訪問; 如果沒有如果沒有, 就再退就再退回一步進行搜索。重復上述過程回一步進行搜索。重復上述過程, 直到連通圖直到連通圖中所有頂點都被訪問過為止。中所有頂點都被訪問過為止。精選ppt146-146-4848圖的深度優(yōu)先搜索算法圖的深度優(yōu)先搜索算法template void DFS (Graph& G, const T& v) /從頂點v出發(fā)對圖G進行深度優(yōu)先遍歷的主過程 int i,

42、loc, n = G.NumberOfVertices(); /頂點個數(shù) bool *visited = new booln; /創(chuàng)建輔助數(shù)組 for (i = 0; i n; i+) visited i = false; /輔助數(shù)組visited初始化loc = G.getVertexPos(v); DFS (G, loc, visited); /從頂點0開始深度優(yōu)先搜索 delete visited; /釋放visited精選ppt146-146-4949templatevoid DFS (Graph& G, int v, bool visited) cout G.getValue

43、(v) ; /訪問頂點v visitedv = true; /作訪問標記 int w = G.getFirstNeighbor (v); /第一個鄰接頂點 while (w != -1) /若鄰接頂點w存在 if ( !visitedw ) DFS(G, w, visited); /若w未訪問過, 遞歸訪問頂點w w = G.getNextNeighbor (v, w); /下一個鄰接頂點 精選ppt146-146-5050廣度優(yōu)先搜索廣度優(yōu)先搜索BFSBFS (Breadth First Search)(Breadth First Search)n廣度優(yōu)先搜索的示例廣度優(yōu)先搜索的示例廣度優(yōu)先

44、搜索過程廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹廣度優(yōu)先生成樹ACDEGBFIHACDEGBFH123456789123456789I精選ppt146-146-5151nBFS在訪問了起始頂點在訪問了起始頂點 v 之后之后, 由由 v 出發(fā)出發(fā), 依次依次訪問訪問 v 的各個未被訪問過的鄰接頂點的各個未被訪問過的鄰接頂點 w1, w2, , wt, 然后再順序訪問然后再順序訪問 w1, w2, , wt 的所的所有還未被訪問過的鄰接頂點。再從這些訪問有還未被訪問過的鄰接頂點。再從這些訪問過的頂點出發(fā)，再訪問它們的所有還未被訪過的頂點出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點，問過的鄰接頂點， 如此做

45、下去，直到圖中如此做下去，直到圖中所有頂點都被訪問到為止。所有頂點都被訪問到為止。n廣度優(yōu)先搜索是一種分層的搜索過程廣度優(yōu)先搜索是一種分層的搜索過程, 每向前每向前走一步可能訪問一批頂點走一步可能訪問一批頂點, 不像深度優(yōu)先搜索不像深度優(yōu)先搜索那樣有往回退的情況。因此那樣有往回退的情況。因此, 廣度優(yōu)先搜索不廣度優(yōu)先搜索不是一個遞歸的過程。是一個遞歸的過程。精選ppt146-146-5252n為了實現(xiàn)逐層訪問為了實現(xiàn)逐層訪問, 算法中使用了一個隊列算法中使用了一個隊列, 以以記憶正在訪問的這一層和上一層的頂點記憶正在訪問的這一層和上一層的頂點, 以便以便于向下一層訪問。于向下一層訪問。n為避免

46、重復訪問為避免重復訪問, 需要一個輔助數(shù)組需要一個輔助數(shù)組 visited ，給被訪問過的頂點加標記。給被訪問過的頂點加標記。template void BFS (Graph& G, const T& v) int i, w, n = G.NumberOfVertices(); /圖中頂點個數(shù)圖的廣度優(yōu)先搜索算法圖的廣度優(yōu)先搜索算法精選ppt146-146-5353 bool *visited = new booln; for (i = 0; i n; i+) visitedi = false; int loc = G.getVertexPos (v);/取頂點號 cout G

47、.getValue (loc) ; /訪問頂點v visitedloc = true; /做已訪問標記 Queue Q; Q.EnQueue (loc); /頂點進隊列, 實現(xiàn)分層訪問 while (!Q.IsEmpty() ) /循環(huán), 訪問所有結(jié)點 Q.DeQueue (loc); w = G.getFirstNeighbor (loc); /第一個鄰接頂點 while (w != -1) /若鄰接頂點w存在 if (!visitedw) /若未訪問過精選ppt146-146-5454 cout G.getValue (w) ;/訪問 visitedw = true; Q.EnQueue

48、(w); /頂點w進隊列 w = G.getNextNeighbor (loc, w); /找頂點loc的下一個鄰接頂點 /外層循環(huán)，判隊列空否 delete visited;精選ppt146-146-5555連通分量連通分量 (Connected component)(Connected component)n當無向圖為非連通圖時，從圖中某一頂點出當無向圖為非連通圖時，從圖中某一頂點出發(fā)，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索發(fā)，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點，只能訪算法不可能遍歷到圖中的所有頂點，只能訪問到該頂點所在最大連通子圖問到該頂點所在最大連通子圖（連通

49、分量）（連通分量）的的所有頂點。所有頂點。n若從無向圖每一連通分量中的一個頂點出發(fā)若從無向圖每一連通分量中的一個頂點出發(fā)進行遍歷進行遍歷, 可求得無向圖的所有連通分量?？汕蟮脽o向圖的所有連通分量。n例如，對于非連通的無向圖，所有連通分量例如，對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。的生成樹組成了非連通圖的生成森林。精選ppt146-146-5656ACDEBFGOIHJNMLK非連通無向圖AHKCDEIBFOGJNML非連通圖的連通分量精選ppt146-146-5757確定連通分量的算法確定連通分量的算法template void Components (Graph&

50、amp; G) /通過DFS，找出無向圖的所有連通分量 int i, n = G.NumberOfVertices(); /圖中頂點個數(shù) bool *visited = new booln; /訪問標記數(shù)組 for (i = 0; i n; i+) visitedi = false; for (i = 0; i n; i+) /掃描所有頂點 if (!visitedi) /若沒有訪問過 DFS (G, i, visited);/訪問 OutputNewComponent(); /輸出連通分量 精選ppt146-146-5858 delete visited; n例：以深度優(yōu)先搜索方法從頂點例：

51、以深度優(yōu)先搜索方法從頂點 出發(fā)遍歷出發(fā)遍歷圖圖, 建立深度優(yōu)先生成森林。建立深度優(yōu)先生成森林。AABCDEFGABDECFG精選ppt146-146-5959template void DFS_Forest (Graph& G, Tree & F) TreeNode * rt, * subT; int n = G.NumberOfVertices(); static int *visited = new intn; /訪問數(shù)組 for (int i = 0; i n; i+) visited i = 0; for (i = 0; i n; i+) /遍歷所有頂點 if (!vi

52、sitedi) /頂點 i 未訪問過 if (F.IsEmpty() /F原為空生成森林,建根 subT = rt = F.BuildRoot(G.GetValue(i); /頂點 i 的值成為根 rt 的值 精選ppt146-146-6060 else (subT, G.GetValue(i); /頂點 i 的值成為 subT 右兄弟的值 DFS_Tree (G, F, subT, i, visited); /從頂點 i 出發(fā)深度優(yōu)先遍歷, 建子樹 template void DFS_Tree (Graph& G, Tree&F, TreeNode * rt, int v,

53、int visited ) TreeNode * p;精選ppt146-146-6161 visitedv = 1; /頂點 作訪問過標志 int w = G.GetFirstNeighbor (v); /取頂點v的第一個鄰接頂點 int FirstChild = 1; /第一個未訪問子女應(yīng)是 的左子女 while ( w != -1 ) /鄰接頂點 存在 if (! visited w) / 未訪問過, 將成為 的子女 if (FirstChild) p = F.InsertLeftChild (rt, G.GetValue(w); / 插入為 的左子女精選ppt146-146-6262 F

54、irstChild = 0; /建右兄弟 else (p, G.GetValue(w); /p插入為 p 的左子女 DFS_Tree (G, F, p, w, visited); /遞歸建立 w 的以 p 為根的子樹 /鄰接頂點 w 處理完 w = G.GetNextNeighbor (v, w); /取 v 的下一個鄰接頂點 w /回到 while 判鄰接頂點 w 存在; 精選ppt146-146-6363重連通分量重連通分量 (Biconnected Component)(Biconnected Component)n在無向連通圖在無向連通圖G中中, 當且僅當刪去當且僅當刪去G中的頂點中的

55、頂點v及所有依附于及所有依附于v的所有邊后的所有邊后, 可將圖分割成兩個可將圖分割成兩個或兩個以上的連通分量，則稱頂點或兩個以上的連通分量，則稱頂點v為為關(guān)節(jié)點關(guān)節(jié)點。n沒有沒有關(guān)節(jié)點關(guān)節(jié)點的連通圖叫做重連通圖。的連通圖叫做重連通圖。n在重連通圖上在重連通圖上, 任何一對頂點之間至少存在有任何一對頂點之間至少存在有兩條路徑兩條路徑, 在刪去某個頂點及與該頂點相關(guān)聯(lián)在刪去某個頂點及與該頂點相關(guān)聯(lián)的邊時的邊時, 也不破壞圖的連通性。也不破壞圖的連通性。精選ppt146-146-6464n一個連通圖一個連通圖G如果不是重連通圖，那么它可以如果不是重連通圖，那么它可以包括幾個重連通分量。包括幾個重連通

56、分量。n在一個無向連通圖在一個無向連通圖G中中, 重連通分量可以利用重連通分量可以利用深度優(yōu)先生成樹找到。深度優(yōu)先生成樹找到。n在圖中各在圖中各頂點旁標明的深度優(yōu)先數(shù)頂點旁標明的深度優(yōu)先數(shù), 給出進行給出進行深度優(yōu)先搜索時各頂點訪問的次序。深度優(yōu)先搜索時各頂點訪問的次序。n深度優(yōu)先生成樹的深度優(yōu)先生成樹的根是根是關(guān)節(jié)點關(guān)節(jié)點的充要條件是它的充要條件是它至少有兩個子女至少有兩個子女。n其它頂點其它頂點 u 是是關(guān)節(jié)點關(guān)節(jié)點的充要條件是它至少有一的充要條件是它至少有一個子女個子女 w, 從從 w 出發(fā)出發(fā), 不能通過不能通過 w、w 的子孫及的子孫及一條回邊所組成的路徑到達一條回邊所組成的路徑到達

57、 u 的祖先的祖先。精選ppt146-146-6565ABCDEFGHIJABCDEFGHJABCDEFGHJII12345678910根有兩根有兩 個子女個子女精選ppt146-146-6666最小生成樹最小生成樹 ( minimum cost spanning tree )( minimum cost spanning tree )n使用不同的遍歷圖的方法，可以得到不同的生使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。生成樹。n按照生成樹的定義，按照生成樹的定義，n 個頂點的連通網(wǎng)絡(luò)的生個頂點的連通網(wǎng)絡(luò)的生成

58、樹有成樹有 n 個頂點、個頂點、n-1條邊。條邊。n構(gòu)造最小生成樹構(gòu)造最小生成樹 假設(shè)有一個網(wǎng)絡(luò)，用以表示假設(shè)有一個網(wǎng)絡(luò)，用以表示 n 個城市之間架設(shè)通信線路，邊上的權(quán)值代表個城市之間架設(shè)通信線路，邊上的權(quán)值代表架設(shè)通信線路的成本。如何架設(shè)才能使線路架架設(shè)通信線路的成本。如何架設(shè)才能使線路架設(shè)的成本達到最小？設(shè)的成本達到最?。烤xppt146-146-6767n構(gòu)造最小生成樹的準則構(gòu)造最小生成樹的準則v必須使用且僅使用該網(wǎng)絡(luò)中的必須使用且僅使用該網(wǎng)絡(luò)中的 n-1 條邊條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的來聯(lián)結(jié)網(wǎng)絡(luò)中的 n 個頂點；個頂點；v不能使用產(chǎn)生回路的邊；不能使用產(chǎn)生回路的邊；v各邊上的權(quán)值的總和達到最小

59、。各邊上的權(quán)值的總和達到最小。北京北京 天津天津南京南京上海上海廣州廣州西安西安成都成都昆明昆明武漢武漢34764158312419253822221931394450精選ppt146-146-6868北京北京 天津天津南京南京上海上海廣州廣州西安西安成都成都昆明昆明武漢武漢76241922221931北京北京 天津天津南京南京上海上海廣州廣州西安西安成都成都昆明昆明武漢武漢34764158312419253822221931394450精選ppt146-146-6969克魯斯卡爾克魯斯卡爾 (Kruskal) (Kruskal) 算法算法n克魯斯卡爾算法的基本思想：克魯斯卡爾算法的基本思想：

60、設(shè)有一個有設(shè)有一個有 n 個頂點的連通網(wǎng)絡(luò)個頂點的連通網(wǎng)絡(luò) N = V, E , 最初先構(gòu)造一個只有最初先構(gòu)造一個只有 n 個頂點個頂點, 沒有邊的非連沒有邊的非連通圖通圖 T = V, , 圖中每個頂點自成一個連通圖中每個頂點自成一個連通分量。當在分量。當在 E 中選到一條具有最小權(quán)值的邊中選到一條具有最小權(quán)值的邊時時, 若該邊的兩個頂點落在不同的連通分量上，若該邊的兩個頂點落在不同的連通分量上，則將此邊加入到則將此邊加入到 T 中中; 否則將此邊舍去，重新否則將此邊舍去，重新選擇一條權(quán)值最小的邊。如此重復下去選擇一條權(quán)值最小的邊。如此重復下去, 直到直到所有頂點在同一個連通分量上為止。所有頂點在同一個連通分量上為止。精選ppt146-146-7070KruskalKruskal算法的偽代碼描述算法的偽代碼描述 T = ;/T是最小生成樹的邊集合是最小生成樹的邊集合 /E是帶權(quán)無向圖的邊集合是帶權(quán)無向圖的邊集合while ( T 包含的邊少于包含的邊少于n-1