第四章 圖
4.2 有向圖
在有向圖中，邊是單邊的：每條邊所連接的兩個(gè)頂點(diǎn)都是一個(gè)有序?qū)Τ亢幔麄兊泥徑有允菃蜗虻摹?/p>
4.2.1 術(shù)語
一幅有方向性的圖(或有向圖)是由一組頂點(diǎn)和一組有方向的邊組成的，每條有方向的邊都連接著有序的一對(duì)頂點(diǎn)。
在一幅有向圖中，有向路徑由一系列頂點(diǎn)組成辟拷，對(duì)于其中的每個(gè)頂點(diǎn)都存在一條有向邊從它指向序列的下一個(gè)頂點(diǎn)。
有向環(huán)為一條至少含有一條邊且起點(diǎn)和終點(diǎn)相同的有向路徑阐斜。
簡(jiǎn)單有向環(huán)是一條(除了起點(diǎn)和終點(diǎn)必須相同之外)不含有重復(fù)的頂點(diǎn)和邊的環(huán)衫冻。
我們假設(shè)有向路徑都是簡(jiǎn)單的，除非我們明確指出了某個(gè)重復(fù)了的頂點(diǎn)谒出。
4.2.2有向圖的數(shù)據(jù)類型
4.2.2.1 有向圖的表示
我們使用鄰接表來表示有向圖隅俘，其中邊v->w表示為頂點(diǎn)v所對(duì)應(yīng)的鄰接鏈表包含一個(gè)w頂點(diǎn)。
4.2.2.2 有向圖取反
API中添加了一個(gè)方法reverse()笤喳。它返回有向圖的一個(gè)副本为居，但將其中所有邊的方向反轉(zhuǎn)。
Digraph數(shù)據(jù)類型
代碼：
public class Digraph {
private final int V;
private int E;
private Bag<Integer>[] adj;
public Digraph(int V) {
this.V = V;
this.E = 0;
adj = (Bag<Integer>[]) new Bag[V];
for (int i = 0; i < V; i++) {
adj[i] = new Bag<>();
}
}
public int getE() {
return E;
}
public int getV() {
return V;
}
public void addEdge(int v, int w) {
adj[v].add(w);
E++;
}
public Iterable<Integer> adj(int v) {
return adj[v];
}
public Digraph reverse() {
Digraph R = new Digraph(V);
for (int v = 0; v < V; v++) {
for (int w : adj[v])
R.addEdge(w, v);
}
return R;
}
public String toString() {
String s = V + " vertices," + E + " edges\n";
for (int v = 0; v < V; v++) {
s += v + ": ";
for (int w : this.adj(v)) {
s += w + " ";
}
s += "\n";
}
return s;
}
}
4.2.3有向圖的可達(dá)性
單點(diǎn)可達(dá)性杀狡。給定一幅有向圖和一個(gè)起點(diǎn)s蒙畴，回答"是否存在一條從s到給定頂點(diǎn)v的有向路徑？"等類似問題呜象。
在添加了一個(gè)接受多個(gè)頂點(diǎn)的構(gòu)造函數(shù)之后膳凝，這份API使得用力能夠解決一個(gè)更加一般的問題。
多點(diǎn)可達(dá)性恭陡。給定一幅有向圖和頂點(diǎn)的集合蹬音，回答“是否存在一條從集合中的任意頂點(diǎn)到達(dá)給定頂點(diǎn)v 的有向路徑？”等類似問題休玩。
算法：有向圖的可達(dá)性
public class DirectedDFS {
private boolean[] marked;
public DirectedDFS(Digraph g, Integer s) {
marked = new boolean[g.getV()];
dfs(g, s);
}
public DirectedDFS(Digraph g, Iterable<Integer> sources) {
marked = new boolean[g.getV()];
for (int s : sources) {
dfs(g, s);
}
}
private void dfs(Digraph g, int v) {
marked[v] = true;
for (int w : g.adj(v)) {
if (!marked[w])
dfs(g, w);
}
}
public boolean marked(int v) {
return marked[v];
}
}
4.2.3.2 有向圖的尋路
DepthFirstPaths和BreadthFirstPaths是有向圖處理的重要代碼著淆。它們可以高效地解決以下問題。
單點(diǎn)有向路徑哥捕。給定一幅有向圖和一個(gè)起點(diǎn)s牧抽，回答“從s到給定目的頂點(diǎn)v是否存在一條有向路徑嘉熊？如果有遥赚，找出這條路徑”等類似問題
單點(diǎn)最短有向路徑。給定一幅有向圖和一個(gè)起點(diǎn)s阐肤，回答“從s到給定目的頂點(diǎn)v是否存在一條有向路徑凫佛？如果有找到其中最短的那條（所含邊數(shù)最少）”等類似問題讲坎。
/**
* 有向圖的深度優(yōu)先搜索路徑
*/
class DepthFirstDirectedPaths {
private boolean[] marked; //標(biāo)記是否被訪問過
private int[] edgeTo; //一直頂點(diǎn)的路徑上的最后一個(gè)頂點(diǎn)
private final int s; //起點(diǎn)
public DepthFirstDirectedPaths(Digraph g, int s) {
this.s = s;
marked = new boolean[g.getV()];
edgeTo = new int[g.getV()];
dfs(g, s);
}
private void dfs(Digraph g, int v) {
marked[v] = true;
for (int w : g.adj(v)) {
if (!marked[v]) {
edgeTo[w] = v;
dfs(g, w);
}
}
}
private boolean hasPathTo(int v) {
return marked[v];
}
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<Integer> stack = new Stack<>();
for (int x = v; v != s; x = edgeTo[x]) {
stack.push(x);
}
stack.push(s);
return stack;
}
}
/**
* 有向圖的廣度優(yōu)先搜索路徑
*/
class BreadthFirstDirectedPaths {
private boolean[] marked; //標(biāo)記是否被訪問過
private int[] edgeTo; //一直頂點(diǎn)的路徑上的最后一個(gè)頂點(diǎn)
private final int s; //起點(diǎn)
public BreadthFirstDirectedPaths(Digraph g, int s) {
this.s = s;
marked = new boolean[g.getV()];
edgeTo = new int[g.getV()];
bfs(g, s);
}
private void bfs(Digraph g, int v) {
marked[v] = true;
Deque<Integer> stack = new ArrayDeque<>();
stack.offer(v);
while (!stack.isEmpty()) {
int t = stack.poll();
for (int w : g.adj(t)) {
if (!marked[w]) {
marked[w] = true;
edgeTo[w] = t;
stack.offer(w);
}
}
}
}
private boolean hasPathTo(int v) {
return marked[v];
}
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<Integer> stack = new Stack<>();
for (int x = v; v != s; x = edgeTo[x]) {
stack.push(x);
}
stack.push(s);
return stack;
}
}
4.2.4環(huán)和有向無環(huán)圖
從原則上來說，一幅有向圖可能含有大量的環(huán)愧薛；在實(shí)際應(yīng)用中晨炕，我們一般只會(huì)重點(diǎn)關(guān)注其中一小部分，或者只是想知道它們是否存在
尋找有向環(huán)
基于深度優(yōu)先搜索的來解決這個(gè)問題并不困難毫炉，系統(tǒng)維護(hù)的遞歸調(diào)用的棧正是“當(dāng)前”正在遍歷的有向路徑瓮栗。一旦我們找到了一條有向邊v->w且w已經(jīng)存在于棧中，就找到了一個(gè)環(huán)瞄勾，因?yàn)闂１硎镜氖且粭l由w到v的有向路徑费奸，而v->w正好補(bǔ)全了這個(gè)環(huán)。同時(shí)进陡，如果沒有找到這樣的邊愿阐，說明有向圖是無環(huán)的。
/**
* 尋找有向環(huán)
* 如果存在多個(gè)有向環(huán),則只找到一個(gè)有向環(huán)
*/
public class DirectedCycle {
private boolean[] marked;
private int[] edgeTo;
private Stack<Integer> cycle; //有向環(huán)中的所有頂點(diǎn)
private boolean[] onStack; //遞歸調(diào)用的棧上的所有頂點(diǎn)
public DirectedCycle(Digraph g) {
marked = new boolean[g.getV()];
edgeTo = new int[g.getV()];
onStack = new boolean[g.getV()];
for (int v = 0; v < g.getV(); v++) {
if (!marked[v])
dfs(g, v);
}
}
private void dfs(Digraph g, int v) {
marked[v] = true;
onStack[v] = true;
for (int w : g.adj(v)) {
if (hasCycle()) return;
else if (!marked[w]) {
edgeTo[w] = v;
dfs(g, w);
} else if (onStack[w]) {
cycle = new Stack<Integer>();
for (int x = v; x != w; x = edgeTo[w]) {
cycle.push(x);
}
cycle.push(w);
cycle.push(v);
}
}
onStack[v] = false;
}
public boolean hasCycle() {
return cycle != null;
}
public Iterable<Integer> cycle() {
return cycle;
}
}
該類為標(biāo)準(zhǔn)的遞歸bfs()方法添加了一個(gè)布爾類型的數(shù)組onStack[]來保存遞歸調(diào)用期間棧上的所有頂點(diǎn)趾疚。當(dāng)它找到一條邊v->w且w在棧中的時(shí)候缨历，就找到了一個(gè)有向環(huán)。環(huán)上的所有頂點(diǎn)可以通過edgeTo[]來得到糙麦。
同樣辛孵，需要指出的是，廣度優(yōu)先搜索也可以找到是否有環(huán)喳资，這個(gè)問題我們放到后面拓?fù)渑判虻臅r(shí)候用例題討論觉吭。
4.2.4.3 頂點(diǎn)的深度優(yōu)先次序與拓?fù)渑判?/h4>
![]()
image-20200728151416010.png
實(shí)際上我們已經(jīng)見過一種拓?fù)渑判虻乃惴ǎ褐灰砑右恍写a，深度標(biāo)準(zhǔn)優(yōu)先搜索程序就能完成這項(xiàng)任務(wù)仆邓。
如果將dfs()的參數(shù)頂點(diǎn)保存在一個(gè)數(shù)據(jù)結(jié)構(gòu)中鲜滩，遍歷這個(gè)數(shù)據(jù)結(jié)構(gòu)實(shí)際上就能訪問圖中的所有頂點(diǎn)，遍歷的順序取決于這個(gè)數(shù)據(jù)結(jié)構(gòu)的性質(zhì)以及是在遞歸調(diào)用之前還是之后保存节值。典型的應(yīng)用中徙硅，人們感興趣的是頂點(diǎn)的以下3中排列順序。
- 前序：在遞歸調(diào)用之前將頂點(diǎn)加入隊(duì)列搞疗。
- 后序：在遞歸調(diào)用之后將頂點(diǎn)加入隊(duì)列嗓蘑。
- 逆后序：在遞歸調(diào)用之后將頂點(diǎn)壓入棧。
有向圖中基于深度優(yōu)先搜索的頂點(diǎn)排序
public class DepthFirstOrder {
private boolean[] marked;
private Queue<Integer> pre; //所有頂點(diǎn)的前序排列
private Queue<Integer> post; //所有頂點(diǎn)的后序排列
private Stack<Integer> reversePost; //所有頂點(diǎn)的逆后序排列
public DepthFirstOrder(Digraph g) {
marked = new boolean[g.getV()];
pre = new ArrayDeque<>();
post = new ArrayDeque<>();
reversePost = new Stack<>();
for (int v = 0; v < g.getV(); v++) {
if (!marked[v]) dfs(g, v);
}
}
private void dfs(Digraph g, int v) {
marked[v] = true;
pre.add(v);
for (int w : g.adj(v)) {
if (!marked[w])
dfs(g, w);
}
post.add(v);
reversePost.push(v);
}
public Iterable<Integer> pre() {
return pre;
}
public Iterable<Integer> post() {
return post;
}
public Iterable<Integer> reversePost() {
return reversePost;
}
}
拓?fù)渑判?/strong>
public class Topological {
private Iterable<Integer> order; //頂點(diǎn)的拓?fù)渑判?
public Topological(Digraph g) {
DirectedCycle cycleFinder = new DirectedCycle(g);
if (!cycleFinder.hasCycle()) {
//先判斷是否有環(huán)匿乃，有環(huán)的話不能進(jìn)行拓?fù)渑判? DepthFirstOrder dfs = new DepthFirstOrder(g);
order = dfs.reversePost();
}
}
public Iterable<Integer> order() {
return order;
}
public boolean isDAG() {
return order != null;
}
}
一副有向圖的拓?fù)漤樞蚣礊樗许旤c(diǎn)的逆后序排列桩皿。
證明。對(duì)于任意邊v->w幢炸，在調(diào)用dfs(v)的時(shí)候泄隔，有以下三種情況必成立
1.dfs(w)已經(jīng)被調(diào)用過且已經(jīng)返回了(w已經(jīng)被標(biāo)記)
2.dfs(w)還沒有被調(diào)用過(w還未被標(biāo)記)，因此v->w會(huì)直接或間接調(diào)用并返回dfs(w),且dfs(w)會(huì)在dfs(v)返回前返回宛徊。
3.dfs(w)已經(jīng)調(diào)用還未被返回佛嬉。證明的關(guān)鍵在于逻澳，在有向無環(huán)圖中這種情況是不可能的，由于遞歸調(diào)用鏈意味著存在從w到v的路徑暖呕，但存在v->w表示存在一個(gè)環(huán)斜做。
在兩種可能的情況中，dfs(w)都會(huì)在dfs(v)之前完成湾揽，因此在后序排列中w在v之前而在逆后序中v在w之前瓤逼。因此任意一條邊v->w都如我們所愿地從排名較前頂點(diǎn)指向排名較后的頂點(diǎn)。
在實(shí)際應(yīng)用中库物，拓?fù)渑判蚝陀邢颦h(huán)的檢測(cè)總會(huì)在一起出現(xiàn)抛姑，因?yàn)橛邢颦h(huán)的檢測(cè)是排序的前提。
實(shí)際應(yīng)用一下
LeetCode題目:
4.2.5有向圖的強(qiáng)連通性
定義艳狐。如果兩個(gè)頂點(diǎn)v和w是互相可達(dá)的定硝，則稱它們?yōu)?strong>強(qiáng)連通的。也就是說毫目，既存在一條從v到w的有向路徑蔬啡，也存在一條從w到v的有向路徑。如果一幅有向圖的任意兩個(gè)頂點(diǎn)都是強(qiáng)連通的镀虐，則稱這幅有向圖也是強(qiáng)連通的箱蟆。
4.2.5.1強(qiáng)連通分量
Kosaraju算法
算法完成了以下幾點(diǎn)：
- 在給定的一幅有向圖G中，使用DepthFirstOrder來計(jì)算它的反向圖GR的逆后序排列刮便。
- 在G中進(jìn)行標(biāo)準(zhǔn)的深度優(yōu)先搜索空猜，但是要按照剛才得到的順序而非標(biāo)準(zhǔn)的順序來訪問所有未被標(biāo)記的頂點(diǎn)。
- 在構(gòu)造函數(shù)中恨旱，所有在同一個(gè)遞歸dfs()調(diào)用訪問道德頂點(diǎn)都在同一個(gè)強(qiáng)連通分量中
public class KosarajuSCC {
private boolean[] marked; //已經(jīng)訪問過的頂點(diǎn)
private int[] id; //強(qiáng)連通分量的標(biāo)識(shí)符
private int count; //強(qiáng)連通分量個(gè)數(shù)
public KosarajuSCC(Digraph digraph) {
marked = new boolean[digraph.getV()];
id = new int[digraph.getV()];
DepthFirstOrder order = new DepthFirstOrder(digraph.reverse());
for(int v:order.reversePost())
{
if(!marked[v])
dfs(digraph,v);
}
}
private void dfs(Digraph digraph, int s) {
marked[s] = true;
id[s] = count;
for (int w : digraph.adj(s)) {
if (!marked[w])
dfs(digraph, w);
}
}
public int getCount() {
return count;
}
public boolean stronglyConnected(int v, int w) {
return id[v] == id[w];
}
}
命題辈毯。使用深度優(yōu)先搜索查找給定有向圖G的反向圖GR，根據(jù)由此得到的所有頂點(diǎn)的逆后序再次使用深度優(yōu)先搜索處理有向圖搜贤，其構(gòu)造函數(shù)每次遞歸調(diào)用所標(biāo)記的頂點(diǎn)都在同一個(gè)強(qiáng)連通分量中谆沃。
證明。首先用反證法證明“每個(gè)和s強(qiáng)連通的頂點(diǎn)v都會(huì)在構(gòu)造函數(shù)調(diào)用的dfs(G,s)中訪問到”仪芒。假設(shè)有一個(gè)和s強(qiáng)連通的頂點(diǎn)v不會(huì)在構(gòu)造函數(shù)調(diào)用的dfs(G,s)中訪問到唁影。因?yàn)榇嬖趶膕到v的路徑，所以v肯定在之前就已經(jīng)被標(biāo)記過了掂名。但是据沈，因?yàn)橐泊嬖趶膙到s的路徑，在dfs(G,v)調(diào)用中s肯定會(huì)被標(biāo)記饺蔑，因此構(gòu)造函數(shù)不會(huì)調(diào)用dfs(G,s),矛盾锌介。
其次，證明“構(gòu)造函數(shù)調(diào)用的dfs(G,s)所到達(dá)的任意頂點(diǎn)v都必然和s強(qiáng)連通“膀钠。
設(shè)v為dfs(G,s)到達(dá)的某個(gè)頂點(diǎn)掏湾。那么,G必然存在一條s到v的路徑，只需要證明G中還存在一條從v到s的路徑即可肿嘲。這也等價(jià)于GR中存在一條從s到v的路徑融击，只需要證明在GR中存在一條從s到v的路徑即可。
證明的核心在于雳窟，按照逆后序進(jìn)行深度優(yōu)先搜索與為這尊浪，在GR中進(jìn)行的深度優(yōu)先搜索中，dfs(G,v)必然在dfs(G,s)之前就已經(jīng)結(jié)束了封救，這樣dfs(G,v)的調(diào)用出現(xiàn)兩種情況
1.調(diào)用在dfs(G,s)調(diào)用之前（并且在dfs(G,s)）調(diào)用之前結(jié)束
2.調(diào)用在dfs(G,s)調(diào)用之后（并且在dfs(G,s)）調(diào)用之前結(jié)束
第一種情況是不可能出現(xiàn)的拇涤，因?yàn)樵贕R中存在一條從v到s的路徑；而第二種情況說明GR中存在一條從s到v的路徑誉结。
