1.1 走迷宮

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

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

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

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

1.2 圖的深度優(yōu)先搜索實(shí)現(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;/*** 單點(diǎn)連通性* @author: Administrator* @createTime: 2023/03/03 19:58*/
public class DepthFirstSearch {/*** 頂點(diǎn)是否標(biāo)記*/private boolean[] marked;/*** 與指定頂點(diǎn)連通的頂點(diǎn)總數(shù)*/private int count;/*** 圖*/private Graph graph;/*** 起點(diǎn)*/private int s;public DepthFirstSearch(Graph graph, int s) {this.graph = graph;this.s = s;check(s);marked = new boolean[graph.V()];dfs();}/*** 搜索圖g中與起點(diǎn)v連通的所有頂點(diǎn)*/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("索引越界異常");}}/*** 判斷起點(diǎn)是否與給定頂點(diǎn)x連通* @param x 給定頂點(diǎn)* @return*/public boolean marked(int x) {check(x);return marked[x];}/*** 返回圖中與頂點(diǎn)想連通的頂點(diǎn)數(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 算法分析及性能

知識點(diǎn)：

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

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

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

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

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

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

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

1. 4 單點(diǎn)連通性

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

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

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

后記

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

?QQ:806797785

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

參考鏈接:

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