圖論及其應(yīng)用

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