




版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、精選ppt146-146-1 1n圖的基本概念圖的基本概念n圖的存儲(chǔ)表示圖的存儲(chǔ)表示n圖的遍歷與連通性圖的遍歷與連通性 n最小生成樹(shù)最小生成樹(shù)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ù)對(duì)象某個(gè)數(shù)據(jù)對(duì)象 是頂點(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有向圖與無(wú)向圖有向圖與無(wú)向圖 在有向圖中,頂點(diǎn)對(duì)在有向圖中,頂點(diǎn)對(duì) 是有序的。在無(wú)向圖中,頂點(diǎn)對(duì)是有序的。在無(wú)向圖中,頂點(diǎn)對(duì)(x, y)是無(wú)序是無(wú)序的。的。n完全圖完全圖 若有若有 n 個(gè)頂點(diǎn)的無(wú)向圖有個(gè)頂點(diǎn)的無(wú)向圖有 n(n-1)/2 條條邊邊, 則此圖為完全無(wú)向圖。有則此圖為完全無(wú)向圖。有 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) 中的一條邊,中的一條邊,則稱(chēng)則稱(chēng) u 與與 v 互為鄰接頂點(diǎn)互為鄰接頂點(diǎn)。n子圖子圖 設(shè)有兩個(gè)圖設(shè)有兩個(gè)圖G(V, E) 和和G(V, E)。若若V V 且且E E, 則稱(chēng)圖則稱(chēng)圖G是圖是圖G的子圖。的子圖。n權(quán)權(quán) 某些圖的邊具有與它相關(guān)的數(shù)某些圖的邊具有與它相關(guān)的數(shù), 稱(chēng)之為權(quán)。稱(chēng)之為權(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)過(guò)一些頂點(diǎn)一些邊經(jīng)過(guò)一些頂點(diǎn) vp1, vp2, , vpm,到達(dá)頂,到達(dá)頂點(diǎn)點(diǎn)vj
5、。則稱(chēng)頂點(diǎn)序列。則稱(chēng)頂點(diǎn)序列 (vi vp1 vp2 . vpm vj) 為從頂為從頂點(diǎn)點(diǎn)vi 到頂點(diǎn)到頂點(diǎn) vj 的路徑。它經(jīng)過(guò)的邊的路徑。它經(jīng)過(guò)的邊(vi, vp1)、(vp1, vp2)、.、(vpm, vj) 應(yīng)是屬于應(yīng)是屬于E的邊。的邊。精選ppt146-146-6 6n路徑長(zhǎng)度路徑長(zhǎng)度 非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的條數(shù)。帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。邊的權(quán)之和。n簡(jiǎn)單路徑簡(jiǎn)單路徑 若路徑上各頂點(diǎn)若路徑上各頂點(diǎn) v1, v2, ., vm 均不均不 互相重復(fù)互相重復(fù), 則稱(chēng)這樣的路徑為簡(jiǎn)單路徑。則稱(chēng)這
6、樣的路徑為簡(jiǎn)單路徑。n回路回路 若路徑上第一個(gè)頂點(diǎn)若路徑上第一個(gè)頂點(diǎn) v1 與最后一個(gè)頂與最后一個(gè)頂點(diǎn)點(diǎn)vm 重合重合, 則稱(chēng)這樣的路徑為回路或環(huán)。則稱(chēng)這樣的路徑為回路或環(huán)。012301230123精選ppt146-146-7 7n連通圖與連通分量連通圖與連通分量 在在無(wú)向圖無(wú)向圖中中, 若從頂點(diǎn)若從頂點(diǎn)v1到頂點(diǎn)到頂點(diǎn)v2有路徑有路徑, 則稱(chēng)頂點(diǎn)則稱(chēng)頂點(diǎn)v1與與v2是連通的。是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的如果圖中任意一對(duì)頂點(diǎn)都是連通的, 則稱(chēng)此圖則稱(chēng)此圖是連通圖。非連通圖的極大連通子圖叫做連是連通圖。非連通圖的極大連通子圖叫做連通分量。通分量。n強(qiáng)連通圖與強(qiáng)連通分量強(qiáng)連通圖與強(qiáng)連通
7、分量 在在有向圖有向圖中中, 若對(duì)于若對(duì)于每一對(duì)頂點(diǎn)每一對(duì)頂點(diǎn)vi和和vj, 都存在一條從都存在一條從vi到到vj和從和從vj到到vi的路徑的路徑, 則稱(chēng)此圖是強(qiáng)連通圖。非強(qiáng)連通圖則稱(chēng)此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。n生成樹(shù)生成樹(shù) 一個(gè)連通圖的生成樹(shù)是其極小連通一個(gè)連通圖的生成樹(shù)是其極小連通子圖,在子圖,在 n 個(gè)頂點(diǎn)的情形下,有個(gè)頂點(diǎn)的情形下,有 n-1 條邊。條邊。精選ppt146-146-8 8圖的抽象數(shù)據(jù)類(lèi)型圖的抽象數(shù)據(jù)類(lèi)型class Graph /對(duì)象: 由一個(gè)頂點(diǎn)的非空集合和一個(gè)邊集合構(gòu)成/每條邊由一個(gè)頂點(diǎn)對(duì)來(lái)表示。publ
8、ic: Graph();/建立一個(gè)空的圖 void insertVertex (const T& vertex); /插入一個(gè)頂點(diǎn)vertex, 該頂點(diǎn)暫時(shí)沒(méi)有入邊 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(); /若圖中沒(méi)有頂點(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圖的存儲(chǔ)表示圖的存儲(chǔ)表示n圖的模板基類(lèi)圖的模板基類(lèi) 在模板類(lèi)定義中的數(shù)據(jù)類(lèi)型在模板類(lèi)定義中的數(shù)據(jù)類(lèi)型參數(shù)表參數(shù)表 中,中,T是頂點(diǎn)數(shù)據(jù)的是頂點(diǎn)數(shù)據(jù)的類(lèi)型,類(lèi)型,E是邊上所附數(shù)據(jù)的類(lèi)型。是邊上所附數(shù)據(jù)的類(lèi)型。n這個(gè)模板基類(lèi)是按
10、照最復(fù)雜的情況(即帶權(quán)這個(gè)模板基類(lèi)是按照最復(fù)雜的情況(即帶權(quán)無(wú)向圖)來(lái)定義的,如果需要使用非帶權(quán)圖,無(wú)向圖)來(lái)定義的,如果需要使用非帶權(quán)圖,可將數(shù)據(jù)類(lèi)型參數(shù)表可將數(shù)據(jù)類(lèi)型參數(shù)表 改為改為 。n如果使用的是有向圖,也可以對(duì)程序做相應(yīng)如果使用的是有向圖,也可以對(duì)程序做相應(yīng)的改動(dòng)。的改動(dòng)。 精選ppt146-146-11 11圖的模板基類(lèi)圖的模板基類(lèi) const int maxWeight = ; /無(wú)窮大的值(= )const int DefaultVertices = 30; /最大頂點(diǎn)數(shù)(=n)template class Graph /圖的類(lèi)定義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無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的;n有向圖的鄰接矩陣可能是不對(duì)稱(chēng)的。有向圖的鄰接矩陣可能是不對(duì)稱(chēng)的。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在無(wú)向圖中在無(wú)向圖中, 統(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用鄰接矩陣表示的圖的類(lèi)定義用鄰接矩陣表示的圖的類(lèi)定義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。對(duì)于帶權(quán)圖,邊結(jié)點(diǎn)中還要保。對(duì)于帶權(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ù),以及它對(duì)應(yīng)邊鏈表的頭指針以及它對(duì)應(yīng)邊鏈表的頭指針adj。 鄰接表鄰接表 (Adjacency List)(Adjacency List)精選ppt146-146-2525ABCDdata adjABCD0123dest linkdest link 130210無(wú)向圖的鄰接表無(wú)向圖的鄰接表n統(tǒng)計(jì)某頂點(diǎn)對(duì)應(yīng)邊鏈表中結(jié)點(diǎn)個(gè)數(shù),可得該頂統(tǒng)計(jì)某頂點(diǎn)對(duì)應(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)對(duì)應(yīng)的邊鏈表中。個(gè)頂點(diǎn)對(duì)應(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 條邊,則用鄰接表表示條邊,則用鄰接表表示無(wú)向圖時(shí),需要無(wú)向圖時(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é)省大量的存儲(chǔ)空時(shí),可以節(jié)省大量的存儲(chǔ)空間。此外,把同一個(gè)頂點(diǎn)的所有邊鏈接在一個(gè)間。此外,把同一個(gè)頂點(diǎn)的所有邊鏈接在一個(gè)單鏈表中,也使得圖的操作更為便捷。單鏈表中,也使得圖的操作更為便捷。 精選ppt146-146-2929用鄰接表表示的圖的類(lèi)定義用鄰接表表示的圖的類(lèi)定義 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 /圖的類(lèi)定義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 存儲(chǔ)分配錯(cuò)!存儲(chǔ)分配錯(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;/對(duì)應(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)的位置,/若沒(méi)有下一個(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無(wú)向圖的情形無(wú)向圖的情形u邊結(jié)點(diǎn)的結(jié)構(gòu)邊結(jié)點(diǎn)的結(jié)構(gòu)n其中其中, mark 是記錄是否處理過(guò)的標(biāo)記是記錄是否處理過(guò)的標(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é)合起來(lái)表示??砂褍蓚€(gè)表結(jié)合起來(lái)表示。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畫(huà)出在下圖所表示的有向圖中刪畫(huà)出在下圖所表示的有向圖中刪除頂點(diǎn)除頂點(diǎn)V3V3后的十字鏈表存儲(chǔ)結(jié)構(gòu)圖后的十字鏈表存儲(chǔ)結(jié)構(gòu)圖。精選ppt146-146-4444圖的遍歷與連通性圖的遍歷與連通性n從已給的連通圖中某一頂點(diǎn)出發(fā),沿著一些邊從已給的連通圖中某一頂點(diǎn)出發(fā),沿著一些邊訪(fǎng)遍圖中所有的頂點(diǎn),且使每個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)訪(fǎng)遍圖中所有的頂點(diǎn),且使每
38、個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次,就叫做圖的遍歷一次,就叫做圖的遍歷 (Graph Traversal)。n圖中可能存在回路,且圖的任一頂點(diǎn)都可能與圖中可能存在回路,且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通,在訪(fǎng)問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)其它頂點(diǎn)相通,在訪(fǎng)問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪(fǎng)問(wèn)過(guò)的頂點(diǎn)。沿著某些邊又回到了曾經(jīng)訪(fǎng)問(wèn)過(guò)的頂點(diǎn)。n為了避免重復(fù)訪(fǎng)問(wèn),可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否為了避免重復(fù)訪(fǎng)問(wèn),可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪(fǎng)問(wèn)過(guò)的輔助數(shù)組被訪(fǎng)問(wèn)過(guò)的輔助數(shù)組 visited 。精選ppt146-146-4545n輔助數(shù)組輔助數(shù)組visited 的初始狀態(tài)為的初始狀態(tài)為 0, 在圖的遍在圖的遍歷過(guò)程中歷過(guò)程中,
39、一旦某一個(gè)頂點(diǎn)一旦某一個(gè)頂點(diǎn) i 被訪(fǎng)問(wèn)被訪(fǎng)問(wèn), 就立即就立即讓讓visitedi為為 1, 防止它被多次訪(fǎng)問(wèn)。防止它被多次訪(fǎng)問(wèn)。n圖的遍歷的分類(lèi)圖的遍歷的分類(lèi):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、過(guò)程深度優(yōu)先搜索過(guò)程 深度優(yōu)先生成樹(shù)深度優(yōu)先生成樹(shù)精選ppt146-146-4747nDFS 在訪(fǎng)問(wèn)圖中某一在訪(fǎng)問(wèn)圖中某一起始頂點(diǎn)起始頂點(diǎn) v 后后, 由由 v 出發(fā)出發(fā), 訪(fǎng)問(wèn)它的任一訪(fǎng)問(wèn)它的任一鄰接頂點(diǎn)鄰接頂點(diǎn) w1; 再?gòu)脑購(gòu)?w1 出發(fā)出發(fā), 訪(fǎng)問(wèn)訪(fǎng)問(wèn)與與 w1鄰鄰 接接但還但還沒(méi)有訪(fǎng)問(wèn)過(guò)的頂點(diǎn)沒(méi)有訪(fǎng)問(wèn)過(guò)的頂點(diǎn) w2; 然后再然后再?gòu)膹?w2 出發(fā)出發(fā), 進(jìn)行類(lèi)似的訪(fǎng)問(wèn)進(jìn)行類(lèi)似的訪(fǎng)問(wèn), 如此進(jìn)行下去如此進(jìn)行下去, 直至到達(dá)所有的鄰接頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)直至到達(dá)所有的鄰接頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)的頂點(diǎn) u 為止。為止。接著接著, 退回一步退回一步, 退到前一次剛訪(fǎng)問(wèn)過(guò)退到前一次剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn)的頂點(diǎn)
41、, 看是否還有其它沒(méi)有被訪(fǎng)問(wèn)的鄰接頂看是否還有其它沒(méi)有被訪(fǎng)問(wèn)的鄰接頂點(diǎn)。點(diǎn)。如果有如果有, 則訪(fǎng)問(wèn)此頂點(diǎn)則訪(fǎng)問(wèn)此頂點(diǎn), 之后再?gòu)拇隧旤c(diǎn)出之后再?gòu)拇隧旤c(diǎn)出發(fā)發(fā), 進(jìn)行與前述類(lèi)似的訪(fǎng)問(wèn)進(jìn)行與前述類(lèi)似的訪(fǎng)問(wèn); 如果沒(méi)有如果沒(méi)有, 就再退就再退回一步進(jìn)行搜索。重復(fù)上述過(guò)程回一步進(jìn)行搜索。重復(fù)上述過(guò)程, 直到連通圖直到連通圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)為止。中所有頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)為止。精選ppt146-146-4848圖的深度優(yōu)先搜索算法圖的深度優(yōu)先搜索算法template void DFS (Graph& G, const T& v) /從頂點(diǎn)v出發(fā)對(duì)圖G進(jìn)行深度優(yōu)先遍歷的主過(guò)程 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開(kāi)始深度優(yōu)先搜索 delete visited; /釋放visited精選ppt146-146-4949templatevoid DFS (Graph& G, int v, bool visited) cout G.getValue
43、(v) ; /訪(fǎng)問(wèn)頂點(diǎn)v visitedv = true; /作訪(fǎng)問(wèn)標(biāo)記 int w = G.getFirstNeighbor (v); /第一個(gè)鄰接頂點(diǎn) while (w != -1) /若鄰接頂點(diǎn)w存在 if ( !visitedw ) DFS(G, w, visited); /若w未訪(fǎng)問(wèn)過(guò), 遞歸訪(fǎng)問(wèn)頂點(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、搜索過(guò)程廣度優(yōu)先搜索過(guò)程 廣度優(yōu)先生成樹(shù)廣度優(yōu)先生成樹(shù)ACDEGBFIHACDEGBFH123456789123456789I精選ppt146-146-5151nBFS在訪(fǎng)問(wèn)了起始頂點(diǎn)在訪(fǎng)問(wèn)了起始頂點(diǎn) v 之后之后, 由由 v 出發(fā)出發(fā), 依次依次訪(fǎng)問(wèn)訪(fǎng)問(wèn) v 的各個(gè)未被訪(fǎng)問(wèn)過(guò)的鄰接頂點(diǎn)的各個(gè)未被訪(fǎng)問(wèn)過(guò)的鄰接頂點(diǎn) w1, w2, , wt, 然后再順序訪(fǎng)問(wèn)然后再順序訪(fǎng)問(wèn) w1, w2, , wt 的所的所有還未被訪(fǎng)問(wèn)過(guò)的鄰接頂點(diǎn)。再?gòu)倪@些訪(fǎng)問(wèn)有還未被訪(fǎng)問(wèn)過(guò)的鄰接頂點(diǎn)。再?gòu)倪@些訪(fǎng)問(wèn)過(guò)的頂點(diǎn)出發(fā),再訪(fǎng)問(wèn)它們的所有還未被訪(fǎng)過(guò)的頂點(diǎn)出發(fā),再訪(fǎng)問(wèn)它們的所有還未被訪(fǎng)問(wèn)過(guò)的鄰接頂點(diǎn),問(wèn)過(guò)的鄰接頂點(diǎn), 如此做
45、下去,直到圖中如此做下去,直到圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。n廣度優(yōu)先搜索是一種分層的搜索過(guò)程廣度優(yōu)先搜索是一種分層的搜索過(guò)程, 每向前每向前走一步可能訪(fǎng)問(wèn)一批頂點(diǎn)走一步可能訪(fǎng)問(wèn)一批頂點(diǎn), 不像深度優(yōu)先搜索不像深度優(yōu)先搜索那樣有往回退的情況。因此那樣有往回退的情況。因此, 廣度優(yōu)先搜索不廣度優(yōu)先搜索不是一個(gè)遞歸的過(guò)程。是一個(gè)遞歸的過(guò)程。精選ppt146-146-5252n為了實(shí)現(xiàn)逐層訪(fǎng)問(wèn)為了實(shí)現(xiàn)逐層訪(fǎng)問(wèn), 算法中使用了一個(gè)隊(duì)列算法中使用了一個(gè)隊(duì)列, 以以記憶正在訪(fǎng)問(wèn)的這一層和上一層的頂點(diǎn)記憶正在訪(fǎng)問(wèn)的這一層和上一層的頂點(diǎn), 以便以便于向下一層訪(fǎng)問(wèn)。于向下一層訪(fǎng)問(wèn)。n為避免
46、重復(fù)訪(fǎng)問(wèn)為避免重復(fù)訪(fǎng)問(wèn), 需要一個(gè)輔助數(shù)組需要一個(gè)輔助數(shù)組 visited ,給被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)加標(biāo)記。給被訪(fǎng)問(wèn)過(guò)的頂點(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)號(hào) cout G
47、.getValue (loc) ; /訪(fǎng)問(wèn)頂點(diǎn)v visitedloc = true; /做已訪(fǎng)問(wèn)標(biāo)記 Queue Q; Q.EnQueue (loc); /頂點(diǎn)進(jìn)隊(duì)列, 實(shí)現(xiàn)分層訪(fǎng)問(wèn) while (!Q.IsEmpty() ) /循環(huán), 訪(fǎng)問(wèn)所有結(jié)點(diǎn) Q.DeQueue (loc); w = G.getFirstNeighbor (loc); /第一個(gè)鄰接頂點(diǎn) while (w != -1) /若鄰接頂點(diǎn)w存在 if (!visitedw) /若未訪(fǎng)問(wèn)過(guò)精選ppt146-146-5454 cout G.getValue (w) ;/訪(fǎng)問(wèn) 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)無(wú)向圖為非連通圖時(shí),從圖中某一頂點(diǎn)出當(dāng)無(wú)向圖為非連通圖時(shí),從圖中某一頂點(diǎn)出發(fā),利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索發(fā),利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點(diǎn),只能訪(fǎng)算法不可能遍歷到圖中的所有頂點(diǎn),只能訪(fǎng)問(wèn)到該頂點(diǎn)所在最大連通子圖問(wèn)到該頂點(diǎn)所在最大連通子圖(連通
49、分量)(連通分量)的的所有頂點(diǎn)。所有頂點(diǎn)。n若從無(wú)向圖每一連通分量中的一個(gè)頂點(diǎn)出發(fā)若從無(wú)向圖每一連通分量中的一個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷進(jìn)行遍歷, 可求得無(wú)向圖的所有連通分量??汕蟮脽o(wú)向圖的所有連通分量。n例如,對(duì)于非連通的無(wú)向圖,所有連通分量例如,對(duì)于非連通的無(wú)向圖,所有連通分量的生成樹(shù)組成了非連通圖的生成森林。的生成樹(shù)組成了非連通圖的生成森林。精選ppt146-146-5656ACDEBFGOIHJNMLK非連通無(wú)向圖AHKCDEIBFOGJNML非連通圖的連通分量精選ppt146-146-5757確定連通分量的算法確定連通分量的算法template void Components (Graph&
50、amp; G) /通過(guò)DFS,找出無(wú)向圖的所有連通分量 int i, n = G.NumberOfVertices(); /圖中頂點(diǎn)個(gè)數(shù) bool *visited = new booln; /訪(fǎng)問(wèn)標(biāo)記數(shù)組 for (i = 0; i n; i+) visitedi = false; for (i = 0; i n; i+) /掃描所有頂點(diǎn) if (!visitedi) /若沒(méi)有訪(fǎng)問(wèn)過(guò) DFS (G, i, visited);/訪(fǎng)問(wèn) 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; /訪(fǎng)問(wèn)數(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 未訪(fǎng)問(wèn)過(guò) 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)先遍歷, 建子樹(shù) template void DFS_Tree (Graph& G, Tree&F, TreeNode * rt, int v,
53、int visited ) TreeNode * p;精選ppt146-146-6161 visitedv = 1; /頂點(diǎn) 作訪(fǎng)問(wèn)過(guò)標(biāo)志 int w = G.GetFirstNeighbor (v); /取頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn) int FirstChild = 1; /第一個(gè)未訪(fǎng)問(wèn)子女應(yīng)是 的左子女 while ( w != -1 ) /鄰接頂點(diǎn) 存在 if (! visited w) / 未訪(fǎng)問(wèn)過(guò), 將成為 的子女 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 為根的子樹(shù) /鄰接頂點(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在無(wú)向連通圖在無(wú)向連通圖G中中, 當(dāng)且僅當(dāng)刪去當(dāng)且僅當(dāng)刪去G中的頂點(diǎn)中的
55、頂點(diǎn)v及所有依附于及所有依附于v的所有邊后的所有邊后, 可將圖分割成兩個(gè)可將圖分割成兩個(gè)或兩個(gè)以上的連通分量,則稱(chēng)頂點(diǎn)或兩個(gè)以上的連通分量,則稱(chēng)頂點(diǎn)v為為關(guān)節(jié)點(diǎn)關(guān)節(jié)點(diǎn)。n沒(méi)有沒(méi)有關(guān)節(jié)點(diǎn)關(guān)節(jié)點(diǎn)的連通圖叫做重連通圖。的連通圖叫做重連通圖。n在重連通圖上在重連通圖上, 任何一對(duì)頂點(diǎn)之間至少存在有任何一對(duì)頂點(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è)無(wú)向連通圖在一個(gè)無(wú)向連通圖G中中, 重連通分量可以利用重連通分量可以利用深度優(yōu)先生成樹(shù)找到。深度優(yōu)先生成樹(shù)找到。n在圖中各在圖中各頂點(diǎn)旁標(biāo)明的深度優(yōu)先數(shù)頂點(diǎn)旁標(biāo)明的深度優(yōu)先數(shù), 給出進(jìn)行給出進(jìn)行深度優(yōu)先搜索時(shí)各頂點(diǎn)訪(fǎng)問(wèn)的次序。深度優(yōu)先搜索時(shí)各頂點(diǎn)訪(fǎng)問(wèn)的次序。n深度優(yōu)先生成樹(shù)的深度優(yōu)先生成樹(shù)的根是根是關(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ā), 不能通過(guò)不能通過(guò) w、w 的子孫及的子孫及一條回邊所組成的路徑到達(dá)一條回邊所組成的路徑到達(dá)
57、 u 的祖先的祖先。精選ppt146-146-6565ABCDEFGHIJABCDEFGHJABCDEFGHJII12345678910根有兩根有兩 個(gè)子女個(gè)子女精選ppt146-146-6666最小生成樹(shù)最小生成樹(shù) ( minimum cost spanning tree )( minimum cost spanning tree )n使用不同的遍歷圖的方法,可以得到不同的生使用不同的遍歷圖的方法,可以得到不同的生成樹(shù);從不同的頂點(diǎn)出發(fā),也可能得到不同的成樹(shù);從不同的頂點(diǎn)出發(fā),也可能得到不同的生成樹(shù)。生成樹(shù)。n按照生成樹(shù)的定義,按照生成樹(shù)的定義,n 個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)的生個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)的生成
58、樹(shù)有成樹(shù)有 n 個(gè)頂點(diǎn)、個(gè)頂點(diǎn)、n-1條邊。條邊。n構(gòu)造最小生成樹(shù)構(gòu)造最小生成樹(shù) 假設(shè)有一個(gè)網(wǎng)絡(luò),用以表示假設(shè)有一個(gè)網(wǎng)絡(luò),用以表示 n 個(gè)城市之間架設(shè)通信線(xiàn)路,邊上的權(quán)值代表個(gè)城市之間架設(shè)通信線(xiàn)路,邊上的權(quán)值代表架設(shè)通信線(xiàn)路的成本。如何架設(shè)才能使線(xiàn)路架架設(shè)通信線(xiàn)路的成本。如何架設(shè)才能使線(xiàn)路架設(shè)的成本達(dá)到最?。吭O(shè)的成本達(dá)到最???精選ppt146-146-6767n構(gòu)造最小生成樹(shù)的準(zhǔn)則構(gòu)造最小生成樹(shù)的準(zhǔn)則v必須使用且僅使用該網(wǎng)絡(luò)中的必須使用且僅使用該網(wǎng)絡(luò)中的 n-1 條邊條邊來(lái)聯(lián)結(jié)網(wǎng)絡(luò)中的來(lái)聯(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), 沒(méi)有邊的非連沒(méi)有邊的非連通圖通圖 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是最小生成樹(shù)的邊集合是最小生成樹(shù)的邊集合 /E是帶權(quán)無(wú)向圖的邊集合是帶權(quán)無(wú)向圖的邊集合while ( T 包含的邊少于包含的邊少于n-1
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 第九課自定義函數(shù)教學(xué)設(shè)計(jì)2023-2024學(xué)年青島版(2019)信息技術(shù)第三冊(cè)
- 2024年武漢江岸區(qū)某國(guó)有企業(yè)招聘投資團(tuán)隊(duì)成員5人筆試參考題庫(kù)附帶答案詳解
- 安徽省黃山地區(qū)2023-2024學(xué)年八年級(jí)下學(xué)期期末語(yǔ)文試題
- 第一單元第六課三、《AVERAGEIF函數(shù)》教學(xué)設(shè)計(jì) 2023-2024學(xué)年新世紀(jì)版(2018)初中信息技術(shù)七年級(jí)下冊(cè)
- 第六單元碳和碳的氧化物單元整體教學(xué)設(shè)計(jì)-2023-2024學(xué)年九年級(jí)化學(xué)人教版上冊(cè)
- 2025年貴州航空職業(yè)技術(shù)學(xué)院?jiǎn)握新殬I(yè)傾向性測(cè)試題庫(kù)必考題
- 配電線(xiàn)路工專(zhuān)業(yè)復(fù)習(xí)題含參考答案
- 護(hù)理藥理學(xué)題庫(kù)+參考答案
- 中醫(yī)兒科學(xué)模擬考試題含答案
- 10《老人與?!方虒W(xué)設(shè)計(jì) 2024-2025學(xué)年統(tǒng)編版高中語(yǔ)文選擇性必修上冊(cè)
- 《護(hù)患溝通》課件
- 2024-2025學(xué)年新教材高中化學(xué) 第三章 鐵 金屬材料 2.1 合金說(shuō)課稿 新人教版必修1
- 《籃球防守腳步移動(dòng)技術(shù) 滑步》教案
- 完整版項(xiàng)目部組織機(jī)構(gòu)圖
- 浙江省杭州市2023-2024學(xué)年七年級(jí)上學(xué)期期末考試數(shù)學(xué)試題(含答案)
- 人工智能客服機(jī)器人使用手冊(cè)
- 品牌全球化體育營(yíng)銷(xiāo)趨勢(shì)洞察報(bào)告 2024
- (新版)拖拉機(jī)駕駛證科目一知識(shí)考試題庫(kù)500題(含答案)
- (人衛(wèi)版第九版?zhèn)魅静W(xué)總論(一))課件
- 工業(yè)機(jī)器人仿真與離線(xiàn)編程項(xiàng)目-8-KUKA-Sim-Pro-軟件的介紹及基本操作
- 第2課++生涯規(guī)劃+筑夢(mèng)未來(lái)(課時(shí)2)【中職專(zhuān)用】中職思想政治《心理健康與職業(yè)生涯》高效課堂 (高教版基礎(chǔ)模塊)
評(píng)論
0/150
提交評(píng)論