1.基本圖算法

參見基本的圖算法
 參見深度優(yōu)先搜索和廣度優(yōu)先搜索專題

圖的表示包括鄰接鏈表和鄰接矩陣
廣度優(yōu)先搜索：算法需要在發(fā)現(xiàn)所有距離源節(jié)點(diǎn)s為k（k條邊）的所有結(jié)點(diǎn)之后送淆，才會發(fā)現(xiàn)距離源節(jié)點(diǎn)s為k+1的其他結(jié)點(diǎn)衰琐。
深度優(yōu)先搜索：深度優(yōu)先搜索總是對最近才發(fā)現(xiàn)的結(jié)點(diǎn)v的出發(fā)邊進(jìn)行搜索痪枫，直到該節(jié)點(diǎn)的所有出發(fā)邊都被發(fā)現(xiàn)為止蛋勺。一旦結(jié)點(diǎn)v的所有出發(fā)邊都被發(fā)現(xiàn)残腌，搜索則回溯到v的前驅(qū)結(jié)點(diǎn)村斟，來搜索該前驅(qū)結(jié)點(diǎn)的其他出發(fā)邊贫导。
該過程一直持續(xù)到從源節(jié)點(diǎn)可以達(dá)到的所有結(jié)點(diǎn)都被發(fā)現(xiàn)為止。
拓?fù)渑判颍ㄊ褂蒙疃葍?yōu)先搜索）：對于一個(gè)有向無環(huán)圖G = (V, E)來說蟆盹，其拓?fù)渑判蚴荊中所有結(jié)點(diǎn)的一種線性次序孩灯，該次序滿足如下條件：
如果圖G包含邊(u ,v)，則結(jié)點(diǎn)u在拓?fù)渑判蛑谐鲇诮Y(jié)點(diǎn)v的前面（如果G含有回路逾滥，則不可能排出一個(gè)線性次序）峰档。
強(qiáng)連通分量（使用深度優(yōu)先搜索/拓?fù)渑判颍喝绻粋€(gè)有向圖中任意兩個(gè)頂點(diǎn)互相可達(dá)，則該有向圖是強(qiáng)連通的寨昙。有向圖的強(qiáng)連通分量是“相互可達(dá)”關(guān)系下頂點(diǎn)的等價(jià)類讥巡。
有向圖G = (V, E)的強(qiáng)連通分量是一個(gè)最大結(jié)點(diǎn)集合 C包含于V，對于該集合中的任一對結(jié)點(diǎn)u和v來說毅待，路徑 u ->...-> v和v ->...-> u同時(shí)存在尚卫，也就是u和v可以互相可達(dá)。

2. 最小生成樹——無向圖

參見最小生成樹

使用貪心算法求解尸红，關(guān)鍵在于對貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)的證明吱涉。
Kruskal算法：集合A是一個(gè)森林，每次加入到集合A中的安全邊永遠(yuǎn)是權(quán)重最小的連接兩個(gè)不同分量的邊外里。
Prim算法（廣度優(yōu)先搜索）：集合A是一棵樹怎爵，每次加入到A中的安全邊永遠(yuǎn)是連接A和A之外某個(gè)節(jié)點(diǎn)的邊中權(quán)重最小的邊。

3.單源最短路徑

參見最短路徑專題

給定一個(gè)帶權(quán)重的有向圖G=(V, E)和權(quán)重函數(shù)w:E ->R盅蝗，該權(quán)重函數(shù)將每條邊映射到實(shí)數(shù)值的權(quán)重上鳖链。
圖中一條路徑p=<v_{0, v₁, ..., v_k>的權(quán)重w(p)是構(gòu)成該路徑的所有邊的權(quán)重之和：}

定義從結(jié)點(diǎn)u到結(jié)點(diǎn)v的最短路徑權(quán)重δ(u, v)如下：

從結(jié)點(diǎn)u到結(jié)點(diǎn)v的最短路徑則定義為任何一條權(quán)重為w(p) = δ(u, v)的從u到v的路徑p。
最短路徑問題
1）單源最短路徑問題
給定一個(gè)圖G=(V, E)墩莫，希望找到從給定源節(jié)點(diǎn)s∈V到每個(gè)結(jié)點(diǎn)v∈V的最短路徑芙委。
2）單目的地最短路徑問題
找到從每個(gè)結(jié)點(diǎn)v到給定目的地結(jié)點(diǎn)t的最短路徑。如果將圖的每條邊的方向翻轉(zhuǎn)過來狂秦，可以將該問題轉(zhuǎn)換為單元最短路徑問題
3）單節(jié)點(diǎn)對最短路徑問題
找到從給定結(jié)點(diǎn)u到給定v的最短路徑灌侣。如果解決了針對單個(gè)結(jié)點(diǎn)u的單源最短路徑問題，那么也就解決了這個(gè)問題
Bellman-Ford算法——O(VE)
對每條邊調(diào)用|V| - 1次松弛操作裂问。
SPFA算法——對Bellman-Ford的一個(gè)改進(jìn)（廣度優(yōu)先搜索）
建立一個(gè)先進(jìn)先出的隊(duì)列用來保存待優(yōu)化的結(jié)點(diǎn)侧啼，優(yōu)化時(shí)每次取出隊(duì)首結(jié)點(diǎn)u，并且用u點(diǎn)當(dāng)前的最短路徑估計(jì)值對u的所有鄰接點(diǎn)v進(jìn)行松弛操作堪簿，如果v點(diǎn)的最短路徑估計(jì)值有所調(diào)整痊乾，且v點(diǎn)不在當(dāng)前的隊(duì)列中，就將v點(diǎn)放入隊(duì)尾椭更。這樣不斷從隊(duì)列中取出結(jié)點(diǎn)來進(jìn)行松弛操作哪审，直至隊(duì)列空為止。
有向無環(huán)圖的按拓?fù)漤樞蜻M(jìn)行松弛的算法——Θ(V + E)
非負(fù)權(quán)重有向無環(huán)圖Dijkstra算法（貪心算法）（廣度優(yōu)先搜索）
算法維持集合S虑瀑，從源節(jié)點(diǎn)s到該集合中每個(gè)結(jié)點(diǎn)之間的最短路徑已經(jīng)被找到协饲。
算法重復(fù)從結(jié)點(diǎn)集V-S中選擇最短路徑估計(jì)最小的結(jié)點(diǎn)u畏腕，將u加入到集合S，然后對所有從u發(fā)出的邊進(jìn)行松弛茉稠。
二叉堆——O((V+E)lgV)
斐波那契堆——O(VlgV+E)
差分約束系統(tǒng)——?dú)w約為單源最短路徑問題（核心依據(jù)是三角不等式性質(zhì)）

4.所有結(jié)點(diǎn)對的最短路徑問題

參見最短路徑專題

所有結(jié)點(diǎn)對最短路徑問題
對于每對結(jié)點(diǎn)u和v，找到從結(jié)點(diǎn)u到結(jié)點(diǎn)v的最短路徑把夸。
基本方法和重復(fù)平方法——Θ(n⁴)和Θ(n³lgn)
1）動態(tài)規(guī)劃
2）基本方法去掉一個(gè)不確定的邊而线，需要遍歷找到是哪個(gè)邊
3）重復(fù)平方法與基本方法的區(qū)別在于：基本方法到最終解，每次增加一條邊恋日；重復(fù)平方法每次增加一倍膀篮。
Floyd-Warshall——Θ(n³)
1）動態(tài)規(guī)劃
2）Floyd-Warshall去掉中間一個(gè)確定的點(diǎn)，不用遍歷求最小
Johnson算法——O(V2lgV+VE)（稀疏圖特別適合）
1）基于Bellman-Ford判斷是否有負(fù)值環(huán)路
2）最大的特色是基于單源最短路徑算法來進(jìn)行岂膳，對每一點(diǎn)分別利用Dijkstra算法（時(shí)間效率最好的單源最短路徑算法）
3）Dijkstra算法有限值誓竿，就利用“差分約束系統(tǒng)”里面的方法，利用三角不等式谈截，將w'(u, v)變成非負(fù)的

5.最大流

參見最大流

5.1 最大流問題

（流網(wǎng)絡(luò)）流網(wǎng)絡(luò)G=(V, E)是一個(gè)有向圖筷屡，圖中每條邊(u, v) ∈E有一個(gè)非負(fù)的容量值c(u, v) ≥ 0。
并且如果邊集合E包含一條邊(u, v)簸喂，則圖中不存在反方向的邊(v, u)毙死。
如果(u, v) ? E，定義c(u, v) = 0喻鳄，且圖中不允許自循環(huán)扼倘。
兩個(gè)特殊結(jié)點(diǎn)：源結(jié)點(diǎn)s和匯點(diǎn)t。每個(gè)結(jié)點(diǎn)都在從源結(jié)點(diǎn)到匯點(diǎn)的某條路徑上除呵。即對于每個(gè)結(jié)點(diǎn)v∈V再菊，流網(wǎng)絡(luò)包含一條路徑s -> v -> t。
因此颜曾，流網(wǎng)絡(luò)是連通的纠拔，且由于源節(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)都至少有一條進(jìn)入的邊，則|E| ≥ |V| -1泛啸。
（流）設(shè)G=(V, E)是一個(gè)流網(wǎng)絡(luò)绿语，其容量函數(shù)為c。設(shè)s為網(wǎng)絡(luò)的源結(jié)點(diǎn)候址，t為匯點(diǎn)吕粹。G中的流是一個(gè)實(shí)值函數(shù)f: V x V -> R，滿足下面兩條性質(zhì)：
1）容量限制：對于所有的結(jié)點(diǎn)u, v ∈ V岗仑，要求 0 ≤ f(u, v) ≤ c(u, v)匹耕。
f(u, v)為從結(jié)點(diǎn)u到結(jié)點(diǎn)v的流。
2）流量守恒：對于所有的結(jié)點(diǎn)u ∈ V-{s, t}荠雕，要求

當(dāng)(u, v) ? E時(shí)稳其，從結(jié)點(diǎn)u到結(jié)點(diǎn)v之間沒有流驶赏，因此f(u, v) = 0.
（流的值|f|）一個(gè)流f的值|f|定義如下：

流f的值是從源結(jié)點(diǎn)流程的總流量減去流入源結(jié)點(diǎn)的總流量。通常既鞠，一個(gè)流網(wǎng)絡(luò)不會有任何進(jìn)入源結(jié)點(diǎn)的邊煤傍。也即后面的項(xiàng)為0.
（最大流問題）在最大流問題中，給定一個(gè)流網(wǎng)絡(luò)G嘱蛋、一個(gè)源結(jié)點(diǎn)s蚯姆、一個(gè)匯點(diǎn)t，希望找到值最大的一個(gè)流洒敏。

5.2 四種解法（本質(zhì)是兩種解法：Ford-Fulkerson和推送—重貼標(biāo)簽算法）

Ford-Fulkerson方法——O(E|f*|)
Edmonds-Karp算法（Ford-Fulkerson方法的一種實(shí)現(xiàn)）——O(VE2)
這里主要是約定了查找增廣路徑的方法：尋找s到t的最短路徑龄恋。
使用廣度優(yōu)先搜索來改善。
在殘存網(wǎng)絡(luò)中選擇的增廣路徑是一條從源結(jié)點(diǎn)s到匯點(diǎn)t的最短路徑凶伙，其中每條邊的權(quán)重為單位距離郭毕。
推送—重貼標(biāo)簽算法—— O(V2E)
前置重貼標(biāo)簽算法（推送—重貼標(biāo)簽算法的一種實(shí)現(xiàn)）—— O(V3)