圖論及其應(yīng)用

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