生成樹(SpanningTree)無向連通圖G=(V,E)的生成樹是G的極小連通子圖，即包含G的|V|個(gè)頂點(diǎn)和|V|-1條邊的連通子圖。通過圖的遍歷算法，可以獲得生成樹。V1V2V3V4V5V8V6V7V1V2V4V8V5V3V6V7V1V2V3V4V5V8V6V7深度優(yōu)先：廣度優(yōu)先：生成樹生成森林非連通無向圖G的每個(gè)連通分量的生成樹，構(gòu)成了圖G的生成森林。通過對G的不同連通分量使用圖的遍歷算法可以獲取G的生成森林abchdekfg812345670812345670achdkfebgabchdekfg生成森林最小生成樹-引例假設(shè)要建立一個(gè)通訊網(wǎng)絡(luò)，使得n個(gè)城市之間可以通訊，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？選擇只修建n-1線路的方案選擇上述方案中使用經(jīng)費(fèi)最少的方案abcdegf195141827168213127帶權(quán)圖：n個(gè)城市和城市間可能鋪設(shè)的通訊線路頂點(diǎn)：表示城市邊：表示一條通訊線路權(quán)值：經(jīng)費(fèi)最小生成樹-引例帶權(quán)無向連通圖G=(V,E)的一棵生成樹在所有的生成樹中，邊的權(quán)值之和最小。最小生成樹最小生成樹算法：克魯斯卡爾算法、普里姆算法。二者都采用了貪心策略，分別使用檢測和預(yù)防的方法防止產(chǎn)生回路克魯斯卡爾(Kruskal)算法1、用|V|個(gè)集合表示|V|個(gè)不同的連通分量。初始時(shí)，每個(gè)頂點(diǎn)屬于一個(gè)連通分量2、??A,A是構(gòu)成最小生成樹邊的集合3、重復(fù)以下的操作直至A包含了n-1條邊：3.1、取下一條權(quán)值最小的邊<u,v>(貪心)3.2、若u、v屬于不同的集合，則A=A∪{<u,v>}，并且合并u、v所屬的集合否則，不做任何操作abcdegf3abcegfd<c,d,3><b,c,5><d,b,7><e,d,8><b,e,12><a,e,14><g,e,16><a,g,18><a,b,19><f,d,21><g,f,27>21581416克魯斯卡爾算法1234567444444克魯斯卡爾算法－課堂練習(xí)abcefd1018359567算法分析kruskal算法的時(shí)間復(fù)雜度與使用的數(shù)據(jù)結(jié)構(gòu)有關(guān)如果使用二叉堆和并查集，時(shí)間復(fù)雜度(最壞)：取邊(|E|次)，O(|E|log|E|)并查集的操作：最多2|E|次查找、最多|V|-1次合并操作，均攤為O(|E|+|V|)結(jié)論:O(|E|log|E|+|V|)Kruskal算法從具有n個(gè)連通分量的非連通圖開始，貪心的選擇權(quán)重最小的邊加入圖，用檢測邊的兩個(gè)端點(diǎn)是否屬于同一個(gè)連通分量，防止在圖中形成回路。隨著邊的不斷加入，得到了原圖的一棵最小生成樹。普里姆算法的核心是預(yù)防產(chǎn)生回路：將圖G=(V,E)的頂點(diǎn)劃分為不相交的兩部分U，V-U，初始時(shí)U={v0}通過一條邊，將V-U中滿足條件的一個(gè)頂點(diǎn)“拉”到U反復(fù)運(yùn)用上面的“拉”操作，U中的樹不斷長大，最終得到了原圖的一棵最小生成樹。普里姆(Prim)算法UV-U普里姆(Prim)算法UV-Uv8105一般地，V-U的某個(gè)頂點(diǎn)v可能通過多條邊連接U的多個(gè)頂點(diǎn)。對v而言，只需記住那條最短的邊(貪心)。下圖中，頂點(diǎn)v只記住權(quán)重為5的邊。數(shù)組d[]存放V-U中的頂點(diǎn)到U的最短邊的權(quán)重：d[v]=min{w(vk,v):vk∈U}普里姆(Prim)算法拉V-U的某個(gè)頂點(diǎn)到U時(shí)，選擇具有最短邊的頂點(diǎn)(貪心)，下圖中，頂點(diǎn)v將被“拉”到U。UV-Uv715518滿足條件的頂點(diǎn)v:d[v]=min{d[vi]:vi∈V-U}普里姆(Prim)算法UV-Uuv106新的頂點(diǎn)被“拉”入U(xiǎn)以后，V-U中的頂點(diǎn)到U的最短邊可能發(fā)生變化。下圖中，u加入U(xiǎn)后，頂點(diǎn)v連接到U的最短邊就需要變更為權(quán)重為6的邊。d[v]=min{d[v],w(u,v)}普里姆(Prim)算法d[]:進(jìn)入U(xiǎn)的最短邊的權(quán)重p[]：p[vj]=vi，如果vj通過與vi相鄰的邊進(jìn)入U(xiǎn)Q:存放頂點(diǎn)的最小優(yōu)先隊(duì)列，按照d[]比較大小1、初始化:d[v0]=0，d[vi]=∞;p[vi]=-1;U=?；Q=V2、whileQ≠?{3、從Q中取出頂點(diǎn)u，u的d[u]最小4、U=U∪{u}5、foru的鄰接點(diǎn)v，v?U6、ifw(u,v)<d[v]thend[v]=w(u,v)，p[v]=u}abcdegf195141827168213127abegf14d8c351621g<g,a,18>b<b,a,19>e<e,a,14><c,d,3>f<f,d,21>c普里姆算法d<d,e,8><b,e,12><g,e,16><b,d,7><b,c,5>普里姆算法－課堂練習(xí)abcefd1018359567參照Dijsktra算法畫出Prim算法的數(shù)組p[]和d[]的變化過程。算法分析使用二叉堆實(shí)現(xiàn)的時(shí)間復(fù)雜度找加入的結(jié)點(diǎn)及修改權(quán)重，log(|V|)，|V|-1次找鄰接點(diǎn)，總計(jì)|E|結(jié)論|V|log|V|+|E|Prim算法從只有一個(gè)頂點(diǎn)的樹開始，貪心的選擇權(quán)重最小的邊，向樹中“嫁接”邊和點(diǎn)，讓樹逐步長大，最終形成原圖的最小生成樹。Prim算法的時(shí)間復(fù)雜度與使用的數(shù)據(jù)結(jié)構(gòu)有關(guān)并查集只支持集合的合并操作和成員查找(判定)操作的集合。集合：{2,4,6,8}集合:{1,3,5,7,9}集合：{2,4,6,8,1,3,5,7,9}集合名：以某個(gè)元素作為集合名，例如:集合2:{2,4,6,8}2468并查集的查找查找某個(gè)元素屬于哪個(gè)結(jié)合。{2,4,6,8}2468并查集的合并-重量規(guī)則2468135791357992468結(jié)點(diǎn)數(shù)多的集合作為根ABC并查集的合并-高度規(guī)則DGHIJKDGHIJKABC層數(shù)多的集合作為根并查集的合并-查詢路徑折疊DGHIJKABCDHGIJKABC查找的過程也附帶著進(jìn)行合并。假設(shè)查找的結(jié)點(diǎn)是H，將H到根結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)都作為根的孩子結(jié)點(diǎn)。并查集的均攤時(shí)間復(fù)雜度Tarjan和VanLeeuwen定理：k1、k2:正常數(shù)f:查找次數(shù)u:合并次數(shù)n:集合元素個(gè)數(shù)??(p,q)是Ackermann函數(shù)的倒數(shù)T(f,u):時(shí)間復(fù)雜度k1(n