圖論 之 圖的基本算法課件

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

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

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