1.1 走迷宮

簡單的迷宮，如下圖1.1-1所示：

探索迷宮而不迷路，我們需要：

• 選擇一條沒有標記過的通道，在你走過的路上鋪一條繩子；
• 標記所有你第一次路過的路口和通道；
• 當來到一個標記過的路口時（用繩子）回退到上一個路口；
• 當回退的路口已沒有可走的通道時繼續(xù)回退。

繩子可以保證總能找到一條出路，標記能保證你不會兩次經(jīng)過同一條通道或者路口。我們把上迷宮，用等價的圖來代替，如下圖1.1-2所示：

1.2 圖的深度優(yōu)先搜索實現(xiàn)

圖的遍歷算法非遞歸代碼如下：

import java.util.Map;/*** key-value pair 類* @author: Administrator* @createTime: 2023/03/04 21:49*/
public final class Entry<K, V> implements Map.Entry<K, V>{private K key;private V value;public Entry(K key, V value) {this.key = key;this.value = value;}@Overridepublic K getKey() {return key;}@Overridepublic V getValue() {return value;}@Overridepublic V setValue(V value) {V oldValue = value;this.value = value;return oldValue;}
}/**===========*/import com.gaogzhen.datastructure.stack.Stack;
import edu.princeton.cs.algs4.Graph;import java.util.Iterator;/*** 單點連通性* @author: Administrator* @createTime: 2023/03/03 19:58*/
public class DepthFirstSearch {/*** 頂點是否標記*/private boolean[] marked;/*** 與指定頂點連通的頂點總數(shù)*/private int count;/*** 圖*/private Graph graph;/*** 起點*/private int s;public DepthFirstSearch(Graph graph, int s) {this.graph = graph;this.s = s;check(s);marked = new boolean[graph.V()];dfs();}/*** 搜索圖g中與起點v連通的所有頂點*/private void dfs() {Stack<Entry<Integer, Iterator<Integer>>> path = new Stack<>();// marked[v] = true;if (!marked[s]) {marked[s] = true;count++;Iterable<Integer> iterable = graph.adj(s);Iterator<Integer> it;if (iterable != null && (it = iterable.iterator()) != null){path.push(new Entry<>(s, it));}}while (!path.isEmpty()) {Entry<Integer, Iterator<Integer>> entry = path.pop();int x;Iterator<Integer> it = entry.getValue();Integer f = entry.getKey();while (it.hasNext()) {x = it.next();if (!marked[x]) {marked[x] = true;count++;if (it.hasNext()) {path.push(entry);}Iterable<Integer> iterable = graph.adj(x);if (iterable != null && (it = iterable.iterator()) != null){path.push(new Entry<>(x, it));}break;}}}}/*** 檢測索引是否在范圍之內(nèi)* @param i 給定索引*/private void check(int i) {if (i < 0 || i > graph.V() - 1) {throw new IndexOutOfBoundsException("索引越界異常");}}/*** 判斷起點是否與給定頂點x連通* @param x 給定頂點* @return*/public boolean marked(int x) {check(x);return marked[x];}/*** 返回圖中與頂點想連通的頂點數(shù)* @return*/public int count() {return count;}}

測試代碼：

public static void testDepth() {String path = "H:\\gaogzhen\\java\\projects\\algorithm\\asserts\\maze.txt";In in = new In(path);Graph graph = new Graph(in);int s = 0;DepthFirstSearch depthFirstSearch = new DepthFirstSearch(graph, s);int t = 5;System.out.println(depthFirstSearch.marked(t));System.out.println(depthFirstSearch.count());
}
// 測試結(jié)果
true
6

1.3 算法分析及性能

知識點：

• Entry類就是一個鍵值對類，存在一對鍵值；在DepthFirstSearch中key用于存儲頂點序號，value存儲該頂點對應鄰接頂點迭代器。
• 深度優(yōu)先搜索非遞歸實現(xiàn)，主要借助棧來代替遞歸調(diào)用棧幀結(jié)構(gòu)，已節(jié)省內(nèi)存占用和提高運行效率。

算法分析：dfs()方法為該算法實現(xiàn)的主要方法，方法源代碼以給出，這里不再贅述整體流程，著重分析下以下一個關(guān)鍵問題。

• 該非遞歸dfs方法如何保證深度優(yōu)先？
  • 首先我把鍵值對Entry起點和起點對應的鄰接（連通）頂點集合迭代器壓入棧中
  • 外層循環(huán)開始
    • 彈出棧頂元素，獲取Entry的頂點及對應的鄰接頂點集合迭代器
    • 內(nèi)層循環(huán)判斷該迭代器有下一個元素即還有鄰接頂點，取出一個鄰接頂點。
      • 判斷改鄰接頂點沒有被標記過
        • 標記數(shù)組對應頂點索引標記
        • 連通頂點計數(shù)+1
        • 判斷迭代器還有元素，重新壓入棧中
        • break跳出內(nèi)層循環(huán)
  • 總結(jié)：只要鄰接頂點（更深一層的頂點）沒被標記過，標記之后同層迭代器壓入棧中，去訪問更深一層的頂點；而不是繼續(xù)訪問同層的頂點。
• 該dfs方法如果保證同層（同一個頂點的鄰接頂點）訪問全部訪問完畢且只訪問一次？
  • 每個頂點只訪問一次是標記數(shù)組marked[]索引和頂點一一對應，默認都是false未標記；標記之后不會在壓入棧中，自然不會在標記一次
  • 訪問同層元素是通過迭代器完成的，while配合迭代hasNext,next()方法保證全部訪問一邊且不會重復訪問。
• 深度優(yōu)先算法性能如何？見下面的命題及證明。
  • 這里根據(jù)上面的算法簡單分析
  • 完成循環(huán)判斷棧不為空，那么只有未被標記的頂點及其鄰接表（迭代器）會放入棧中；也就是說所有的頂點及其鄰接表都會被放入棧中且不會重復
  • 內(nèi)層判斷迭代器有元素那么所有的鄰接表會被遍歷一邊，鄰接表代表對應頂點的度數(shù)
  • 結(jié)論深度優(yōu)先搜索標記與起點連通的所有頂點所需的時間和頂點的度數(shù)之和成正比

命題A。深度優(yōu)先搜索標記與起點連通的所有頂點所需的時間和頂點的度數(shù)之和成正比。

證明：首先，我們要證明這個算法能標記所有與起點s連通的所有頂點（且不會標記其他頂點）。算法僅通過邊來尋找頂點，所以每個被標記的頂點都與s連通；反證法證明標記了所有與s連通的頂點，假設某個沒有被標記的頂點w與s連通。因為s作為起點是被標記的，由s到w的任意一條路徑中至少有一條邊連接的兩個頂點分別被標記過河沒有被標記過，例如v-x。根據(jù)算法，在標記了v后比如發(fā)現(xiàn)x，因此這樣的邊不存在。

每個頂點都只會被標記一次保證了時間上限（檢查標記的耗時和度數(shù)成正比）。

詳細搜索軌跡，可參考算法第四版341頁。

1. 4 單點連通性

連通性。給定一幅圖，回答“兩個給定的頂點是否連通”？或者圖中有多少個連通子圖等類似問題。

問題“兩個給定的頂點是否連通？”等價于“兩個給定的頂點間是否存在一條路徑？”，也可以叫做路經(jīng)檢測問題。深度優(yōu)先搜索解決了這個問題。

遞歸方法參考《算法第四版？或者書提供的jar包。

后記

如果小伙伴什么問題或者指教，歡迎交流。

?QQ:806797785

??源代碼倉庫地址：https://gitee.com/gaogzhen/algorithm

參考鏈接:

[1][美]Robert Sedgewich,[美]Kevin Wayne著;謝路云譯.算法：第4版[M].北京：人民郵電出版社，2012.10.P338-P342.