圖的定義

　　G=(V,E)

　　G代表圖

　　V代表|V|為結(jié)點數(shù)

　　E代表|E|為邊的條數(shù)

圖的表示

　　

　　圖的常規(guī)標準表示方式有兩種，一種是鄰接鏈表、一種是鄰接矩陣。

　　在稀疏圖中多用鏈表，稠密圖中多用矩陣。（稀疏與稠密看的是|E|與|V|的2次方的比較，|E|遠遠小于|V|的2次方為稀疏圖）

　　鄰接鏈表的一大缺點是無法快速判斷一條邊是否是圖中的，唯一的辦法是搜索結(jié)點找邊。

　　圖規(guī)模比較小時，更傾向于使用鄰接矩陣表示法。

廣度優(yōu)先搜索

　　Prim的最小生成樹算法和Dijkstra的單源最短路徑算法都用了廣度優(yōu)先搜索。

　　

深度優(yōu)先搜索

最小生成樹

　　無向圖中的最小權(quán)重樹為最小生成樹

　　定義：在連通無向圖G=(V,E)中找到一個無環(huán)子集T屬于E，既能夠?qū)⑺械慕Y(jié)點（針腳）連接起來，又具有最小的權(quán)重。由于T是無環(huán)的，并且連通所有結(jié)點，因此，T必然是一棵樹。我們稱之為最小生成樹。

Kruskal算法和Prim算法

　　這兩個算法都是最小生成樹算法

Kruskal算法

　　每次找最小的邊，看是否在同一個樹里（邊（u，v）中u和v都在樹里則為不安全）

　　用的貪心策略

　　下面為偽代碼和解釋

MST-KRUSKAL(G,w)
    A=null
    for each vertex v∈G.V
        MAKE-SET(v) //初始化樹根
    sort the edges of G.E into nondecreasing order by weight w
    for each edge(u,v)∈G.E, take in nondecreasing order by weight //循環(huán)邊（最小權(quán)到最大權(quán)）
        if FIND-SET(u) != FIND-SET(v) //u與v是否同一棵樹
            A=AU{(u,v)} //A中加入邊（u，v）
            UNION(u,v) //兩棵樹中的結(jié)點合并
    return A

Prim算法

　　從一個點開始貪心其中最小的權(quán)邊加入樹中

　　下面為偽代碼

MST-PRIM(G,w,r)
    for each u∈G.V                      //初始化每個結(jié)點u屬于G.V
        u:key = 無限                     //u.key=無窮
        u:π = NIL                       //u.π=空
    r:key = 0;                          //根點的最小權(quán)為0
    Q=G.V                               //最小優(yōu)先隊列初始化為G.V
    while Q != null
        u=EXTRACT-MIN(Q)         　　　　//找Q中最小權(quán)點賦值給u
        for each v∈G.Adj[u]          　 //循環(huán)與u相連的點v
        if v∈Q and w(u,v) < v.key 　　　//如果v屬于Q 點u的權(quán)值加上邊(u,v)的權(quán)值小于v.key
            v.π = u                    //v點的父結(jié)點 = u
            v.key = w(u,v)             //v點的權(quán)值 = 點u的權(quán)值加上邊(u,v)的權(quán)值

單源最短路徑

　　定義：給定一個圖G=（V,E），我們希望找到從給定源結(jié)點s∈V到每個結(jié)點v∈V的最短路徑。

　　幾個變體問題：

　　　　1）單目的地最短路徑問題：每個結(jié)點v到給定目的地點的最短路徑

　　　　2）單結(jié)點對最短路徑問題：結(jié)點u到結(jié)點v的最短路徑

　　　　3）所有結(jié)點對最短路徑問題：對于每個結(jié)點u和v，找到其最短路徑

最短路徑的最優(yōu)子結(jié)構(gòu)

　　兩個結(jié)點之間的一條最短路徑包含著其他的最短路徑（最短路徑的子路徑也是最短路徑）。

最短路徑的表示

　　用前驅(qū)子圖的表示方法，具體形式為每個結(jié)點開辟一個空間存儲它的上一結(jié)點。（其實另開辟一個數(shù)組也是可以的）

松弛操作

　　松弛技術(shù)：對于每個結(jié)點v來說，我們維持一個屬性v.d，用來記錄從源結(jié)點s到結(jié)點v的最短路徑權(quán)重的上界。我們稱v.d為s到v的最短路徑估計。

　　松弛過程：v結(jié)點本身有一個最短估計值為v.d，又找到一條到v的路徑把權(quán)值跟v.d進行比較，如果后者小，則更新v.d和v.π。

　　以下是偽代碼

PELAX(u,v,w)
    if v.d > u.d + w(u,v) //如果新路徑權(quán)值小于原來的估算權(quán)值
        v.d = u.d + w(u,v) //估算權(quán)值被更新
        v.π = u //前驅(qū)更新

Bellman-Ford算法

　　注意：此算法可處理邊權(quán)值為負值的情況，此算法可判斷出負值成環(huán)的存在。

　　以下為偽代碼

BELLMAN-FORD(G,w,s)

    INITIALIZE-SINGLE-SOURCE(G,s) //初始化圖

    for i = 1 to |G.V| - 1 //循環(huán)全部結(jié)點
        for each edge(u,v)∈G.E //循環(huán)每個結(jié)點所連邊
            RELAX(u,v,w) //松弛操作
    
    for each edge(u,v)∈G.E //循環(huán)每條邊
        if v.d > u.d + w(u,v) //測試是否還能松弛，從而找到環(huán)
            return FALSE //如果能松弛，則返回False

    return TRUE //運行正確放回True

有向無環(huán)圖的單源最短路徑問題

　　根據(jù)結(jié)點的拓撲排序次序來對帶權(quán)重的有向無環(huán)圖G=（V，E）進行邊的松弛。

　　注意：1.如果源結(jié)點s不是拓撲排序后的第一個結(jié)點，直到找到源結(jié)點s前的所有結(jié)點可以無視。

　　　　　2.邊權(quán)非負

　　以下是偽代碼

DAG-SHORTEST-PATHS(G,w,s)
    topologically sort the vertices of G //拓撲排序圖G
    INITALIZE-SINGLE-SOURCE(G,s) //初始化G，并設源點s
    for each vertex u, taken in topologically sorted order //按拓撲排序后結(jié)點順序循環(huán)結(jié)點
        for each vertex v∈G.Adj[u] //循環(huán)結(jié)點所連邊
            RELAX(u,v,w) //松弛操作

Dijkstra算法

　　解決帶權(quán)重的有向圖上單源最短路徑問題

　　注意：1.邊權(quán)非負

　　　　　2.Dijkstra算法比Bellman-Ford算法運行速度快。

　　算法核心思想：重復從結(jié)點集V-S中選擇最短路徑估計最小的結(jié)點u，加入集合S，對從u出發(fā)的邊進行松弛。（V為全部結(jié)點集合，S為已使用結(jié)點集合）

　　以下是偽代碼

DIJKSTRA(G,w,s)
    INITIALIZE-SINGLE-SOURCE(G,s) //初始化圖G，設源點s
    S=空 //初始化集合S為空
    Q=G.V //初始化集合Q，為V
    while Q != 空
        u = EXTRACT-MIN(Q) //找出Q中最小估算結(jié)點，賦值給u，并在Q中刪除
        S = S U {u} //將結(jié)點u加入集合S中
        for each vertex v∈G.Adj[u] //循環(huán)與u相連的每個點
            RELAX(u,v,w) //松弛操作

　　

　　

總結(jié)

以上是生活随笔為你收集整理的算法导论精华总结 ~ 图算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。