圖論 之 圖的基本算法課件

1、圖論 之 圖的基本算法王恩澤我們將要學(xué)的圖的表示圖的遍歷（DFS，BFS）拓?fù)渑判蜃疃搪窂剿惴ǎ―ijkstra，F(xiàn)loyd）最小生成樹算法（Prim）圖的表示要表示一個(gè)圖G=(V, E)，有兩種標(biāo)準(zhǔn)方法：鄰接表和鄰接矩陣鄰接表常用于表示稀疏圖，臨街矩陣常用于表示稠密圖鄰接表可以使用包含記錄的數(shù)組或指針類型存儲，鄰接矩陣常用二維數(shù)組存儲。這兩種方式可以存儲有向圖或無向圖，也可以是加權(quán)圖當(dāng)圖較小時(shí)，一般用鄰接矩陣處理。無權(quán)圖的存儲可以用一個(gè)二進(jìn)位代替一個(gè)字節(jié)來節(jié)省空間圖的遍歷DFS的結(jié)果是一棵樹，所有前向邊由父節(jié)點(diǎn)指向子節(jié)點(diǎn)，反向邊由子節(jié)點(diǎn)回指父節(jié)點(diǎn)。在DFS中，可能出現(xiàn)一棵樹或多棵樹的結(jié)果BF

2、S是最簡單的圖搜索算法之一，Prim、Dijkstra等重要算法應(yīng)用了BFS類似的思想。BFS使用到隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，節(jié)點(diǎn)被三次染色后構(gòu)成廣度優(yōu)先樹。BFS的運(yùn)行復(fù)雜度是O(V+E)，是圖G鄰接表大小的一個(gè)線性函數(shù)拓?fù)渑判蛲負(fù)渑判蚴菓?yīng)用于有向無環(huán)圖的一種算法拓?fù)?，是?shù)學(xué)的一個(gè)分支，它對圖形進(jìn)行等價(jià)變換，研究一個(gè)問題或圖形的本質(zhì)。許多魔術(shù)及智力玩具便是拓?fù)鋵W(xué)的廣泛應(yīng)用經(jīng)過拓?fù)渑判虻膱D，形成一個(gè)由所有頂點(diǎn)構(gòu)成的線性序列，它滿足對于任意一條邊(u, v)，u頂點(diǎn)出現(xiàn)在v頂點(diǎn)的前面。因此，這個(gè)序列滿足圖中所有頂點(diǎn)的先后順序最小生成樹算法兩個(gè)最常用的最小生成樹算法是Prim算法和Kruskal算法，漸進(jìn)

3、意義上來說，兩個(gè)算法的時(shí)間復(fù)雜度是相同的，均為O(ElogV)（經(jīng)過堆優(yōu)化）。而Prim算法和Dijkstra算法形式類似，相對比較好記另外，Prim算法中如果用斐波那契堆來實(shí)現(xiàn)最小優(yōu)先隊(duì)列，算法時(shí)間復(fù)雜度還可以改進(jìn)為O(E + VlogV)，不過這種方法在信息學(xué)競賽中并不常見Dijkstra Vs PrimDijkstra算法和Prim算法是圖論中兩個(gè)常見的算法，分別用來求單源最短路和最小生成樹從形式上看，Dijkstra和Prim很相似，有時(shí)候甚至?xí)阉鼈儗戝e(cuò)這次我們從另一個(gè)角度來看看Dijkstra和Prim從Dijkstra看Prim通常來說，盡管它們解決的問題不相同，但是Dijkstra和Prim算法復(fù)雜度都是O(n2)的我們也許在書本或資料中了解過：Dijkstra的時(shí)間復(fù)雜度可以降低到O(nlogn)級別。如何做呢？對，用堆來存儲同樣地，Prim算法也可以用堆降低到O(nlogn)復(fù)雜度的，也就是說生成樹問題也可以在O(nlogn)時(shí)間內(nèi)用Prim算法解決，只不過我們大部分都沒有實(shí)踐過不要小看它，它能讓Prim算法可負(fù)擔(dān)的數(shù)據(jù)范圍擴(kuò)大成百