[算法] 圖論

圖的表示

鄰接矩陣
int G [maxv][maxv]或<vector<vector<int> > G
數(shù)組元素存儲(chǔ)連接與否或連接權(quán)重的信息
如果有多個(gè)邊的相關(guān)屬性桐款，例如多個(gè)權(quán)重豺旬，則可以聲明邊的結(jié)構(gòu)體 struct edge替換上面的int
如果有多個(gè)節(jié)點(diǎn)的相關(guān)屬性，例如節(jié)點(diǎn)的顏色、訪問(wèn)時(shí)間、估計(jì)最短距離等戈抄，只需再單獨(dú)聲明|V|大小的一維數(shù)組即可
鄰接表
vector<int> G[maxv]

for(int i = 0; i < E; i++)  {
  cin >> s >> t;
  G[s].push_back[t];
  // G[t].push_back[s];
}

每個(gè)節(jié)點(diǎn)的鄰接表中存儲(chǔ)連接信息，也可以表示為<vector<vector<int> > G后专，但與鄰接矩陣不同這只能表示無(wú)權(quán)重圖划鸽，對(duì)于單權(quán)重圖也需要聲明邊結(jié)構(gòu)體：
struct edge { int to; int cost; }
vector<edge> G[maxv]

1. 搜索

對(duì)于連通圖，一次搜索可訪問(wèn)全部節(jié)點(diǎn)

BFS

利用BFS可求：

無(wú)權(quán)圖從給定源點(diǎn)出發(fā)到所以可以到達(dá)結(jié)點(diǎn)間的最短路徑
樹(shù)的直徑(樹(shù)的所有最短路徑距離的最大值)：兩次BFS即可實(shí)現(xiàn)戚哎，第二次BFS選擇第一次遍歷得到的最長(zhǎng)路徑的末節(jié)點(diǎn)作為源節(jié)點(diǎn)

DFS

深度優(yōu)先森林的前驅(qū)子圖的深度優(yōu)先森林中包含：
樹(shù)邊（遍歷路徑）裸诽、后向邊（已訪問(wèn)過(guò)的某級(jí)父節(jié)點(diǎn)）、前向邊（已訪問(wèn)過(guò)的某子節(jié)點(diǎn)）型凳、橫邊（其他所有的邊崭捍，包括不同樹(shù)間的邊）
第一次訪問(wèn)邊（u,v）時(shí)，如果v為白色即樹(shù)邊啰脚，如果v為灰色即后向邊殷蛇，如果v為黑色即橫向邊或前向邊（無(wú)向圖中是不會(huì)出現(xiàn)前向邊和橫向邊的）

利用DFS可求：

有向圖或無(wú)向圖是無(wú)環(huán)圖<=>DFS不產(chǎn)生后向邊
對(duì)于無(wú)向圖這一判定算法的時(shí)間復(fù)雜度O(V)與E無(wú)關(guān)，因?yàn)閷?duì)于無(wú)環(huán)的森林|E| < |V|-1橄浓，因此如果存在后向邊粒梦，遍歷V個(gè)結(jié)點(diǎn)后后向邊一定已經(jīng)出現(xiàn)
拓?fù)渑判?br> DFS結(jié)束時(shí)間的反序
$O(V+E)$
連通分量
無(wú)向圖的連通分量個(gè)數(shù)即DFS森林樹(shù)的顆數(shù)
有向圖的強(qiáng)連通分量即對(duì)G和G的轉(zhuǎn)置分別DFS得到的結(jié)果
有向圖的單連通分量判定：
從每個(gè)點(diǎn)作一次DFS藏杖，得到一棵DFS樹(shù)裆馒，如果沒(méi)有出現(xiàn)DFS樹(shù)內(nèi)cross edge和forward edge坐桩，則此圖必為單連通圖
有向圖的半連通分量判定：
計(jì)算強(qiáng)連通分量宅静，對(duì)得到的分量圖SCC進(jìn)行拓?fù)渑判颍绻負(fù)渑判虻慕Y(jié)果<v1,v2...vk>線性鏈的各邊<v0,v1>..<vk-1,vk>存在摹迷，則半連通
時(shí)間復(fù)雜度O(V+E)
銜接點(diǎn)罢吃、橋棒妨、雙連通分量
樸素方法
對(duì)于每個(gè)點(diǎn)露氮，刪除該點(diǎn)判斷圖的連通性O(shè)(V(V+E))
利用深度優(yōu)先森林
前驅(qū)子圖的根節(jié)點(diǎn)是圖的銜接點(diǎn)<=>它在前驅(qū)子圖中至少有兩個(gè)子節(jié)點(diǎn)
歐拉回路
如果圖的每個(gè)節(jié)點(diǎn)的出度等于入度則存在歐拉回路
如果一個(gè)無(wú)向圖連通圖最多只有兩個(gè)奇點(diǎn)（就是度數(shù)為奇數(shù)的點(diǎn)）祖灰，則一定存在歐拉回路
二分圖判定
二分圖：若能將無(wú)向圖G=(V,E)的頂點(diǎn)V劃分為兩個(gè)交集為空的頂點(diǎn)集，并且任意邊的兩個(gè)端點(diǎn)都分屬于兩個(gè)集合畔规，則稱(chēng)圖G為一個(gè)為二分圖
二分圖判定：染色法

LCA 多個(gè)點(diǎn)的最近公共祖先
RMQ區(qū)間最值查詢

2. 連通無(wú)向圖的最小生成樹(shù)

最小生成樹(shù)：
貪心算法核心是找到一個(gè)安全邊(u,v)加入到集合A使得 A U {(u,v)} 依然是最小生成樹(shù)的一個(gè)子集
橫跨切割的權(quán)重最小的邊即輕量級(jí)邊

Kruskal算法：集合A是森林局扶，按權(quán)重從低到高考察每條邊，如果它將兩棵不同的樹(shù)連接起來(lái)就加入到森林A里并完成兩棵樹(shù)的合并
實(shí)現(xiàn)：不相交數(shù)據(jù)結(jié)構(gòu)

MST-Kruskal(G, w)
A = 空集
for each vertex v in G.V
  make-set(v)
sort edges E in G.E in nodecreasing order
for each edge (u,v) in sorted G.E
  if find-set(u) != find-set(v) //否則會(huì)形成環(huán)
    A.push((u,v))
    union(u,v)
return A

時(shí)間復(fù)雜度O(ElgV)

Prim算法：集合A是一棵樹(shù)叁扫，每次加入連接集合A和A之外結(jié)點(diǎn)的所有邊中權(quán)重最小的邊
實(shí)現(xiàn)：優(yōu)先隊(duì)列
增加最小生成樹(shù)的根節(jié)點(diǎn)r作為輸入
v.key存在v和樹(shù)中節(jié)點(diǎn)的所有邊中的最小權(quán)重

MST-Prim(G, w, r)
for each vertex v in G.V
  v.key = 無(wú)窮
  v.pi = null
r.key = 0
Q = G.V
while Q 不為空
  u = extract-min(Q)
  for each v in G.adj[u]
    if v in Q  and w(u,v) < v.key
        v.pi = u
        v.key = w(u,v)

第一次循環(huán)隊(duì)列中為MST根節(jié)點(diǎn)r
建堆總時(shí)間O(V)
extract-min時(shí)間 $lgV$ 共V次
使用二叉堆 $O(VlgV+ElgV) = O(ElgV)$
使用斐波那契堆 $O(E + VlgV)$ 時(shí)間復(fù)雜度與迪杰斯特拉算法相同
差別主要在于for循環(huán)(E次)中v.key隱含的decrease-key操作在斐波那契堆上的執(zhí)行成本可以從lgV降為1

3. 最短路徑

3.1 問(wèn)題分析

最短路徑具有最優(yōu)子結(jié)構(gòu)：最短路徑的子路徑也是最短路
無(wú)權(quán)重圖的最短路徑可以直接使用BFS求解三妈，因此本節(jié)討論的圖均有權(quán)重
最短路徑問(wèn)題可以包含負(fù)權(quán)重邊(例如Bellman-Ford)，但不支持負(fù)權(quán)重環(huán)(不過(guò)Bellman-Ford算法可以檢測(cè)是否存在負(fù)權(quán)重環(huán))
最短路徑必定不包括環(huán)路莫绣，路徑長(zhǎng)度至多為|V| - 1
最短路徑的表示是以源點(diǎn)s為根節(jié)點(diǎn)的一顆最短路徑樹(shù)畴蒲，由于s到每個(gè)可以從s到達(dá)的節(jié)點(diǎn)的最短路徑不唯一，最短路徑樹(shù)不唯一
三角不等式 $\delta(s, v) <= \delta(s, u) + w(v, u)$ $\delta$ 表示兩點(diǎn)間最短路徑

松弛操作

v.d -- 最短路徑估計(jì)

Relax(u, v, w)
if v.d > u.d + w(u, v)
  v.d = u.d + w(u, v)    
  v.pi = u

松弛滿足
上界性質(zhì) $v. d >= \delta(s, v)$
收斂性質(zhì) 一旦 $v.d = \delta(s, v)$ v.d收斂不會(huì)再發(fā)生變化
非路徑性質(zhì) 對(duì)于不可達(dá)點(diǎn) $v.d = \infty$

3.2 單源最短路徑

Bellman-Ford

每條邊松弛|V| -1次（最壞情況下每次循環(huán)只松弛了一條邊）之后如果存在不滿足三角不等式的結(jié)點(diǎn)v.d > u.d + w(u,v)說(shuō)明存在負(fù)權(quán)重環(huán)

時(shí)間復(fù)雜度O(VE)

Bellman-Ford的改進(jìn)

改進(jìn)關(guān)鍵是對(duì)松弛頂點(diǎn)的順序重排序
Yen的改進(jìn)Ex 21-1
分解圖對(duì)節(jié)點(diǎn)拓?fù)渑判蚝髢蓤D交替松弛

DAG-Shortest-Path

DSP只適用于有向無(wú)環(huán)圖
拓?fù)渑判蚝蟀凑展?jié)點(diǎn)依賴(lài)順序依次對(duì)發(fā)節(jié)點(diǎn)發(fā)出的所有邊進(jìn)行松弛
時(shí)間復(fù)雜度O(V + E)

利用DSP可以求解PERT圖的關(guān)鍵路徑：

關(guān)鍵路徑：
將圖中所有權(quán)重變?yōu)樨?fù)數(shù)对室，運(yùn)行DSP 或將松弛操作改為反向操作模燥，初始化對(duì)應(yīng)變?yōu)樨?fù)無(wú)窮

Dijkstra

Dijkstra可用于有環(huán)圖狞玛，但不允許存在負(fù)權(quán)重的邊
貪心策略：維護(hù)一個(gè)已求出最短路徑節(jié)點(diǎn)的集合S，以v.d為key構(gòu)造最小堆涧窒，每次選擇V-S中的最小堆頂，將其加入S并松弛所有與其相鄰的邊锭亏。注意第一次執(zhí)行循環(huán)extract-min得到的是源點(diǎn)s纠吴。

Dijkstra(G, w, s)
for each vertex v in G.V
  v.d = 無(wú)窮大
  v.pi = null
s.d = 0
Q = G.V
while Q 不為空
  u = extract-min(Q)
  S.push(u)
  for each v in G.adj[u]
    if v.d > u.d + w(u, v)
        v.d = u.d + w(u, v)    
        v.pi = u

時(shí)間復(fù)雜度

應(yīng)用

差分約束

將m*n的線性規(guī)劃矩陣看作是n個(gè)節(jié)點(diǎn)和m條邊構(gòu)成的圖的鄰接矩陣的轉(zhuǎn)置
約束圖增加節(jié)點(diǎn) $v_0$ 與其他所有節(jié)點(diǎn)以權(quán)重為0的邊連接
約束條件 $x_j - x_i <= b_k$ 轉(zhuǎn)換為 $w(x_i, x_j) = b_k$
約束圖的最短路徑的解即差分約束系統(tǒng)的解

3.3 多源最短路徑

重復(fù)平方法

類(lèi)比矩陣乘法

Floyd

適用負(fù)權(quán)重邊，不允許存在負(fù)權(quán)重環(huán) O(V^3)
動(dòng)態(tài)規(guī)劃
遞歸定義最優(yōu)解：
中間節(jié)點(diǎn)恰好經(jīng)過(guò)k節(jié)點(diǎn) VS 中間節(jié)點(diǎn)不包括k節(jié)點(diǎn)

Floyd-warshall

利用Floyd求圖的傳遞閉包
有向圖的傳遞閉包：如果存在從i到j(luò)的路徑則閉包中(i,j)有邊相連
每條邊權(quán)重賦值1慧瘤，運(yùn)行Floyd算法戴已，根據(jù)中間求解結(jié)果是否包含無(wú)窮的邊來(lái)判斷 O(n^3)

稀疏圖的Johnson算法-Reweight

適用負(fù)權(quán)重邊，調(diào)用Bellman-ford可檢測(cè)負(fù)權(quán)重環(huán)
要滿足重新賦值權(quán)重后最短路徑不變锅减，新增節(jié)點(diǎn)s與所有節(jié)點(diǎn)相連且w(s,v) = 0糖儡，使用Bellman-ford計(jì)算 $\delta(s,v)$ ，令 $h(v) = \delta(s,v)$ 怔匣，則新權(quán)重 $w'(u,v) = w(u,v)+h(u)-h(v)$ 且負(fù)權(quán)重邊均變?yōu)檎樟\(yùn)行V次Dijkstra算法，最后將最短路徑還原即可每瞒。
$O(V^2 \lg V+VE)$

4. 最大流

定義

流網(wǎng)絡(luò)（連通圖金闽、單向邊）
多源多匯：增加超級(jí)源點(diǎn)和超級(jí)匯點(diǎn)
存在雙向邊：增加一個(gè)額外節(jié)點(diǎn)
流
滿足容量限制和流量守恒
流f的值為從源節(jié)點(diǎn)流出的總流量減流入源節(jié)點(diǎn)的總流量
殘余網(wǎng)絡(luò)
殘余容量的反向容量最多將其正向容量抵消

殘存網(wǎng)絡(luò)每條邊必須允許大于0的流量通過(guò)

增廣路徑
殘余網(wǎng)絡(luò)中從s到t的簡(jiǎn)單路徑

增廣路徑的殘余容量

割

注意割的容量不包括反向邊，而橫跨任何割的凈流量都相同

Ford-Fulkerson方法

初始化流為0剿骨，沿著殘余網(wǎng)絡(luò)的增廣路徑增加流代芜，直至殘余網(wǎng)絡(luò)不包括任何增廣路徑
最大流最小割定理
三條件等價(jià)：
1.殘余網(wǎng)絡(luò)不包括任何增廣路徑
2.f是最大流
3.流網(wǎng)絡(luò)的某個(gè)切割c=|f|
基本Ford-Fulkerson算法
O(E|f*|)
Edmonds-Karp算法
O(VE^2)

二分圖匹配

匹配
滿足每個(gè)節(jié)點(diǎn)最多只有一條邊相連的邊的子集
增加源點(diǎn)匯點(diǎn)，賦值單位權(quán)重構(gòu)造G'浓利，則流網(wǎng)絡(luò)的最大流即二分圖的最大匹配
O(VE)

圖論500題

https://blog.csdn.net/luchy0120/article/details/39696417

https://blog.csdn.net/luomingjun12315/article/details/47438607

最后編輯于：2020.02.02 18:13:26

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末挤庇，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子贷掖，更是在濱河造成了極大的恐慌嫡秕，老刑警劉巖，帶你破解...
沈念sama閱讀 211,817評(píng)論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件苹威，死亡現(xiàn)場(chǎng)離奇詭異淘菩，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)屠升，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,329評(píng)論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)潮改，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人腹暖，你說(shuō)我怎么就攤上這事汇在。” “怎么了脏答？”我有些...
開(kāi)封第一講書(shū)人閱讀 157,354評(píng)論 0贊 348
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵糕殉，是天一觀的道長(zhǎng)亩鬼。經(jīng)常有香客問(wèn)我，道長(zhǎng)阿蝶，這世上最難降的妖魔是什么雳锋？我笑而不...
開(kāi)封第一講書(shū)人閱讀 56,498評(píng)論 1贊 284
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮羡洁，結(jié)果婚禮上玷过，老公的妹妹穿的比我還像新娘。我一直安慰自己筑煮，他們只是感情好辛蚊，可當(dāng)我...
茶點(diǎn)故事閱讀 65,600評(píng)論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布。她就那樣靜靜地躺著真仲，像睡著了一般袋马。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上秸应，一...
開(kāi)封第一講書(shū)人閱讀 49,829評(píng)論 1贊 290
城市分裂傳說(shuō)
那天虑凛，我揣著相機(jī)與錄音，去河邊找鬼软啼。笑死卧檐，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的焰宣。我是一名探鬼主播霉囚，決...
沈念sama閱讀 38,979評(píng)論 3贊 408
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼匕积！你這毒婦竟也來(lái)了盈罐？” 一聲冷哼從身側(cè)響起，我...
開(kāi)封第一講書(shū)人閱讀 37,722評(píng)論 0贊 266
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤闪唆，失蹤者是張志新（化名）和其女友劉穎盅粪，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體悄蕾，經(jīng)...
沈念sama閱讀 44,189評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡票顾，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,519評(píng)論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了帆调。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片奠骄。...
茶點(diǎn)故事閱讀 38,654評(píng)論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖番刊，靈堂內(nèi)的尸體忽然破棺而出含鳞，到底是詐尸還是另有隱情，我是刑警寧澤芹务，帶...
沈念sama閱讀 34,329評(píng)論 4贊 330
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布蝉绷，位于F島的核電站鸭廷，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏熔吗。R本人自食惡果不足惜辆床，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,940評(píng)論 3贊 313
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望桅狠。院中可真熱鬧讼载，春花似錦、人聲如沸垂攘。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 30,762評(píng)論 0贊 21
一樁弒父案淤刃，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)晒他。三九已至，卻和暖如春逸贾，著一層夾襖步出監(jiān)牢的瞬間陨仅，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 31,993評(píng)論 1贊 266
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工铝侵，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留灼伤，地道東北人。一個(gè)月前我還...
沈念sama閱讀 46,382評(píng)論 2贊 360
代替公主和親
正文我出身青樓咪鲜，卻偏偏與公主長(zhǎng)得像狐赡，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子疟丙，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,543評(píng)論 2贊 349