1. 遍歷的意義

1.1 圖的遍歷

圖的遍歷是指按照一定規(guī)則訪問(wèn)圖中的所有頂點(diǎn)，以便獲取圖的信息或執(zhí)行特定操作。常見(jiàn)的圖遍歷算法包括深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）。

深度優(yōu)先搜索（DFS）：從起始頂點(diǎn)開(kāi)始，遞歸或使用棧的方式訪問(wèn)相鄰的頂點(diǎn)，直到所有頂點(diǎn)都被訪問(wèn)過(guò)為止。DFS通過(guò)探索圖的深度來(lái)遍歷圖，一直沿著路徑向下直到無(wú)法繼續(xù)，然后回溯到前一個(gè)頂點(diǎn)，繼續(xù)探索其他路徑。

廣度優(yōu)先搜索（BFS）：從起始頂點(diǎn)開(kāi)始，逐層訪問(wèn)其相鄰頂點(diǎn)，先訪問(wèn)距離起始頂點(diǎn)最近的頂點(diǎn)，然后依次訪問(wèn)距離起始頂點(diǎn)更遠(yuǎn)的頂點(diǎn)。BFS通過(guò)探索圖的廣度來(lái)遍歷圖，先訪問(wèn)離起始頂點(diǎn)最近的頂點(diǎn)，然后依次訪問(wèn)其他相鄰的頂點(diǎn)。

這兩種遍歷算法可以用于有向圖和無(wú)向圖，并且可以用來(lái)解決很多與圖相關(guān)的問(wèn)題，例如尋找路徑、判斷連通性、查找最短路徑等。

1.2 樹(shù)的遍歷

樹(shù)的遍歷算法題鏈接：樹(shù)結(jié)構(gòu)及遍歷

示例-前序遍歷：

class TreeNode { 
    int val;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int val) {
        this.val = val;
    }
}

public class TreeTraversal {

    public void preorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        System.out.print(root.val + " "); // 訪問(wèn)根節(jié)點(diǎn)
        preorderTraversal(root.left);     // 前序遍歷左子樹(shù)
        preorderTraversal(root.right);    // 前序遍歷右子樹(shù)
    }
}

2. 圖的深度優(yōu)先遍歷-前序遍歷

public class GraphDFS {

    private Graph G;           // 頂點(diǎn)數(shù)
    private boolean [] visited;         // 邊數(shù)
    private ArrayList<Integer> order = new ArrayList();

    public GraphDFS(Graph G){
        this.G = G;
        visited = new boolean[G.V()];
        dfs(0);
    }

    private void dfs(int v){
        visited[v] = true;
        order.add(v);

        for (int w : G.adj(v)) {
            if (!visited[w]) {
                dfs(w);
            }
        }
    }

    public Iterable<Integer> order(){
        return order;
    }
}

該遞歸方法按照以下步驟進(jìn)行遍歷：

1. 選擇一個(gè)起始節(jié)點(diǎn) v 進(jìn)行遍歷，并將其標(biāo)記為已訪問(wèn)。
2. 輸出當(dāng)前節(jié)點(diǎn)的值。
3. 對(duì)于當(dāng)前節(jié)點(diǎn) v 的每個(gè)鄰接節(jié)點(diǎn) w，如果鄰接節(jié)點(diǎn) w 尚未訪問(wèn)，則遞歸調(diào)用該方法，以節(jié)點(diǎn) w 作為新的起始節(jié)點(diǎn)，繼續(xù)遍歷。
4. 重復(fù)步驟2和步驟3，直到所有節(jié)點(diǎn)都被訪問(wèn)過(guò)。

該遞歸方法的關(guān)鍵在于遞歸調(diào)用。通過(guò)遞歸，當(dāng)遍歷到一個(gè)節(jié)點(diǎn)的鄰接節(jié)點(diǎn)時(shí)，會(huì)先訪問(wèn)鄰接節(jié)點(diǎn)，然后再遞歸訪問(wèn)鄰接節(jié)點(diǎn)的鄰接節(jié)點(diǎn)，以此類(lèi)推，直到遍歷完所有可達(dá)的節(jié)點(diǎn)。這樣就實(shí)現(xiàn)了深度優(yōu)先搜索的效果。

在遍歷過(guò)程中，使用一個(gè)布爾類(lèi)型的數(shù)組 visited 來(lái)標(biāo)記節(jié)點(diǎn)是否已訪問(wèn)。初始時(shí)，所有節(jié)點(diǎn)的訪問(wèn)狀態(tài)都設(shè)置為 false。在遍歷過(guò)程中，將訪問(wèn)過(guò)的節(jié)點(diǎn)標(biāo)記為 true，以避免重復(fù)訪問(wèn)。

通過(guò)遞歸調(diào)用和節(jié)點(diǎn)的訪問(wèn)狀態(tài)標(biāo)記，該方法能夠深入到圖的每個(gè)連通分量，并逐個(gè)訪問(wèn)每個(gè)節(jié)點(diǎn)，確保不會(huì)漏掉任何節(jié)點(diǎn)。

代碼運(yùn)行結(jié)果：

    public static void main(String[] args) {
        Graph graph = new Graph("g.txt");
        GraphDFS graphDFS = new GraphDFS(graph);
        System.out.println(graphDFS.order());
    }

   [0, 1, 2, 3, 4, 5, 6]

   Process finished with exit code 0

上述優(yōu)先遍歷邏輯的問(wèn)題

該方法在遍歷過(guò)程中只能遍歷到與起始節(jié)點(diǎn)連通的頂點(diǎn)，對(duì)于不連通的頂點(diǎn)是無(wú)法遍歷到的。

在構(gòu)造函數(shù) GraphDFS(Graph G) 中，使用深度優(yōu)先搜索算法進(jìn)行遍歷的起始節(jié)點(diǎn)是固定的，即始終從頂點(diǎn)0開(kāi)始。然后在 dfs(int v) 方法中，通過(guò)遞歸調(diào)用遍歷與當(dāng)前節(jié)點(diǎn)相鄰的節(jié)點(diǎn)。由于該算法的起始節(jié)點(diǎn)是固定的，因此只能訪問(wèn)到與起始節(jié)點(diǎn)連通的頂點(diǎn)。

如果圖中存在多個(gè)連通分量（即圖中有多個(gè)獨(dú)立的子圖），且起始節(jié)點(diǎn)只屬于其中一個(gè)連通分量，那么其他連通分量中的頂點(diǎn)是無(wú)法通過(guò)該方法遍歷到的。

要遍歷整個(gè)圖，需要對(duì)每個(gè)頂點(diǎn)都調(diào)用深度優(yōu)先搜索算法進(jìn)行遍歷，以確保遍歷到所有的頂點(diǎn)?？梢酝ㄟ^(guò)循環(huán)遍歷圖中的每個(gè)頂點(diǎn)，并對(duì)未訪問(wèn)過(guò)的頂點(diǎn)調(diào)用深度優(yōu)先搜索方法來(lái)實(shí)現(xiàn)。

改進(jìn)構(gòu)造器方法：

    public GraphDFS(Graph G){
        this.G = G;
        visited = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++ ){
            if (!visited[v]){
                dfs(v);
            }
        }
    }

3. 圖的深度優(yōu)先遍歷-后序遍歷

public class GraphDFS {

    private Graph G;           // 頂點(diǎn)數(shù)
    private boolean [] visited;         // 邊數(shù)
    private ArrayList<Integer> pre = new ArrayList();  // 先序遍歷
    private ArrayList<Integer> post = new ArrayList();   // 后序遍歷

    public GraphDFS(Graph G){
        this.G = G;
        visited = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++ ){
            if (!visited[v]){
                dfs(v);
            }
        }
    }

    private void dfs(int v){
        visited[v] = true;
        pre.add(v);

        for (int w : G.adj(v)) {
            if (!visited[w]) {
                dfs(w);
            }
        }
        post.add(v);
    }

    public Iterable<Integer> pre(){
        return pre;
    }

    public Iterable<Integer> post(){
        return post;
    }

    public static void main(String[] args) {
        Graph graph = new Graph("g.txt");
        GraphDFS graphDFS = new GraphDFS(graph);
        System.out.println(graphDFS.pre());
        System.out.println(graphDFS.post());
    }
}

上述代碼實(shí)現(xiàn)了圖的后序遍歷。主要的實(shí)現(xiàn)思路如下：

在GraphDFS類(lèi)中，定義了一個(gè)私有成員變量pre和post，它們分別用于存儲(chǔ)前序遍歷和后序遍歷的頂點(diǎn)順序。

在GraphDFS的構(gòu)造函數(shù)中，遍歷圖中的所有頂點(diǎn)。對(duì)于每個(gè)未被訪問(wèn)過(guò)的頂點(diǎn)，調(diào)用dfs方法進(jìn)行深度優(yōu)先搜索。

在dfs方法中，首先將當(dāng)前頂點(diǎn)標(biāo)記為已訪問(wèn)，并將其添加到pre列表中，表示前序遍歷的順序。

然后遍歷當(dāng)前頂點(diǎn)的鄰接頂點(diǎn)，如果鄰接頂點(diǎn)未被訪問(wèn)過(guò)，則遞歸調(diào)用dfs方法進(jìn)行深度優(yōu)先搜索。在遞歸回溯時(shí)，將當(dāng)前頂點(diǎn)添加到post列表中，表示后序遍歷的順序。

最后，通過(guò)調(diào)用pre()和post()方法，可以獲取到前序遍歷和后序遍歷的頂點(diǎn)順序。

4. 復(fù)雜度分析

優(yōu)先搜索的過(guò)程中，每個(gè)頂點(diǎn)只會(huì)被訪問(wèn)一次。

對(duì)于稀疏圖（邊數(shù)接近頂點(diǎn)數(shù)的數(shù)量級(jí)）而言，深度優(yōu)先遍歷的時(shí)間復(fù)雜度可以近似地表示為O(V+E)，其中V是頂點(diǎn)數(shù)，E是邊數(shù)。這是因?yàn)樵诿總€(gè)頂點(diǎn)上進(jìn)行一次訪問(wèn)的操作，以及遍歷每條邊的操作都需要一定的時(shí)間。

對(duì)于稠密圖（邊數(shù)接近V^2的數(shù)量級(jí)）而言，深度優(yōu)先遍歷的時(shí)間復(fù)雜度可以近似地表示為O(V^2)，其中V是頂點(diǎn)數(shù)。這是因?yàn)樵诿總€(gè)頂點(diǎn)上進(jìn)行一次訪問(wèn)的操作，以及遍歷每個(gè)頂點(diǎn)的鄰接列表的操作都需要一定的時(shí)間。

上述示例中，是稀疏圖，所以，其時(shí)間復(fù)雜度為 O(V+E)。

總結(jié)而言，深度優(yōu)先遍歷的時(shí)間復(fù)雜度與圖的規(guī)模有關(guān)，一般情況下可以近似表示為O(V+E)或O(V^2)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-740952.html

到了這里，關(guān)于圖論與算法（3）圖的深度優(yōu)先遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！