定義

從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)碉钠，且使每一個頂點(diǎn)僅被訪問一次，這個訪問的過程叫做圖的遍歷(Traversing Graph)。且圖的遍歷算法是一個比較基礎(chǔ)的算法帕识，前面我們介紹的有向無環(huán)圖的依賴排序（拓?fù)渑判颍┥巍㈥P(guān)鍵路徑等算法都需要基于該算法胰柑。
通常，有兩條遍歷圖的路徑：廣度優(yōu)先搜索和深度優(yōu)先搜索爬泥，且對無向圖和有向圖都適用柬讨。

另外，由于Guava中的Graph模塊已對這兩種圖的遍歷算法進(jìn)行了實現(xiàn)急灭，且其代碼是我所見過最完美的實現(xiàn)了姐浮。因此，本篇文章不打算重新實現(xiàn)一個遍歷算法葬馋，而是以Guava的實現(xiàn)為基礎(chǔ)進(jìn)行算法分析和驗證卖鲤。它的具體實現(xiàn)代碼文件為：https://github.com/google/guava/blob/master/android/guava/src/com/google/common/graph/Traverser.java

廣度優(yōu)先遍歷

也稱為廣度優(yōu)先搜索（Breadth First Search）肾扰，它類似于樹的分層遍歷算法（按樹的深度來遍歷，深度為1的節(jié)點(diǎn)蛋逾、深度為2的節(jié)點(diǎn)...）集晚。其定義如下：
假設(shè)從圖中某個頂點(diǎn)v出發(fā)，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點(diǎn)区匣，然后分別從這些鄰接點(diǎn)出發(fā)并依次訪問它們的鄰接點(diǎn)偷拔，并使“先被訪問的頂點(diǎn)鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，直到圖中所有所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到亏钩。若此時圖中尚有頂點(diǎn)未被訪問莲绰，則另選圖中一個未曾被訪問的頂點(diǎn)作起始點(diǎn)重復(fù)上述過程，直至圖中所有頂點(diǎn)均被訪問到為止姑丑。

換句話說蛤签，廣度優(yōu)先遍歷的過程是以v為起始點(diǎn)，由近至遠(yuǎn)栅哀，依次訪問和v有路徑相通且路徑長度為1,2,...的頂點(diǎn)的過程震肮。

下面演示對示例圖的廣度優(yōu)先遍歷：假設(shè)從起始點(diǎn)v1開始遍歷，首先訪問v1和v1的鄰接點(diǎn)v2和v3留拾，然后依次訪問v2的鄰接點(diǎn)v4和v5戳晌，及v3的鄰接點(diǎn)v6和v7，最后訪問v4的鄰接點(diǎn)v8痴柔。于是得到節(jié)點(diǎn)的線性遍歷順序為：v1 -> v2 -> v3 -> v4 -> v5 -> v6 -> v7 -> v8沦偎，即示例圖中紅色箭頭線為其廣度優(yōu)先遍歷順序。

廣度優(yōu)先遍歷（紅色箭頭線及序號為遍歷順序）

算法分析

從演示示例的推演中竞帽，我們可以發(fā)現(xiàn)其訪問順序恰好是一個隊列的出隊和入隊的過程：出隊的節(jié)點(diǎn)即為當(dāng)前訪問的節(jié)點(diǎn)扛施，緊接著將其所有的鄰接點(diǎn)入隊，為下次迭代時將要訪問的預(yù)備節(jié)點(diǎn)屹篓。

Guava的實現(xiàn)思路基本也是如此疙渣，下面我們看看它的實現(xiàn)方式：
首先，它定義了一個抽象的廣度優(yōu)先遍歷接口堆巧，以便有多種實現(xiàn)方式（下面它還有一個樹狀圖的遍歷優(yōu)化實現(xiàn)）妄荔，更重要的是它將遍歷的過程封裝在一個迭代器（Iterable）中返回了，僅在調(diào)用方通過next()訪問返回結(jié)果時才動態(tài)輸出其遍歷順序谍肤，個人覺得這是它實現(xiàn)的一大亮點(diǎn)啦租。這樣做的好處是，實際的調(diào)用過程并不消耗cpu時間（僅僅是new了一個特定類型的Iterator）荒揣，而是在調(diào)用完成后在使用其結(jié)果做其他運(yùn)算時（比如輸出或者將其作為其他功能的輸入等）才耗費(fèi)計算時間篷角。一般，我們通常的做法是函數(shù)完成遍歷運(yùn)算然后返回運(yùn)算結(jié)果（List<N>）系任，如果后續(xù)需要利用該結(jié)果進(jìn)行其他運(yùn)算時再循環(huán)遍歷結(jié)果集恳蹲，亦或者直接在在遍歷算法的迭代中直接處理其結(jié)果虐块，而迭代器明顯優(yōu)于這兩種做法盈滴。

廣度優(yōu)先遍歷接口定義為：

/**
 * 
 * @param startNode: 遍歷的起始節(jié)點(diǎn)
 * @return 返回一個Iterable作為節(jié)點(diǎn)的順序
 */
public abstract Iterable<N> breadthFirst(N startNode);

由于接口返回的是一個Iterable苍柏，那么它的實現(xiàn)肯定就是創(chuàng)建了一個Iterable了，然后實現(xiàn)它的iterator()接口：

@Override
public Iterable<N> breadthFirst(final N startNode) {
    /**
     * 創(chuàng)建一個匿名的Iterable隆嗅，并實現(xiàn)iterator()接口
     */
    return new Iterable<N>() {
        @Override
        public Iterator<N> iterator() {
            /**
             * 返回一個自定義的Iterator
             */
            return new BreadthFirstIterator(startNode);
        }
    };
}

該自定義迭代器BreadthFirstIterator中错忱，其主體實現(xiàn)在迭代函數(shù)next()中儡率，每迭代一次（調(diào)用next()函數(shù)一次）返回一個以廣度優(yōu)先遍歷為順序的一個節(jié)點(diǎn)：

/**
 * 聲明為private私有, 可對外隱藏其內(nèi)部實現(xiàn)，調(diào)用者僅需要
 * 知道是一個Iterator即可
 */
private final class BreadthFirstIterator extends Iterator<N> {
    //構(gòu)建節(jié)點(diǎn)順序的隊列：執(zhí)行入隊和出隊操作
    private final Queue<N> queue = new ArrayDeque<>();

    //用于記錄節(jié)點(diǎn)是否訪問標(biāo)記以清，避免重復(fù)訪問
    private final Set<N> visited = new HashSet<>();

    /**
     * 構(gòu)造函數(shù)時儿普，首先從起始點(diǎn)入隊開始
     * @param root
     */
    BreadthFirstIterator(N root) {
        queue.add(root);
        visited.add(root);
    }

    @Override
    public boolean hasNext() {
        /**
         * 當(dāng)隊列為空時，則遍歷完成玖媚，即沒有后續(xù)節(jié)點(diǎn)了箕肃。
         */
        return !queue.isEmpty();
    }

    @Override
    public N next() {
        //隊頭節(jié)點(diǎn)出隊，作為當(dāng)前迭代的訪問節(jié)點(diǎn)
        N current = queue.remove();
        /**
         * 依次將當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)入隊今魔，為下一次迭代做準(zhǔn)備
         */
        for (N neighbor : graph.successors(current)) {
            //add()返回true時（表示第一次加入，即是第一次訪問）障贸，則入隊
            if (visited.add(neighbor)) {
                queue.add(neighbor);
            }
        }
        return current;
    }
}

上面給出了廣度優(yōu)先遍歷算法的實現(xiàn)错森，下面寫一個簡單demo驗證其實現(xiàn)結(jié)果：

//構(gòu)建示例圖所示的圖結(jié)構(gòu)（無向圖）
MutableGraph<String> graph = GraphBuilder.undirected()
    .nodeOrder(ElementOrder.<String>natural()).build();

graph.putEdge(V1, V2);
graph.putEdge(V1, V3);
graph.putEdge(V2, V4);
graph.putEdge(V2, V5);
graph.putEdge(V3, V6);
graph.putEdge(V3, V7);
graph.putEdge(V4, V8);
graph.putEdge(V5, V8);
graph.putEdge(V6, V7);

//測試breadthFirst()接口，從V1開始遍歷
Iterable<String> bfs = Traverser.forGraph(graph).breadthFirst(V1);

//輸出遍歷結(jié)果: for循環(huán)（forEach）默認(rèn)實現(xiàn)iterator的遍歷next()
for (String node : iterable) {
    print(node);
}

輸出順序為：

bfs graph: {V1,V3,V2,V6,V7,V5,V4,V8}

注：雖然該順序與示例圖的紅色箭頭線標(biāo)識的順序有所不同篮洁，但仍滿足廣度優(yōu)先遍歷的順序涩维，其差異主要是在選擇當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)時 遍歷后繼節(jié)點(diǎn)的順序不同。
而該順序不同的主要原因是由于無向圖鄰接點(diǎn)（successors()返回的Set<T>結(jié)果）的存儲結(jié)構(gòu)UndirectedGraphConnections采用的是HashMap袁波，然后通過HashMap的KeySet()（對應(yīng)的是HashSet<T>）返回的節(jié)點(diǎn)集瓦阐，但由于HashSet是不是有序的，所以導(dǎo)致最終的結(jié)果并沒有按預(yù)先的順序篷牌，但結(jié)果整體上滿足遍歷順序的要求睡蟋。

關(guān)于HashMap的順序問題，我做了如下測試：

//返回V1的后繼節(jié)點(diǎn)集
Set<String> successors = graph.successors(V1);
print(success);

//測試HashMap的節(jié)點(diǎn)順序
Map<String, Integer> testMap = new HashMap<>();
testMap.put(V1, 0);
testMap.put(V2, 0);
testMap.put(V3, 0);
print(testMap.keySet());

測試結(jié)果如下枷颊，剛好重現(xiàn)了遍歷順序的差異：

successor: {V3,V2}
Map KeySet() order: {V3,V2,V1}

下面我繼續(xù)來看深度優(yōu)先遍歷：

深度優(yōu)先遍歷

也稱為深度優(yōu)先搜索（Depth First Search）戳杀，它類似于樹的先根遍歷（先訪問樹的根節(jié)點(diǎn)）。其定義如下：
假設(shè)從圖中的某個頂點(diǎn)v出發(fā)夭苗，訪問此節(jié)點(diǎn)后信卡，然后依次從v的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直到圖中所有和v有路徑相通的頂點(diǎn)都被訪問到题造；若此時圖中尚有頂點(diǎn)未被訪問傍菇，則選另選一個未曾訪問的頂點(diǎn)作為起始點(diǎn)重復(fù)上述過程，直至圖中的所有節(jié)點(diǎn)都被訪問到為止界赔。

下面演示對示例圖的深度優(yōu)先遍歷：假設(shè)從起始點(diǎn)v1開始遍歷丢习，在訪問了v1后牵触，選擇其鄰接點(diǎn)v2。因為v2未曾訪問過泛领，則從v2出發(fā)進(jìn)行深度優(yōu)先遍歷荒吏。依次類推，接著從v4渊鞋、v8绰更、v5出發(fā)進(jìn)行遍歷。在訪問了v5后锡宋，由于v5的鄰接點(diǎn)都已被訪問儡湾，則遍歷回退到v8。同樣的理由执俩，繼續(xù)回退到v4徐钠、v2直至v1，此時v1的另一個鄰接點(diǎn)v3未被訪問役首，則遍歷又從v1到v3,再繼續(xù)進(jìn)行下去尝丐。于是得到節(jié)點(diǎn)的線性順序為：v1 -> v2 -> v4 -> v8 -> v5 -> v3 -> v6 -> v7，即示例圖中紅色箭頭線為其深度優(yōu)先遍歷順序衡奥。

深度優(yōu)先遍歷-PreOrder順序（紅色箭頭線及序號為遍歷順序）

算法分析

從上述的描述可以看出爹袁，深度優(yōu)先遍歷的定義就是一個遞歸的過程，每次都以當(dāng)前節(jié)點(diǎn)的第一個未曾訪問過的鄰接點(diǎn)進(jìn)行深度優(yōu)先遍歷的過程矮固。因此使用遞歸函數(shù)實現(xiàn)該算法是最直觀的實現(xiàn)方式失息，但由于遞歸的過程是函數(shù)棧累積的過程，如果節(jié)點(diǎn)數(shù)較多档址，容易造成函數(shù)棧的溢出而導(dǎo)致程序崩潰盹兢，因此正常生產(chǎn)環(huán)境一般會使用一個棧結(jié)構(gòu)（Stack）來存放遍歷的節(jié)點(diǎn)以模擬函數(shù)棧的調(diào)用情況，以此避免遞歸的缺陷守伸。

Guava的大體實現(xiàn)思路也是如此绎秒，使用棧結(jié)構(gòu)來替代函數(shù)的遞歸實現(xiàn)。另外含友，Guava對深度優(yōu)先遍歷還進(jìn)行了擴(kuò)展：區(qū)分節(jié)點(diǎn)的訪問順序是第一次訪問到節(jié)點(diǎn)的順序(PreOrder)替裆，還是訪問到底后回退時的節(jié)點(diǎn)順序(PostOrder)。

附上Guava的原文注釋：
"Pre-order" implies that nodes appear in the {@code Iterable} in the order in which they are first visited.
"Post-order" implies that nodes appear in the {@code Iterable} in the order in which they are visited for the last time.

因此窘问，對于深度優(yōu)先遍歷辆童，Guava根據(jù)這兩個場景定義了下面兩個接口：

//第一次訪問到節(jié)點(diǎn)的順序（Pre-order）
public abstract Iterable<N> depthFirstPreOrder(N startNode);

//訪問到最后，然后回退訪問節(jié)點(diǎn)的順序（Post-order）
public abstract Iterable<N> depthFirstPostOrder(N startNode);

它的實現(xiàn)與上述描述相同惠赫，也是創(chuàng)建了一個Iterable把鉴，然后實現(xiàn)它的iterator()接口，由于這兩個接口相近，下面僅舉例說明其中一個（depthFirstPostOrder）：

@Override
public Iterable<N> depthFirstPostOrder(final N startNode) {
    /**
     * 創(chuàng)建一個匿名的Iterable庭砍，并實現(xiàn)iterator()接口
     */
    return new Iterable<N>() {
        @Override
        public Iterator<N> iterator() {
            /**
             * 返回一個自定義的Iterator
             */
            return new DepthFirstIterator(startNode, Order.POSTORDER);

            /**
             * depthFirstPreOrder()遍歷時也是創(chuàng)建了DepthFirstIterator()场晶，只是參數(shù)換成了Order.PREORDER
             */
            //return new DepthFirstIterator(startNode, Order.PREORDER);
        }
    };
}

該自定義迭代器DepthFirstIterator中，其主體實現(xiàn)在迭代函數(shù)next()中怠缸，每迭代一次（調(diào)用next()函數(shù)一次）返回一個以深度優(yōu)先遍歷為順序的一個節(jié)點(diǎn)：

/**
 * 自定義深度優(yōu)先遍歷的結(jié)果迭代器（AbstractIterator繼承自Iterator）
 */
private final class DepthFirstIterator extends AbstractIterator<N> {

    /**
     * 模擬函數(shù)遞歸遍歷節(jié)點(diǎn)的堆棧诗轻，每次入棧的數(shù)據(jù)是：節(jié)點(diǎn)-節(jié)點(diǎn)的鄰節(jié)點(diǎn)集
     */
    private final Deque<NodeAndSuccessors> stack = new ArrayDeque<>();

    /**
     * 標(biāo)識節(jié)點(diǎn)是否已訪問過
     */
    private final Set<N> visited = new HashSet<>();

    /**
     * 指定深度優(yōu)先遍歷的順序: PREORDER, POSTORDER
     */
    private final Order order;

    /**
     * 構(gòu)造函數(shù)，首先將指定的起始節(jié)點(diǎn)-及鄰接點(diǎn)入棧
     * @param root：起始節(jié)點(diǎn)
     * @param order：指定遍歷的順序
     */
    DepthFirstIterator(N root, Order order) {
        stack.push(withSuccessors(root)); //節(jié)點(diǎn)-及鄰接點(diǎn)入棧
        this.order = order;
    }

    /**
     * 基類封裝的next()函數(shù)
     * @return
     */
    @Override
    protected N computeNext() {
        while (true) { //直到找到合適遍歷順序的節(jié)點(diǎn)
            /**
             * 堆棧為空時揭北，遍歷結(jié)束扳炬，返回null
             */
            if (stack.isEmpty()) {
                return endOfData();
            }

            /**
             * 每次拿到棧頂?shù)臄?shù)據(jù)參與運(yùn)算,且由于withSuccessors()
             * 對應(yīng)的鄰接點(diǎn)也是Iterator,因此需要注意運(yùn)算中是否所有
             * 的鄰接點(diǎn)都有遍歷完畢。（算法核心）
             */
            NodeAndSuccessors node = stack.getFirst();

            /**
             * Set<>.add()操作返回true時搔体，表示為第一次加入到Set集合中
             * 對應(yīng)到遍歷順序 -- PREORDER恨樟。因此firstVisit標(biāo)識PREORDER順序的訪問
             */
            boolean firstVisit = visited.add(node.node);

            /**
             * 當(dāng)successorIterator都遍歷完畢時（!node.successorIterator.hasNext()）,
             * 表示該路徑已經(jīng)遍歷完畢了，現(xiàn)在需要開始回退疚俱，則該節(jié)點(diǎn)是回退時的節(jié)點(diǎn)
             * 對應(yīng)到遍歷順序 -- POSTORDER劝术。因此lastVisit標(biāo)識POSTORDER順序的訪問
             *
             */
            boolean lastVisit = !node.successorIterator.hasNext();

            /**
             * 當(dāng)前步驟是否產(chǎn)生了一個可以返回的迭代節(jié)點(diǎn)（firstVisit | lastVisit）
             */
            boolean produceNode =
                (firstVisit && order == Order.PREORDER) || (lastVisit && order == Order.POSTORDER);

            /**
             * 如果當(dāng)前節(jié)點(diǎn)的鄰接點(diǎn)集都已遍歷完畢時，則將該節(jié)點(diǎn)出棧呆奕。
             * 以致下一次stack.getFirst()時獲得的數(shù)據(jù)變成未訪問的新數(shù)據(jù)
             */
            if (lastVisit) {
                stack.pop();
            } else {
                /**
                 * 如果鄰接點(diǎn)還沒遍歷完畢养晋，則每次將一個鄰接點(diǎn)及鄰接點(diǎn)的鄰接點(diǎn)集合壓入棧中
                 * 需注意該鄰接點(diǎn)是否已有訪問過
                 */
                N successor = node.successorIterator.next();
                if (!visited.contains(successor)) {
                    stack.push(withSuccessors(successor));
                }
            }
            /**
             * 若當(dāng)前節(jié)點(diǎn)滿足遍歷順序（firstVisit | lastVisit）,則返回該節(jié)點(diǎn)。
             * 否則梁钾，將繼續(xù)上述棧中數(shù)據(jù)的操作匙握，直到找到滿足produceNode的節(jié)點(diǎn)或者棧中數(shù)據(jù)遍歷完畢
             */
            if (produceNode) {
                return node.node;
            }
        }
    }

    /**
     * 構(gòu)建堆棧數(shù)據(jù)結(jié)構(gòu)：節(jié)點(diǎn)-及鄰接點(diǎn)
     * @param node
     * @return
     */
    NodeAndSuccessors withSuccessors(N node) {
        return new NodeAndSuccessors(node, graph.successors(node));
    }
}

針對上面給出的深度度優(yōu)先遍歷算法實現(xiàn)，下面還是寫一個簡單demo驗證其實現(xiàn)結(jié)果：

//構(gòu)建示例圖所示的圖結(jié)構(gòu)（無向圖）
MutableGraph<String> graph = GraphBuilder.undirected()
    .nodeOrder(ElementOrder.<String>natural()).build();

graph.putEdge(V1, V2);
graph.putEdge(V1, V3);
graph.putEdge(V2, V4);
graph.putEdge(V2, V5);
graph.putEdge(V3, V6);
graph.putEdge(V3, V7);
graph.putEdge(V4, V8);
graph.putEdge(V5, V8);
graph.putEdge(V6, V7);

//測試depthFirstPreOrder()接口陈轿，從V1開始遍歷
Iterable<String> dfsPre = Traverser.forGraph(graph).depthFirstPreOrder(V1);
for (String node : iterable) {
    print(node);
}


//測試depthFirstPostOrder()接口，從V1開始遍歷
Iterable<String> dfsPost = Traverser.forGraph(graph).depthFirstPostOrder(V1);
for (String node : iterable) {
    print(node);
}

輸出順序為：

dfs pre-order graph: {V1,V3,V6,V7,V2,V5,V8,V4}
dfs post-order graph: {V7,V6,V3,V4,V8,V5,V2,V1}

注：該順序與示例圖的紅色箭頭線標(biāo)識的順序有所不同秦忿，但仍滿足深度優(yōu)先遍歷的順序麦射，其差異原因前面已經(jīng)有說明過。

另外灯谣，由于圖節(jié)點(diǎn)連接屬性的復(fù)雜性（任何兩個節(jié)點(diǎn)都可能存在連接）潜秋，所以在遍歷過程中需要另設(shè)一個Set<N>來記錄該節(jié)點(diǎn)的訪問標(biāo)記（因為圖中如果存在回路時會存在重復(fù)訪問的問題）；為此胎许，Guava對于明確不存在回路的樹形圖（即有向無環(huán)圖）提供了另一種更優(yōu)的訪問方法forTree()峻呛，不過它也是在前面介紹的三種遍歷方法的基礎(chǔ)上進(jìn)行優(yōu)化實現(xiàn)的，具體可以參考原文的前面的鏈接進(jìn)行查看辜窑。

最后钩述，文中示例代碼的詳細(xì)實現(xiàn)參見：https://github.com/Jarrywell/GH-Demo/blob/master/app/src/main/java/com/android/test/demo/graph/TestTraverser.java

參考文檔

《數(shù)據(jù)結(jié)構(gòu)》-- 嚴(yán)蔚敏