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

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

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

3、n(n-1) 條邊條邊, 則此圖為完全有向圖。則此圖為完全有向圖。00001111222265433精選ppt146-146-4 4 n鄰接頂點(diǎn)鄰接頂點(diǎn) 如果如果 (u, v) 是是 E(G) 中的一條邊，中的一條邊，則稱則稱 u 與與 v 互為鄰接頂點(diǎn)互為鄰接頂點(diǎn)。n子圖子圖 設(shè)有兩個(gè)圖設(shè)有兩個(gè)圖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頂點(diǎn)

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

5、。則稱頂點(diǎn)序列。則稱頂點(diǎn)序列 (vi vp1 vp2 . vpm vj) 為從頂為從頂點(diǎn)點(diǎn)vi 到頂點(diǎn)到頂點(diǎn) 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簡單路徑簡單路徑 若路徑上各頂點(diǎn)若路徑上各頂點(diǎn) v1, v2, ., vm 均不均不 互相重復(fù)互相重復(fù), 則稱這樣的路徑為簡單路徑。則稱這

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

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

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

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

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

11、ces; /圖中最大頂點(diǎn)數(shù) int numEdges; /當(dāng)前邊數(shù) int numVertices; /當(dāng)前頂點(diǎn)數(shù) int getVertexPos (T vertex); /給出頂點(diǎn)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; /返回當(dāng)前頂點(diǎn)數(shù) int NumberOf

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

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

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

15、有向圖中在有向圖中, 統(tǒng)計(jì)第統(tǒng)計(jì)第 i 行行 1 的個(gè)數(shù)可得頂點(diǎn)的個(gè)數(shù)可得頂點(diǎn) i 的的出度出度，統(tǒng)計(jì)第，統(tǒng)計(jì)第 j 列列 1 的個(gè)數(shù)可得頂點(diǎn)的個(gè)數(shù)可得頂點(diǎn) j 的的入入度度。n在無向圖中在無向圖中, 統(tǒng)計(jì)第統(tǒng)計(jì)第 i 行行 (列列) 1 的個(gè)數(shù)可得頂?shù)膫€(gè)數(shù)可得頂點(diǎn)點(diǎn)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; /頂點(diǎn)表 E *Edge;/鄰接矩陣int getVertexPos (T vertex) /給出頂點(diǎn)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); /取頂點(diǎn) v 的第一個(gè)鄰接頂點(diǎn)精選ppt146-146-2020 int getNextNeighbor (int v, int w); /取 v 的鄰接頂點(diǎn) w 的下一鄰接頂點(diǎn) bool insertVertex (const T vertex); /插入頂點(diǎn)vertex bool in

18、sertEdge (int v1, int v2, E cost); /插入邊(v1, v2),權(quán)值為cost bool removeVertex (int v); /刪去頂點(diǎn) 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)建頂點(diǎn)表 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) /給出頂點(diǎn)位置為v的第一個(gè)鄰接頂點(diǎn)的位置, /如果

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) /給出頂點(diǎn) v 的某鄰接頂點(diǎn) w 的下一個(gè)鄰接頂點(diǎn) 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鄰接表是鄰接矩陣的改進(jìn)形式。為此需要把鄰接表是鄰接矩陣的改進(jìn)形式。為此需要把鄰接矩陣的各行分別組織為一個(gè)單鏈表。鄰接矩陣的各行分別組織為一個(gè)單鏈表。n在鄰接表中，同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同在鄰接表中，同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)邊鏈表中，每一個(gè)鏈結(jié)點(diǎn)代表一條邊一個(gè)邊鏈表中，每一個(gè)鏈結(jié)點(diǎn)代表一條邊（邊結(jié)點(diǎn)），結(jié)點(diǎn)中有另一頂點(diǎn)的下標(biāo)（邊結(jié)點(diǎn)），結(jié)點(diǎn)中有另一頂點(diǎn)的下標(biāo) dest 和指針和指針 link。對于帶權(quán)圖，邊結(jié)點(diǎn)中還要保。對于帶權(quán)圖，邊結(jié)點(diǎn)中還要

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

23、 個(gè)頂點(diǎn)和第個(gè)頂點(diǎn)和第 j 個(gè)頂點(diǎn)對應(yīng)的邊鏈表中。個(gè)頂點(diǎn)對應(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(出邊表出邊表)(頂點(diǎn)表頂點(diǎn)表)網(wǎng)絡(luò)網(wǎng)絡(luò) ( (帶權(quán)圖帶權(quán)圖) ) 的鄰接表的鄰接表n統(tǒng)計(jì)出邊表中結(jié)點(diǎn)個(gè)數(shù)

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

25、e 個(gè)邊結(jié)點(diǎn)。個(gè)邊結(jié)點(diǎn)。n當(dāng)當(dāng) e 遠(yuǎn)遠(yuǎn)小于遠(yuǎn)遠(yuǎn)小于 n2 時(shí)，可以節(jié)省大量的存儲空時(shí)，可以節(jié)省大量的存儲空間。此外，把同一個(gè)頂點(diǎn)的所有邊鏈接在一個(gè)間。此外，把同一個(gè)頂點(diǎn)的所有邊鏈接在一個(gè)單鏈表中，也使得圖的操作更為便捷。單鏈表中，也使得圖的操作更為便捷。 精選ppt146-146-2929用鄰接表表示的圖的類定義用鄰接表表示的圖的類定義 template struct Edge /邊結(jié)點(diǎn)的定義 int dest; /邊的另一頂點(diǎn)位置 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 /頂點(diǎn)的定義 T data; /頂點(diǎn)的名字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; /頂點(diǎn)表 (各邊鏈表的頭結(jié)點(diǎn)) int getVertexPos (const T vertx) /給出頂點(diǎn)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ù)：建立一個(gè)空的鄰接表 maxVertices = sz; numVertices = 0; numEd

29、ges = 0; NodeTable = new VertexmaxVertices;/創(chuàng)建頂點(diǎn)表數(shù)組 if (NodeTable = NULL) cerr 存儲分配錯(cuò)！存儲分配錯(cuò)！ endl; exit(1); for (int i = 0; i maxVertices; i+) NodeTablei.adj = NULL;精選ppt146-146-3434template Graphlnk:Graphlnk() /析構(gòu)函數(shù)：刪除一個(gè)鄰接表 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; /刪除頂點(diǎn)表數(shù)組精選ppt146-146-3535template int Graphlnk:getFirstNeighbor (int v) /給出頂點(diǎn)位置為 v 的第一個(gè)鄰接頂點(diǎn)的位置, /如果找不到, 則函數(shù)返回-1 if (v != -1) /頂點(diǎn)頂點(diǎn)v存在存在 Edge *p = NodeTablev.adj;/對應(yīng)邊鏈表第一個(gè)邊結(jié)點(diǎn)if (p != NULL) return p-dest;/存在, 返回第一個(gè)鄰接頂點(diǎn) return

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

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

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

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

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

36、 mark vertex1 vertex2 path1 path2精選ppt146-146-4141u頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)n每個(gè)頂點(diǎn)有一個(gè)結(jié)點(diǎn)，它相當(dāng)于出邊表和入邊每個(gè)頂點(diǎn)有一個(gè)結(jié)點(diǎn)，它相當(dāng)于出邊表和入邊表的表頭結(jié)點(diǎn)：其中，數(shù)據(jù)成員表的表頭結(jié)點(diǎn)：其中，數(shù)據(jù)成員data存放與該存放與該頂點(diǎn)相關(guān)的信息，指針頂點(diǎn)相關(guān)的信息，指針Firstout 指示以該頂點(diǎn)指示以該頂點(diǎn)為始頂點(diǎn)的出邊表的第一條邊，為始頂點(diǎn)的出邊表的第一條邊，F(xiàn)irstin 指示以指示以該頂點(diǎn)為終頂點(diǎn)的入邊表的第一條邊。該頂點(diǎn)為終頂點(diǎn)的入邊表的第一條邊。 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畫出在下圖所表示的有向圖中刪畫出在下圖所表示的有向圖中刪除頂點(diǎn)除頂點(diǎn)V3V3后的十字鏈表存儲結(jié)構(gòu)圖后的十字鏈表存儲結(jié)構(gòu)圖。精選ppt146-146-4444圖的遍歷與連通性圖的遍歷與連通性n從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問訪遍圖中所有的頂點(diǎn)，且使每

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

39、一旦某一個(gè)頂點(diǎn)一旦某一個(gè)頂點(diǎn) 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前進(jìn)回退深度優(yōu)先搜索

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

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

42、loc, n = G.NumberOfVertices(); /頂點(diǎn)個(gè)數(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); /從頂點(diǎn)0開始深度優(yōu)先搜索 delete visited; /釋放visited精選ppt146-146-4949templatevoid DFS (Graph& G, int v, bool visited) cout G.getValue

43、(v) ; /訪問頂點(diǎn)v visitedv = true; /作訪問標(biāo)記 int w = G.getFirstNeighbor (v); /第一個(gè)鄰接頂點(diǎn) while (w != -1) /若鄰接頂點(diǎn)w存在 if ( !visitedw ) DFS(G, w, visited); /若w未訪問過, 遞歸訪問頂點(diǎn)w w = G.getNextNeighbor (v, w); /下一個(gè)鄰接頂點(diǎn) 精選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在訪問了起始頂點(diǎn)在訪問了起始頂點(diǎn) v 之后之后, 由由 v 出發(fā)出發(fā), 依次依次訪問訪問 v 的各個(gè)未被訪問過的鄰接頂點(diǎn)的各個(gè)未被訪問過的鄰接頂點(diǎn) w1, w2, , wt, 然后再順序訪問然后再順序訪問 w1, w2, , wt 的所的所有還未被訪問過的鄰接頂點(diǎn)。再從這些訪問有還未被訪問過的鄰接頂點(diǎn)。再從這些訪問過的頂點(diǎn)出發(fā)，再訪問它們的所有還未被訪過的頂點(diǎn)出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點(diǎn)，問過的鄰接頂點(diǎn)， 如此做

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

46、重復(fù)訪問為避免重復(fù)訪問, 需要一個(gè)輔助數(shù)組需要一個(gè)輔助數(shù)組 visited ，給被訪問過的頂點(diǎn)加標(biāo)記。給被訪問過的頂點(diǎn)加標(biāo)記。template void BFS (Graph& G, const T& v) int i, w, n = G.NumberOfVertices(); /圖中頂點(diǎn)個(gè)數(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);/取頂點(diǎn)號 cout G

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

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

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

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

51、以深度優(yōu)先搜索方法從頂點(diǎn) 出發(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+) /遍歷所有頂點(diǎn) if (!vi

52、sitedi) /頂點(diǎn) i 未訪問過 if (F.IsEmpty() /F原為空生成森林,建根 subT = rt = F.BuildRoot(G.GetValue(i); /頂點(diǎn) i 的值成為根 rt 的值 精選ppt146-146-6060 else (subT, G.GetValue(i); /頂點(diǎn) i 的值成為 subT 右兄弟的值 DFS_Tree (G, F, subT, i, visited); /從頂點(diǎn) 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; /頂點(diǎn) 作訪問過標(biāo)志 int w = G.GetFirstNeighbor (v); /取頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn) int FirstChild = 1; /第一個(gè)未訪問子女應(yīng)是 的左子女 while ( w != -1 ) /鄰接頂點(diǎn) 存在 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 為根的子樹 /鄰接頂點(diǎn) w 處理完 w = G.GetNextNeighbor (v, w); /取 v 的下一個(gè)鄰接頂點(diǎn) w /回到 while 判鄰接頂點(diǎn) w 存在; 精選ppt146-146-6363重連通分量重連通分量 (Biconnected Component)(Biconnected Component)n在無向連通圖在無向連通圖G中中, 當(dāng)且僅當(dāng)刪去當(dāng)且僅當(dāng)刪去G中的頂點(diǎn)中的

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

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

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

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

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

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