圖論基礎(chǔ)（Graph Theory）
圖是由結(jié)點（Vertex）和邊（Edge）組成的抽象的數(shù)據(jù)結(jié)構(gòu)。結(jié)點和結(jié)點之間靠邊連接起來。
圖的分類 1
1、無向圖（Undirected Graph），是我們主要研究的部分，我們可以把無向圖看成一種特殊的有向圖;
2、有向圖（Directed Graph），有向圖具有不對稱的特性。
圖的分類 2
1、無權(quán)圖（Unweighted Graph）
2、有權(quán)圖（Weighted Graph）
理解圖的連通性。
上面這張圖，它的連通分量為 。
簡單圖（Simple Graph）：無自環(huán)邊（self-loop），并且無平行邊的圖（parallel-edges）。
我們的學(xué)習(xí)將從簡單圖開始。
圖的表示
本章僅介紹無權(quán)圖。圖這種數(shù)據(jù)結(jié)構(gòu)可以使用“鄰接矩陣”和“鄰接表”來表示。
鄰接矩陣
無向圖的鄰接矩陣表示是一個對稱矩陣。
鄰接表
稀疏圖與稠密圖
鄰接表適合表示稀疏圖（Sparse Graph），邊較少。
鄰接矩陣適合表示稠密圖（Dense Graph），邊較多。
我們的圖是實現(xiàn)了如下接口的 Java 類。
Java 代碼：
// 圖的接口，統(tǒng)一表示稀疏圖與稠密圖
public interface Graph {
// 返回頂點的個數(shù)
int V();
// 返回邊的條數(shù)
int E();
// 在頂點 v 和 w 之間添加一條表
void addEdge(int v, int w);
// 頂點 v 與 頂點 w 是否有邊連接
boolean hasEdge(int v, int w);
// 顯示這個圖中的元素
void show();
// 得到頂點 v 的所有鄰居頂點
Iterable<Integer> adj(int v);
}
編寫相鄰結(jié)點迭代器
為了方便遍歷一個點的所有鄰居結(jié)點，我們需要實現(xiàn)一個迭代器。
稀疏圖（鄰接表）的相鄰點迭代器
由稀疏圖（鄰接表）的表示決定了返回一個結(jié)點的所有相鄰結(jié)點是十分容易的。
Java 代碼：
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
return g[v];
}
稠密圖（鄰接矩陣）的相鄰點迭代器
由稠密圖（鄰接矩陣）得到一個結(jié)點的所有相鄰結(jié)點只須遍歷鄰接矩陣中的一行，把值為 True 的所有頂點拿到即可。
Java 代碼：
public Iterable<Integer> adj(int v){
assert v >= 0 && v < n;
Vector<Integer> adjV = new Vector<>();
for (int i = 0; i < n; i++) {
if(g[v][i]){
adjV.add(i);
}
}
return adjV;
}
我們將圖的數(shù)據(jù)以一定格式保存在一個文件中，因此我們要編寫一個工具類讀這個圖文件。
從一個文件讀出一個圖
我們圖的信息存在一個文件中，然后通過讀取這個文件的內(nèi)容得到圖的頂點和邊的信息，為此我們編寫了如下代碼。
編寫一個讀圖的工具類
例1：文件 testG1.txt 的內(nèi)容如下，其中第 1 行的第 1 個數(shù)表示這張圖有多少個頂點，第 2 個數(shù)表示這張圖有多少條邊。
第 2 行直至最后一行表示的是所有的邊，以兩個頂點來表示一條邊。
13,13
0,5
4,3
0,1
9,12
6,4
5,4
0,2
11,12
9,10
0,6
7,8
9,11
5,3
如果它表示一個無向圖，那么畫出來就是：
用鄰接表表示是這樣的：
用鄰接矩陣表示是這樣的：
深度優(yōu)先遍歷與圖的連通分量
和二分搜索樹的遍歷一樣，圖的遍歷也可以分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷。
圖的深度優(yōu)先遍歷
從圖中任意一個結(jié)點開始，遍歷它的相鄰結(jié)點，只要這個相鄰的結(jié)點還有相鄰的結(jié)點就繼續(xù)遍歷，遍歷完成以后才返回。深度優(yōu)先遍歷可以使用遞歸來完成。
遞歸到底的情形在編碼的時候不容易發(fā)現(xiàn)，其實就是在所有的結(jié)點都被遍歷完成的時候，就是遞歸到底、方法應(yīng)該返回的時候。
實現(xiàn)深度優(yōu)先遍歷有兩個關(guān)鍵點：
從一個頂點開始不停地向下試，直到試不下去了為止；
圖和樹不一樣的，樹到了葉子結(jié)點就走不下去了，在圖中要記錄每一個結(jié)點是否被遍歷過。
圖的深度優(yōu)先遍歷的應(yīng)用
應(yīng)用1：計算圖的連通分量；
Java 代碼：經(jīng)過一次深度優(yōu)先遍歷得到連通分量
public class Component {
private Graph graph;
private boolean[] visited;
// 連通分量的個數(shù)，同時可以在遍歷的過程中，為各個連通分量所在的集合進行標記
private int ccount;
private void dfs(int i) {
// 記錄是否被訪問過，這個非常關(guān)鍵，深度遍歷一開始就要記錄這些結(jié)點被訪問過
visited[i] = true;
Iterable<Integer> adj = graph.adj(i);
for(Integer v:adj){
if(!visited[v]){
dfs(v);
}
}
}
// 構(gòu)造方法，通過傳入一個圖，經(jīng)過了深度優(yōu)先遍歷，計算無權(quán)圖的連通分量
public Component(Graph graph) {
this.graph = graph;
int vCount = graph.V(); // 圖中頂點的個數(shù)
// 可以不用顯式賦值，因為默認就是 false
visited = new boolean[vCount];
for (int i = 0; i < vCount; i++) {
if (!visited[i]){// 如果沒有遍歷過，就進行一次深度優(yōu)先遍歷
// depth first search 深度優(yōu)先遍歷
// 注意：深度優(yōu)先遍歷，不是遍歷這個結(jié)點的所有鄰居
// 而是把所有與該點向量的所有結(jié)點都遍歷一遍
dfs(i);
ccount++; // 經(jīng)過了一次深度優(yōu)先遍歷以后，連通分量 +1
}
}
}
// 返回這個圖的連通分量的個數(shù)
public int getCcount() {
return ccount;
}
}
- 應(yīng)用2：通過計算圖的連通分量，還可以很快地判斷出兩個結(jié)點是否相連。
在計算連通分量的同時，給每一個頂點編號，編號的規(guī)則是：屬于一個連通分量的應(yīng)該編號一樣。在上面的代碼中，在每一次記錄頂點 i 被訪問過以后 visited[i] = true;，馬上給這個頂點編號，編號就用到此時得到的連通分量的最大值。通過給每個頂點標記，我們就能很輕松地實現(xiàn)查詢頂點是否相連，只需要查詢它們的連通分量的組別就行了。
Java 代碼：
public class Component {
private Graph graph;
private boolean[] visited;
private int[] id;
private int ccount;
private void dfs(int i) {
visited[i] = true;
// 在計算連通分量的同時，給每一個頂點編號，編號的規(guī)則是：屬于一個連通分量的應(yīng)該編號一樣。
id[i] = ccount;
Iterable<Integer> adj = graph.adj(i);
for (Integer v : adj) {
if (!visited[v]) {
dfs(v);
}
}
}
public Component(Graph graph) {
this.graph = graph;
int vCount = graph.V();
visited = new boolean[vCount];
id = new int[vCount];
for (int i = 0; i < vCount; i++) {
visited[i] = false;
id[i] = -1;
}
for (int i = 0; i < vCount; i++) {
if (!visited[i]){
dfs(i);
ccount++;
}
}
}
public int getCcount() {
return ccount;
}
public boolean isConnected(int v, int w) {
assert v >= 0 && v < graph.V();
assert w >= 0 && w < graph.V();
return id[v] == id[w];
}
}
尋路算法
在進行深度優(yōu)先遍歷的過程中形成了一條路徑，我們這一節(jié)的目標是得到這條路徑，但我們要知道，使用深度優(yōu)先遍歷并不能保證這條路徑是最短的。
尋路算法是一個常見的算法，實現(xiàn)起來也很簡單：在每一次遍歷的時候，我們都記錄一下，這一次遍歷從何而來。
使用深度優(yōu)先遍歷獲得兩點之間的一條路徑
Java 代碼：
import java.util.Stack;
import java.util.Vector;
// 尋路算法，只能得到無權(quán)圖的一條路徑，該路徑并不是最短路徑
// 該算法對有向圖依然有效
public class Path {
private Graph graph;
private boolean[] visited;
private int[] from;
private void dfs(Integer v) {
visited[v] = true;
Iterable<Integer> adj = graph.adj(v);
for (Integer i : adj) {
if (!visited[i]) {
from[i] = v;
dfs(i);
}
}
}
public Path(Graph graph, int s) {
assert s >= 0 && s < graph.V();
this.graph = graph;
int vCount = graph.V();
visited = new boolean[vCount];
from = new int[vCount];
for (int i = 0; i < vCount; i++) {
visited[i] = false;
from[i] = -1;
}
// 從 source 開始，做一次深度優(yōu)先遍歷
dfs(s);
}
// 查詢從 s 點到 w 點是否有路徑
public boolean hasPath(int w) {
assert w >= 0 && w < graph.V();
return visited[w];
}
// 得到從 s 到 w 的一條路徑
public void path(int w, Vector<Integer> vec) {
assert hasPath(w);
// 我們要倒著把路徑得到，所以應(yīng)該借助棧來完成該工作
Stack<Integer> stack = new Stack<>();
// 這一段邏輯比較繞，但不難
int p = w;
while (p != -1) {
stack.add(p);
p = from[p];
}
while (!stack.isEmpty()) {
vec.add(stack.pop());
}
}
// 顯示從 s 到 w 的一條路徑
public void showPath(int w) {
Vector<Integer> vec = new Vector<>();
path(w, vec);
for (int i = 0; i < vec.size(); i++) {
System.out.print(vec.get(i));
if (i == vec.size() - 1) {
System.out.println();
} else {
System.out.print(" -> ");
}
}
}
}
- [ ] 練習(xí) 1 ：檢查有向圖中是否有環(huán)。
- [ ] 練習(xí) 2 ：檢查有向圖是否是二分圖。
10.7 圖的廣度優(yōu)先遍歷和無權(quán)圖的最短路徑
- 和樹的廣度優(yōu)先遍歷是一致，使用隊列作為輔助的數(shù)據(jù)結(jié)構(gòu)；
-
visited數(shù)組應(yīng)該是對加入到隊列中的元素進行處理，因為它加入到隊列了，早晚都會被處理； - 先遍歷到的結(jié)點比后遍歷到結(jié)點距離起始結(jié)點更近，所以可以解決最短路徑的問題；
- 針對無向圖和有向圖都有效。
10.7.1 圖的廣度優(yōu)先遍歷可以回答的問題
Java 代碼：
import java.util.*;
public class ShortestPath {
private Graph graph;
private int s; // source
private boolean[] visited;
private int[] from; // 記錄了從哪個結(jié)點訪問而來
private int[] ord; // 記錄了層序
public ShortestPath(Graph graph, int s) {
this.graph = graph;
assert s >= 0 && s < graph.V();
visited = new boolean[graph.V()];
from = new int[graph.V()];
ord = new int[graph.V()];
for (int i = 0; i < graph.V(); i++) {
visited[i] = false;
from[i] = -1;
ord[i] = -1;
}
this.s = s;
// 特別要注意：使用鏈表作為隊列的時候，出隊和入隊不能混淆
// 如果入隊的方向是從右到左，出隊也是從右到左
// 如果入隊的方向是從左到右，出隊也是從左到右
LinkedList<Integer> queue = new LinkedList<>();
queue.push(s);
visited[s] = true;
ord[s] = 0;
while (!queue.isEmpty()) {
// peek 的意思是：我只是瞅了一眼，并沒有真的把它拿出來
int v = queue.pollLast();
for (Integer i : graph.adj(v)) {
if (!visited[i]) {
// 注意：LinkedList 有 push 和 add 兩種方法
// 這一點區(qū)別是我在使用測試用例的過程中發(fā)現(xiàn)了錯誤，使用 IDEA 的 debug 調(diào)試代碼的過程中發(fā)現(xiàn)的
// push 的源代碼點開，你會看到 addFirst
// add 的源代碼點開，你會看到 linkLast
queue.push(i);
visited[i] = true;
from[i] = v;
ord[i] = ord[v] + 1;
}
}
}
}
// 圖的廣度優(yōu)先遍歷可以回答的問題 1 : 判斷到結(jié)點 w 是否有路徑
public boolean hasPath(int w) {
assert w >= 0 && w < graph.V();
return visited[w];
}
// 圖的廣度優(yōu)先遍歷可以回答的問題 2 ：打印從 s 到 w 的最短路徑
public void showPath(int w) {
assert hasPath(w);
List<Integer> paths = path(w);
for (int i = 0; i < paths.size(); i++) {
if (i == paths.size() - 1) {
System.out.println(paths.get(i));
} else {
System.out.print(paths.get(i) + " -> ");
}
}
}
// 圖的廣度優(yōu)先遍歷可以回答的問題 3 ：計算從 s 到 w 的最短路徑
public List<Integer> path(int w) {
Stack<Integer> stack = new Stack<>();
int cur = w;
while (cur != -1) {
stack.push(cur);
cur = from[cur];
}
List<Integer> ret = new ArrayList<>();
while (!stack.isEmpty()) {
ret.add(stack.pop());
}
return ret;
}
// 圖的廣度優(yōu)先遍歷可以回答的問題 4 ：查看從 s 點到 w 點的最短路徑長度，若從 s 到 w 不可達，返回 -1
public int length(int w) {
assert w >= 0 && w < graph.V();
return ord[w];
}
}
關(guān)于無權(quán)圖算法的測試：
// 關(guān)于無權(quán)圖算法的測試
public class Main {
public static void main(String[] args) {
// 稠密圖
// DenseGraph graph = new DenseGraph(13, false);
// new ReadGraphUtil(graph, "testG1.txt");
// graph.show();
// 稀疏圖
SparseGraph graph = new SparseGraph(13, false);
new ReadGraphUtil(graph, "testG1.txt");
// graph.show();
Component component = new Component(graph);
System.out.println("圖的連通分量：" + component.getCcount());
// 通過深度優(yōu)先遍歷，得到一個路徑
Path path = new Path(graph, 0);
// 此時的路徑不是最短路徑
path.showPath(6);
// 廣度優(yōu)先遍歷
ShortestPath shortestPath = new ShortestPath(graph, 0);
shortestPath.showPath(3);
}
}
本文源代碼
（本節(jié)完）
