- 表示無向圖的資料結構
- 鄰接表陣列
- 深度優先搜索
- 深度優先搜索尋找路徑
- 深度優先搜索的性能特點
- 廣度優先搜索
- 兩種搜索方式的對比
圖表示由相連的結點所表示的抽象模型，這個模型可以用來研究類似“能否從某個點到達指定的另一個點”、“有多少個結點和指定的結點相連”、“兩個結點之間最短的連接是哪一條”，圖的演算法與很多實際問題相關，比如地圖、搜索引擎、電路、任務調度、商業交易、計算機網路、社交網路等，
無向圖是一種最簡單、最基本的圖模型，僅僅由一組頂點和一組能夠將兩個頂點相連的邊組成，
在圖的實作中，用從0開始的整數值來表示圖的結點，用類似8-5來表示連接結點8和5的邊，在無向圖中，這與5-8表示的是同一條邊，4-6-3-9表示的是4到9之間的一條路徑，
表示無向圖的資料結構
無向圖的API
public class Graph{
Graph(int V) //創建一個含有V個頂點但不含有邊的圖
Graph(In in) //從標準輸入流in讀入一幅圖
int v() //頂點數
int E() //邊數
void addEdge(int v， int w) //向圖中添加一條邊v-w
Iterable<Integer>adj(intv) //和相鄰的所有頂點
String toString() //物件的字串表示
}
第二個建構式接受的輸入由2*E+2個整陣列成，前兩行分別是V和E，表示圖中頂點和邊的數量，接下來每行都是一對互相連接的頂點，
鄰接表陣列
可以選擇鄰接表陣列作為實作Graph的資料結構，它將每個頂點的所有相鄰頂點都保存在一張鏈表中，讀取tingG后構造的鄰接表陣列如圖所示：
代碼實作：
public class Graph {
private final int V; // vertex
private int E; // edge
private Bag<Integer>[] adj;
public Graph(int V) {
this.V = V;
this.E = 0;
adj = (Bag<Integer>[]) new Bag[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag<Integer>();
}
}
public Graph(In in) {
this(in.readInt());
int E = in.readInt();
for (int i = 0; i < E; i++) {
int v = in.readInt();
int w = in.readInt();
addEdge(v, w);
}
}
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
E++;
}
public Iterable<Integer> adj(int v) {
return adj[v];
}
}
用陣列adj[]來表示圖的頂點，可以快速訪問給定頂點的鄰接頂點串列；用Bag資料型別來存盤一個頂點的所有鄰接頂點，可以保證在常數時間內添加新的邊或者遍歷任意頂點的鄰接頂點，要添加比如5-8這條邊時，addEdge方法除了會把8添加到5的鄰接表中，還會把5添加到8的鄰接表，
這種實作的性能特點為:
- 使用的空間和V+E成正比
- 添加一條邊所需的時間為常數
- 遍歷頂點一個頂點的相鄰頂點所需的時間和這個頂點的度數成正比（頂點的度數表示與這個頂點相連的邊數）
深度優先搜索
深度優先搜索是一種遍歷圖的方式，這種演算法的軌跡與走迷宮非常類似，可以將迷宮作為圖，迷宮的通道作為圖的邊，迷宮的路口作為圖的點，迷宮可認為是一種直觀的圖，探索迷宮的一種方法叫做Tremaux搜索，這種方法的具體做法是，選擇一條沒有標記過的通道，在走過的路上鋪一條繩子；標記所有第一次經過的路口和通道；當來到第一個標記過的路口時，回退到上一個路口；當回退的路口已沒有可走的通道時繼續回退，
這樣，最終可以找到一條出路，而且不會多次經過同一通道或者路口，
深度優先搜索的代碼實作與走迷宮類似：
public class DepthFirstSearch {
private boolean[] marked;
private int count;
private final int s;
public DepthFirstSearch(Graph G, int s) {
marked = new boolean[G.V()];
this.s = s;
dfs(G, s);
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
dfs(G, w);
}
}
}
public boolean marked(int w) {
return marked[w];
}
public int count() {
return count;
}
}
這段代碼會搜索出所有與頂點s相鄰的點，中dfs()方法的遞回呼叫機制以及marked陣列對應迷宮中的繩子的作用，當已經處理完一個頂點的所有相鄰頂點后，遞回會結束，演算法在運行的時候，總是會沿著一個頂點的第一個相鄰頂點不斷深入，直到遇到一個在marked陣列已經標記的頂點，才逐層退出遞回，這也是深度優先搜索名稱的由來，最終搜索的結果存盤在marked陣列中，標記為true的位對應的索引就是與頂點s相連的點，
深度優先搜索尋找路徑
深度優先搜索可以解決路徑檢測問題，即回答“兩個給定的頂點之間是否存在一條路徑？”，但如果想找出這條路徑呢？要回答這個問題，只需要對上面的代碼稍作擴展：
public class DepthFirstPaths {
private boolean[] marked;
private int[] edgeTo; //新增的，用于記錄路徑
private final int s;
public DepthFirstPaths(Graph G, int s) {
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
dfs(G, s);
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v; //記錄路徑
dfs(G, w);
}
}
}
public boolean marked(int w) {
return marked[w];
}
public int count() {
return count;
}
public boolean hasPathTo(int v) { //判斷是否存在從s到v的路徑
return marked(v);
}
public Iterable<Integer> pathTo(int v) { //獲取從s到v的路徑，不存在則回傳null
if (!hasPathTo(v))
return null;
Stack<Integer> path = new Stack<Integer>();
for (int x = v; x != s; x = edgeTo[x]) {
path.push(x);
}
path.push(s);
return path;
}
public static void main(String[] args) {
In in = new In(args[0]);
Graph G = new Graph(in);
int s = Integer.parseInt(args[1]);
DepthFirstPaths search = new DepthFirstPaths(G, s);
//
for (int v = 0; v < G.V(); v++) {
StdOut.print(s+" to "+v+": ");
if(search.hasPathTo(v)){
for(int x:search.pathTo(v)){
if(x==s) StdOut.print(x);
else StdOut.print("-"+x);
}
}
StdOut.println();
}
}
}
這段代碼添加了edgeTo[]整形陣列來起到Tremaux搜索中繩子的作用，每次由邊v-w第一次訪問w時，會將edgeTo[w]設為v，最終edgeTo陣列是一顆以起點為根節點的樹，記錄了由任意連通的結點回到根節點的路徑，
下圖為由一副圖生成的edgeTo的內容，及路徑樹的結構的示例：
這與代碼運行結果是一致的：
java DepthFirstPaths tinyCG.txt 0
0 to 0：0
0 to 1：0-2-1
0 to 2：0-2
0 to 3：0-2-3
0 to 4：0-2-3-4
0 to 5：0-2-3-5
深度優先搜索的性能特點
深度優先搜索標記與起點連通的所有頂點所需的時間與頂點的度數之和成正比，
使用深度優先搜索得到從給定起點到任意標記頂點的路徑所需的時間與路徑的長度成正比，
廣度優先搜索
深度優先搜索得到的路徑不僅與圖的結構有關，還受圖的表示的影響，鄰接表中頂點的順序不同，得到的路徑也會不同，所以當需要計算兩點間的最短路徑(單點最短路徑)時，就無法依賴深度優先搜索了，而廣度優先搜索可以解決單點最短路徑問題，
要找到從s到v的最短路徑，從s開始，在所有由一條邊就可以到達的頂點中尋找v，如果找不到就繼續在于s距離兩條邊的頂點中查找，如此一直進行，
public class BreadthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private final int s;
public BreadthFirstPaths(Graph G, int s) {
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
bfs(G, s);
}
private void bfs(Graph G, int s) {
Queue<Integer> queue = new Queue<Integer>();
marked[s] = true;
queue.enqueue(s);
while (!queue.isEmpty()) {
int v = queue.dequeue();
for (int w : G.adj(v)) {
if(!marked[w]){
edgeTo[w]=v;
marked[w]=true;
queue.enqueue(w);
}
}
}
}
public boolean hasPathTo(int v){
return marked[v];
}
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v))
return null;
Stack<Integer> path = new Stack<Integer>();
for (int a = v; a != s; a = edgeTo[a]) {
path.push(a);
}
path.push(s);
return path;
}
// cmd /c --% java algs4.four.BreadthFirstPaths ..\..\..\algs4-data\tinyCG.txt 0
public static void main(String[] args) {
In in = new In(args[0]);
int s = Integer.parseInt(args[1]);
Graph g = new Graph(in);
BreadthFirstPaths search = new BreadthFirstPaths(g, s);
for (int i = 0; i < g.V(); i++) {
StdOut.print(i + ":");
Iterable<Integer> path = search.pathTo(i);
for (Integer p : path) {
if (search.s != p) {
StdOut.print("-" + p);
} else {
StdOut.print(p);
}
}
StdOut.println();
}
}
}
方法bfs中定義了一個佇列來保存所有已經被標記過但其鄰接表還未被檢查過的頂點，先將起點加入佇列，然后重復以下步驟直到佇列為空：
- 取佇列中的下一個頂點v并標記它
- 將與v相鄰的所有未被標記過的頂點加入佇列，
佇列先進先出(FIFO)的特性可以達到廣度優先搜索尋找距離逐漸增大的效果，在深度優先搜索中，實際上隱式地使用了一個遵循后進先出(LIFO)規則的堆疊，在dfs的遞回呼叫的程序中，這個堆疊由系統管理，
兩種搜索方式的對比
不管是深度優先還是廣度優先搜索演算法，它們都會先將起點存入資料結構中，然后重復以下步驟直到資料結構被清空：
- 取其中的下一個頂點v并標記它
- 將與v相鄰而又未被標記過的頂點加入資料結構中
兩種演算法的區別在于從資料結構中獲取下一個頂點的規則，深度優先搜索會首先取最晚加入資料結構的頂點，而廣度優先搜索取得則是最早加入的頂點，這種規則的區別會影響搜索圖的路徑，深度優先搜索會不斷深入圖中，并在堆疊中保存了所有分叉的頂點，廣度優先搜索則像扇面一般掃描圖，用一個佇列保存訪問過的最前段的頂點，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/121137.html
標籤：其他
下一篇：分治法之棋盤覆寫