圖論及其應(yīng)用

圖論及其應(yīng)用山東省青島二中王元煒圖論及其應(yīng)用圖的定義有向圖無向圖特殊的圖——樹圖的最短路算法dijbellman-fold(spfa)floyed圖的生成樹primkruskal潴留算法有向圖的強連通分量tarjan算法有向圖的拓撲序拓撲排序圖的定義1.定義圖G={V,E}V代表圖的頂點集合，E代表圖的邊的集合。2.對于有向圖，E中的每個元素是由有序點對<p,q>構(gòu)成，代表p->q的一條邊。3.對于無向圖，E中的每個元素是由無序點對(p,q)構(gòu)成，代表p和q之間的一條邊。4.如果一個無向圖滿足|E|+1=|V|并且聯(lián)通，那么我們成這個圖是一棵樹5.所有邊都沒有權(quán)值或者權(quán)值都相同叫做無權(quán)圖，否則叫做有權(quán)圖。圖的最短路圖的最短路在實際應(yīng)用中非常多我們說的圖的最短路默認為有向圖，對于無向圖可以理解成每條邊分成兩條邊，方向相反權(quán)值相同。簡單就是說從一個頂點出發(fā)，經(jīng)過一些列邊的集合，到達另外一個點。這些邊的權(quán)值加起來最小最短路算法對于一個無權(quán)圖，那么可以使用寬度優(yōu)先搜索(bfs)進行得到答案時間復(fù)雜度O(n)最短路算法如果我們需要知道所有的點對之間的最短路，可以使用floyed的傳遞閉包方法。floyed算法思想：我們每次選擇一個中間點，然后枚舉起點和終點，用通過中間點的最短路徑更新起點和終點之間的最短路徑時間復(fù)雜度O(n^3)floyed代碼實現(xiàn)代碼非常簡單注意枚舉順序最短路算法如果我們只需要知道從一個點出發(fā)到其他點的最短路，而且圖中的邊權(quán)全部為正，我們可以使用dijsktra算法。算法思想：我們每次選擇一個距離原點最近而且沒有被訪問過的點，然后我們訪問這個節(jié)點，并且用這個點的所有出邊去更新其他所有節(jié)點從原點出發(fā)的距離，重復(fù)此算法直到所有點都被訪問過為止時間復(fù)雜度O(n^2+m)使用堆和臨街表優(yōu)化可以做到O(nlogn+nlogm)dijsktra算法代碼實現(xiàn)dijsktra算法代碼實現(xiàn)使用堆優(yōu)化Bellman-fold算法(spfa)如果圖中出現(xiàn)了負權(quán)變，甚至有可能出現(xiàn)負權(quán)環(huán)（此時最短路不存在）。其他兩個算法就不再適用。這里我們介紹bellman-fold算法bellman-fold算法將判定一個圖是否存在最短路，如果存在則返回，否則返回不存在最短路Bellman-fold算法(SPFA)算法思想：我們將算法進行n此，每次從所有點出發(fā)更新所有后繼節(jié)點的最短路情況如果所有節(jié)點都沒有被更新則返回最短路，如果第n此依然更新，那就返回沒有答案時間復(fù)雜度O(nm)對于一個隊列進行優(yōu)化的方式，我們每次更新一個點就把這個點加入隊列，每次從隊列里面更新。這個優(yōu)化，對于一般的圖來說輔助度是O(Km)的K是常數(shù)SPFA算法實現(xiàn)小試身手在平面上有n個點，每個點都有坐標(x,y)我們每次可以從點A到達點Ｂ，的條件是A,B之間的距離不超過L,給定n,L,和每個點的坐標，求從一號點到達n好點的最短距離n<=1000小試身手直接暴力求出任意兩點之間的距離還是不可達，然后使用Dijsktra算法即可小試身手給你一個平面，上面有n個點，每個點有坐標(x,y)從一個點A到B的距離定義為D=min(A.x-B.x,A.y-B.y)求1-n的最短路n<=1000howaboutn<=100000小試身手默默的等式小試身手默默的等式，和今天的T2類似，還是在取模的意義下建圖。小試身手對于n<=1000我們依然可以直接暴力建出圖來進行Dijsktra算法但是對于n<=10000的測試點，所有邊一共有10^10條，我們無法存下來但是我們發(fā)現(xiàn)，只有x坐標相鄰和y坐標相鄰的邊才有意義(為什么？)，然后就可以建出圖來用堆優(yōu)化的Dij或者spfa過掉小試身手給你一個n個點的圖，小Q有q個詢問，每次詢問任意兩點之間的最短路n<=200,q<=4000000小試身手顯然每次使用Dijsktra是不可能的注意到我們關(guān)心的是任意兩對之間的最短路使用floyed預(yù)處理，每次詢問O(1)回答即可復(fù)雜度O(n^3+q)圖的生成樹對于一個連通圖G={V,E}定義圖的生成樹G'={V,E'}其中E'∈E，|E'|=|V|+1,并且G'聯(lián)通那么G'就叫做G的一個生成樹生成樹的性質(zhì)生成樹有n個點和n-1條邊構(gòu)成，并且聯(lián)通生成樹保留了原圖的最精華的信息（至于為什么之后會說到）生成樹任意兩點之間有且僅有一條路徑最小生成樹對于G的所有生成樹，邊權(quán)和最小的生成樹稱為最小生成樹求最小生成樹的算法：Prim&Kruskal這兩個算法的本質(zhì)就是貪心至于貪心為什么是對的這里不講了理解思想就可以了Prim算法及思想首先我們將V分成兩部分U,SU∩S=?U∪S=V一開始S中只有任意以個節(jié)點每次我們枚舉每條U，S之間的邊權(quán)最小的邊S中這條邊的端點刪除并加入U我們可以每次更新S中點的這個值不需要每次枚舉邊復(fù)雜度O(n^2)如果使用堆優(yōu)化可以做到O(nlogn+nlogm)Prime的代碼實現(xiàn)kruskal算法思想我們把所有邊按照權(quán)值從小到大排序然后枚舉每條邊，順次加入最小生成樹，如果這條邊加入之后依然可以形成最小生成樹就加入，否則就跳過第二步的詢問可以用并查集維護做到O(nαn)kruskal算法實現(xiàn)算法比較Prim只能求出最小生成樹的權(quán)值，無法得到具體的形態(tài)而Kruskal可以求出形態(tài)，所以建議使用KruSkal小試身手有n個點m條邊，求n->m的一條路徑使得邊權(quán)最大的那條邊最小n,m<=100000小試身手用kruskal求出最小生成樹然后求最短路即可（此時最短路的定義有變化但是依然可以求出）小試身手NOIP2013Day1T3給你一個圖，有Q此詢問，每次詢問任意兩點之間邊權(quán)最大路徑的最小值小試身手求出最小生成樹然后使用倍增算法快速求出路徑的值小試身手USACO2008Oct灌水Farmerjohn有一個農(nóng)場需要灌溉，首先我們序號給一個位置引水需要一定的花費，然后任一兩塊農(nóng)田之間連接水渠也有一定的花費，求全部灌溉的最小花費n<=1000小試身手首先建立一個超級原點，和所有點連邊權(quán)值是飲水的代價，然后求最小生成樹即可其他最有比率生成樹最小乘積生成樹潴留算法強連通分量對于一個有向圖G的一個導(dǎo)出子圖G'={V',E'}到處子圖的定義是：其中V'是V的子集，當且僅當對于任意<x,y>∈E且x∈V',y∈V'則<x,y>屬于E'如果該導(dǎo)出子圖中任意兩點可達，則成為G'是G的一個強連通分量如果G'是G的一個強連通分量，且不存在一個H是G的強連通分量滿足G包含于H，G是一個極大強連通分量強連通分量的性質(zhì) 強連通分量之間任意兩點互相可達，任意兩個強連通分量之間的關(guān)系是拓撲的Tarjan算法Tarjan算法是基于對圖深度優(yōu)先搜索的算法，每個強連通分量為搜索樹中的一棵子樹。搜索時，把當前搜索樹中未處理的節(jié)點加入一個堆棧，回溯時可以判斷棧頂?shù)綏Ｖ械墓?jié)點是否為一個強連通分量。tarjan算法定義DFN(u)為節(jié)點u搜索的次序編號(時間戳)，Low(u)為u或u的子樹能夠追溯到的最早的棧中節(jié)點的次序號。由定義可以得出Low(u)=MinDFN(u),Low(v),(u,v)為樹枝邊，u為v的父節(jié)點DFN(v),(u,v)為指向棧中節(jié)點的后向邊(非橫叉邊)當DFN(u)=Low(u)時，以u為根的搜索子樹上所有節(jié)點是一個強連通分量。tarjan算法tarjan算法拓撲排序每次選擇一個入度