高級(jí)數(shù)據(jù)結(jié)構(gòu)2

1、JYP，1，雙連接組件(6.4.2)，雙連接組件對(duì)連接性的要求比一般的連接組件更高，生成雙連接組件的操作更復(fù)雜。假設(shè)無(wú)向圖G是連通的，雙連通分量的形式定義如下。定義：G的頂點(diǎn)V是一個(gè)連接點(diǎn)。當(dāng)且僅當(dāng)從G中刪除V及其相關(guān)邊時(shí)，剩余圖至少有兩個(gè)連通分量。例如，JYP，2，在下面的連通圖G6中，頂點(diǎn)1、4和7是連接點(diǎn)。定義：雙連通圖是沒(méi)有連接點(diǎn)的連通圖。例如，圖G5是雙連接的：JYP，4，但是圖G6不是雙連接的。在通信網(wǎng)絡(luò)圖中，邊代表通信鏈路，頂點(diǎn)代表通信站，關(guān)節(jié)明顯是弱鏈路。定義：連通圖G的雙連通分量是圖G的最大雙連通子圖，JYP，5，圖G6包含四個(gè)雙連通分量，如下所示：JYP，6，不難發(fā)現(xiàn)同一圖

2、的兩個(gè)雙連通分量最多有一個(gè)公共頂點(diǎn)?？梢酝茢?，一條邊不能出現(xiàn)在兩個(gè)或更多的雙連通分量中。因此，圖G的二部分被分成E(G)。圖G的雙連通分量可以通過(guò)圖G的任何深度最優(yōu)教師樹(shù)形成來(lái)獲得，JYP，7，以及圖G6，其根是頂點(diǎn)0，如下所示：JYP，8，其中非樹(shù)邊緣由虛線表示。頂點(diǎn)旁邊的數(shù)字稱為頂點(diǎn)的深度優(yōu)先數(shù)，簡(jiǎn)稱為dfn。頂點(diǎn)的dfn表示在深度優(yōu)先搜索中訪問(wèn)頂點(diǎn)的順序。例如，在前一個(gè)G6生成樹(shù)中，dfn(0)=1，dfn(1)=2，dfn(7)=5。請(qǐng)注意，在深層最佳教師樹(shù)中，如果頂點(diǎn)u是v的祖先，則dfn(u) dfn(v)。JYP，9，與生成樹(shù)t相比，當(dāng)且僅當(dāng)u是v的祖先或v是u的祖先時(shí)，非樹(shù)邊(

3、u，v)是后邊。例如，(4，1)和(6，7)是后邊緣。不是后邊緣的非樹(shù)邊緣稱為水平邊緣。根據(jù)深度優(yōu)先搜索定律，與任何圖形的任何深度相比，圖形不可能有水平邊。因此，10歲的JYP，如果至少有兩個(gè)孩子，那么作為一名優(yōu)秀教師的根就有必要也有足夠的理由成為一個(gè)連接點(diǎn)。任何其他頂點(diǎn)u成為連接點(diǎn)的充要條件是u至少有一個(gè)子w，這使得通過(guò)僅由w、w的后代和返回邊組成的路徑到達(dá)u的祖先是不可能的，因?yàn)閯h除頂點(diǎn)u及其相關(guān)的邊將使w及其后代與u的祖先斷開(kāi)連接。JYP，11，假設(shè)頂點(diǎn)w的祖先包括w本身。為了表示一個(gè)頂點(diǎn)可以通過(guò)它的后代和一個(gè)后邊緣到達(dá)的最高祖先，對(duì)于圖G的每個(gè)頂點(diǎn)W，low(w)被定義為可以通過(guò)它的后

4、代和一個(gè)后邊緣從W到達(dá)的最高祖先的dfn。很明顯，low(w)是從w通過(guò)其子代和后沿可以到達(dá)的dfn中最低的，并且可以通過(guò)以下公式計(jì)算：low(w)=min dfn(w)，min low(x)| x是w的子代，min dfn(x)| (w，x)是后沿，JYP，12以下是在G6的以頂點(diǎn)0為根的深度最優(yōu)樹(shù)中每個(gè)頂點(diǎn)的dfn和低值：JYP，13。通過(guò)修改DFS，可以獲得用于計(jì)算連通圖的每個(gè)頂點(diǎn)的dfn和低值的函數(shù)dfnlow:虛圖：3360 dfnlow(常數(shù)int x)/DFS num=1在頂點(diǎn)x的開(kāi)始處；/num是類型為int的圖形的數(shù)據(jù)成員dfn=新int n；低=新國(guó)際號(hào)碼；/dfn和low

5、都是Graph的數(shù)據(jù)成員，其/類型為int * for(int I=0；I n；I)dfni=lowi=0；DfnLow (x，-1)；/x是根，其父是偽頂點(diǎn)-1刪除dfn刪除low，jyp，14，void graph :dfnlow (int u，int v)/搜索深度首先從u和/計(jì)算dfn和low。v是u dfnu=lowu=num的父級(jí)；對(duì)于(與u相鄰的每個(gè)頂點(diǎn)w)/如果(dfnw=0) /w是未訪問(wèn)的頂點(diǎn)DfnLow (w，u)，則特定代碼與圖的表示有關(guān)；lowu=min2 (lowu，loww)；/min2(x，y)返回x和y/else if (w！=v) lowu=min2 (lo

6、wu，dfnw)；/回到邊緣。注/這意味著(v，u)不是后沿，JYP，15歲。請(qǐng)注意，如果v是u的父代，則(u，v)不能是后沿。函數(shù)DfnLow(u，v)的參數(shù)v旨在區(qū)分這種情況。深度優(yōu)先搜索的第一個(gè)頂點(diǎn)x沒(méi)有父頂點(diǎn)，因此它的調(diào)用形式是DfnLow(x，1)。函數(shù)DfnLow(u，v)使用的另一個(gè)函數(shù)min2返回兩個(gè)參數(shù)中較小的一個(gè)。JYP，16，在DfnLow的基礎(chǔ)上進(jìn)一步處理后，連通圖的邊可以分成雙連通分量。請(qǐng)注意，當(dāng)DfnLow(w，u)返回時(shí)，loww已被計(jì)算。如果為lowwdfnu，則可以確定新的雙連接組件。雙連通分量的所有邊都可以通過(guò)在堆棧中存儲(chǔ)第一個(gè)遇到的邊來(lái)獲得。JYP，17，

7、讓深度優(yōu)先搜索中最近訪問(wèn)的頂點(diǎn)是u，并且頂點(diǎn)w與u相鄰，但不是u的直接父代，那么在以下兩種情況下，(u，w)是第一個(gè)遇到的邊：(1)w是未訪問(wèn)的頂點(diǎn)(2)w是已經(jīng)訪問(wèn)的頂點(diǎn)和u的祖先，因?yàn)槲丛L問(wèn)的頂點(diǎn)的dfn值初始化為0，所以祖先的dfn值小于后代的dfn值。JYP，18，注意：如果dfnw為dfnu，則邊(w，u)必須作為后邊(當(dāng)在w點(diǎn)時(shí))添加到堆棧中，如下所示：u，x，w，2，3，4，JYP，19，雙連接函數(shù)實(shí)現(xiàn)上述過(guò)程：void dfn=new intn低=新國(guó)際號(hào)碼；對(duì)于(int I=0；一. 1 .dfnu=lowu=num，JYP，20，對(duì)于(與u相鄰的每個(gè)頂點(diǎn)w)/具體的代碼與圖

8、if (v！=w /后沿/表示結(jié)束，JYP，21，雙連接時(shí)間復(fù)雜度為0(n e)。請(qǐng)注意，雙連通函數(shù)假設(shè)輸入連通圖至少有兩個(gè)頂點(diǎn)。只有一個(gè)頂點(diǎn)的連通圖是無(wú)限的，但根據(jù)定義，它們也是雙連通的。這可以特別處理。JYP，22歲，求解最小生成樹(shù)的Prim算法(6.5.2)，假設(shè)TV是所選頂點(diǎn)的集合，t是最小生成樹(shù)的所選邊的集合。Prim算法首先在圖G中選擇一個(gè)頂點(diǎn)U，并將U添加到TV中。然后將成本最低的邊(u，v)加到T上，這樣T (u，v)仍然是一棵樹(shù)。重復(fù)上述步驟，直到t包含n 1條邊。請(qǐng)注意，與(u，v)相關(guān)的兩個(gè)頂點(diǎn)必須一個(gè)在電視中，另一個(gè)不在電視中。JYP，23歲，普里姆算法的幀：電視=0；

9、/從頂點(diǎn)0開(kāi)始，假設(shè)g至少有一個(gè)頂點(diǎn)(T=；t包含少于n -1條邊；把(u，v)加到(t)上，使(u，v)成為一條滿足電視需求的、電視成本最低的邊；如果(沒(méi)有這樣的邊緣)斷裂；給電視添加視頻；如果(T包含少于n-1條邊)結(jié)束“沒(méi)有最小生成樹(shù)”；JYP，24歲，下圖中用Prim算法構(gòu)造最小生成樹(shù)的過(guò)程：JYP，25歲，JYP，26歲，JYP，27歲，JYP，28歲，讓它成為不屬于TV的頂點(diǎn)集。對(duì)于任何v，將nearv定義為電視中最小化成本的頂點(diǎn)(nearv，v)(如果(v，w)E，讓成本(v，w)=)，然后成本(nearv，v)=。下一臺(tái)電視的頂點(diǎn)v應(yīng)該滿足：v和成本(近v，v)=。下一個(gè)增加t

10、的邊自然是(nearv，v)。JYP，29，設(shè)w為v in的頂點(diǎn)。頂點(diǎn)v加入電視后，如果成本(nearw，w)成本(v，w)，則nearw變?yōu)関。如果圖G由鄰接矩陣costij表示，算法的時(shí)間復(fù)雜度為0(N2)，因?yàn)樗惴偣策x擇了n 1個(gè)頂點(diǎn)，并且只需要0(n)個(gè)時(shí)間來(lái)選擇每個(gè)頂點(diǎn)V并處理V對(duì)Nearw(其中W和V是相鄰的)的影響。JYP，30，如果圖g由鄰接表表示并且使用斐波那契堆，算法的性能會(huì)更好。對(duì)于v，distv=cost(nearv，v)被定義為從頂點(diǎn)v到構(gòu)造的部分最小生成樹(shù)的最近距離。每次將頂點(diǎn)添加到電視時(shí)，算法需要確定頂點(diǎn)v，以便v和distv=。這對(duì)應(yīng)于上的刪除最小元素操作。當(dāng)

11、v被添加到電視時(shí)，與v in相鄰的頂點(diǎn)的距離值可能會(huì)減小。這對(duì)應(yīng)于上的關(guān)鍵字縮減操作。JYP，31歲，關(guān)鍵字縮減操作的總數(shù)最多是圖形中的邊數(shù)。刪除最小元素的操作總數(shù)是n 1。最初，有n 1個(gè)頂點(diǎn)。如果dist被用作關(guān)鍵字，并且組織是Fibonacci堆，則需要n 1個(gè)插入操作來(lái)初始化Fibonacci堆。然后，需要執(zhí)行n 1次刪除最小元素和最多E次關(guān)鍵詞縮減。所有這些操作的成本是每個(gè)操作的分?jǐn)偝杀镜目偤?，即O(n log n e)。因此，該算法的時(shí)間復(fù)雜度變成了0。當(dāng)e比n2小得多時(shí)，這顯然是一種改進(jìn)。斐波那契堆在最短路徑算法中的應(yīng)用，首先回憶經(jīng)典的最短路徑算法：1空?qǐng)D：3360最短路徑(常數(shù)

12、int n，常數(shù)int v) 2為(int I=0；I n；i ) 3 si=假；disti=lengthvi4 if (i！=v，JYP，33，10表示(int w=0；w n；w ) 11 if(！SW)12 if(distu length uw distw)distw=distu length uw；path w=u；13/(I=0；)結(jié)束14，jyp，34，分析：第2行中的for循環(huán)需要0(n)時(shí)間。第7行中的for循環(huán)執(zhí)行n次，每次選擇第8行并更新第10至12行中的dist值需要0(n)個(gè)時(shí)間。因此，該循環(huán)的總時(shí)間為0(N2)。整個(gè)算法的時(shí)間為0(N2)。即使使用鄰接表，行10到12

13、的總時(shí)間也可以減少到0(e)(因?yàn)橹挥信cU的頂點(diǎn)相鄰的距離可以改變)，并且行8的總時(shí)間仍然是0(N2)。JYP，35，算法的時(shí)間復(fù)雜度可以通過(guò)使用斐波那契堆和鄰接表降低到0(n log n e)。每次迭代，我們需要確定頂點(diǎn)u，以便u和distu=。這對(duì)應(yīng)于上的刪除最小元素操作。隨著u被加到s上，與u相鄰的頂點(diǎn)的距離值可能會(huì)減小。這對(duì)應(yīng)于上的關(guān)鍵字縮減操作。36歲的JYP最初包含n 1個(gè)頂點(diǎn)。如果dist被用作關(guān)鍵字，并且組織是Fibonacci堆，則需要n 1個(gè)插入操作。然后，需要執(zhí)行n 2次刪除最小元素和最多E次關(guān)鍵詞縮減。所有這些操作的成本是每個(gè)操作的分?jǐn)偝杀镜目偤?，即O(n log n

14、e)。因此，該算法的時(shí)間復(fù)雜度為0。當(dāng)e比n2小得多時(shí)，這種實(shí)現(xiàn)顯然更好。調(diào)查問(wèn)題：P223 23(每個(gè)學(xué)生獨(dú)立完成并提交一份報(bào)告作為本課程的主要成績(jī)因素)，JYP，37，基于鏈表和映射表的排序結(jié)果排序(7.8)。對(duì)于基于鏈表的結(jié)果排序，有時(shí)需要在本地重新排列它們，以使它們?cè)谖锢砩鲜沁B續(xù)的。讓我們假設(shè)記錄表r0，rn-1的排序結(jié)果是一個(gè)按照關(guān)鍵字的非遞減順序鏈接的鏈表，并且首先是鏈表的第一個(gè)記錄指針。R0和Rfirst的交換將被記錄。如果第一個(gè)值為0，則表中應(yīng)該有一個(gè)鏈接字段值為0的記錄Rx。如果Rx的鏈接字段可以被修改為指向最初位于R0中的記錄的第一個(gè)新位置，那么剩余的記錄R1、RN-1也以

15、關(guān)鍵字的非遞減順序被鏈接。JYP，38歲，但是在單鏈表中，我們不能快速確定節(jié)點(diǎn)R0的前身Rx。因此，R0的鏈接字段可以設(shè)置為first，表示原來(lái)位于R0的記錄已經(jīng)移動(dòng)到Rfirst。這樣，R0也充當(dāng)了R1的虛擬節(jié)點(diǎn)，rn-1鏈表。有了這個(gè)虛擬節(jié)點(diǎn)，我們可以找到剩余記錄鏈表的第一個(gè)節(jié)點(diǎn)。重復(fù)上述過(guò)程n1次以完成重排。通常，假設(shè)記錄表r0、Ri-1已經(jīng)以物理順序排列，并且Rfirst是剩余記錄Ri、rn-1的鏈表中的第一個(gè)記錄。在記錄ri和Rfirst被交換后，新的ri記錄的鏈接字段被設(shè)置為first，表示最初位于Ri的記錄已經(jīng)移動(dòng)到Rfirst。39歲的JYP。同時(shí)，注意，第一，即剩余記錄的鏈表的第一記錄索引ri，rn-1，總是大于或等于I。我們可以通過(guò)虛擬節(jié)點(diǎn)找到剩余記錄的鏈表的第一記錄索引。函數(shù)列表實(shí)現(xiàn)上述方法：模板空列表(element * list，const int n，int first)/對(duì)鏈表中由first指向的記錄進(jìn)行重新排序，使list0，list n-1/中的關(guān)鍵字按(int I=0；I n1；/找到應(yīng)該放在位置I的記錄.由于位置0、1和1-1處的記錄已經(jīng)/就位，記錄索引必須為1，同時(shí)(第一個(gè)1)第一個(gè)=列表第一。鏈接；/通過(guò)虛擬節(jié)點(diǎn)，JY