閱讀(1.1k) 書簽贊(0) 我要糾錯

C++圖的遍歷

2023-09-20 09:20 更新

圖 9-10 圖的廣度優(yōu)先遍歷步驟 graph_bfs_step8 樹代表的是“一對多”的關(guān)系，而圖則具有更高的自由度，可以表示任意的“多對多”關(guān)系。因此，我們可以把樹看作是圖的一種特例。顯然，樹的遍歷操作也是圖的遍歷操作的一種特例.

圖和樹都都需要應(yīng)用搜索算法來實(shí)現(xiàn)遍歷操作。圖的遍歷方式可分為兩種：「廣度優(yōu)先遍歷 breadth-first traversal」和「深度優(yōu)先遍歷 depth-first traversal」。它們也常被稱為「廣度優(yōu)先搜索 breadth-first search」和「深度優(yōu)先搜索 depth-first search」，簡稱 BFS 和 DFS 。

廣度優(yōu)先遍歷

廣度優(yōu)先遍歷是一種由近及遠(yuǎn)的遍歷方式，從某個節(jié)點(diǎn)出發(fā)，始終優(yōu)先訪問距離最近的頂點(diǎn)，并一層層向外擴(kuò)張。如圖 9-9 所示，從左上角頂點(diǎn)出發(fā)，先遍歷該頂點(diǎn)的所有鄰接頂點(diǎn)，然后遍歷下一個頂點(diǎn)的所有鄰接頂點(diǎn)，以此類推，直至所有頂點(diǎn)訪問完畢。

圖的廣度優(yōu)先遍歷

圖 9-9 圖的廣度優(yōu)先遍歷

1. 算法實(shí)現(xiàn)

BFS 通常借助隊(duì)列來實(shí)現(xiàn)。隊(duì)列具有“先入先出”的性質(zhì)，這與 BFS 的“由近及遠(yuǎn)”的思想異曲同工。

將遍歷起始頂點(diǎn) startVet 加入隊(duì)列，并開啟循環(huán)。
在循環(huán)的每輪迭代中，彈出隊(duì)首頂點(diǎn)并記錄訪問，然后將該頂點(diǎn)的所有鄰接頂點(diǎn)加入到隊(duì)列尾部。
循環(huán)步驟 2. ，直到所有頂點(diǎn)被訪問完成后結(jié)束。

為了防止重復(fù)遍歷頂點(diǎn)，我們需要借助一個哈希表 visited 來記錄哪些節(jié)點(diǎn)已被訪問。

graph_bfs.cpp

/* 廣度優(yōu)先遍歷 BFS */
// 使用鄰接表來表示圖，以便獲取指定頂點(diǎn)的所有鄰接頂點(diǎn)
vector<Vertex *> graphBFS(GraphAdjList &graph, Vertex *startVet) {
    // 頂點(diǎn)遍歷序列
    vector<Vertex *> res;
    // 哈希表，用于記錄已被訪問過的頂點(diǎn)
    unordered_set<Vertex *> visited = {startVet};
    // 隊(duì)列用于實(shí)現(xiàn) BFS
    queue<Vertex *> que;
    que.push(startVet);
    // 以頂點(diǎn) vet 為起點(diǎn)，循環(huán)直至訪問完所有頂點(diǎn)
    while (!que.empty()) {
        Vertex *vet = que.front();
        que.pop();          // 隊(duì)首頂點(diǎn)出隊(duì)
        res.push_back(vet); // 記錄訪問頂點(diǎn)
        // 遍歷該頂點(diǎn)的所有鄰接頂點(diǎn)
        for (auto adjVet : graph.adjList[vet]) {
            if (visited.count(adjVet))
                continue;            // 跳過已被訪問過的頂點(diǎn)
            que.push(adjVet);        // 只入隊(duì)未訪問的頂點(diǎn)
            visited.emplace(adjVet); // 標(biāo)記該頂點(diǎn)已被訪問
        }
    }
    // 返回頂點(diǎn)遍歷序列
    return res;
}

代碼相對抽象，建議對照圖 9-10 來加深理解。

圖的廣度優(yōu)先遍歷步驟

graph_bfs_step2

graph_bfs_step3

graph_bfs_step4

graph_bfs_step5

graph_bfs_step6

graph_bfs_step7

graph_bfs_step8

graph_bfs_step9

graph_bfs_step10

graph_bfs_step11

圖 9-10 圖的廣度優(yōu)先遍歷步驟

廣度優(yōu)先遍歷的序列是否唯一？

不唯一。廣度優(yōu)先遍歷只要求按“由近及遠(yuǎn)”的順序遍歷，而多個相同距離的頂點(diǎn)的遍歷順序是允許被任意打亂的。以圖 9-10 為例，頂點(diǎn) 1、3 的訪問順序可以交換、頂點(diǎn) 2、4、6 的訪問順序也可以任意交換。

2. 復(fù)雜度分析

時間復(fù)雜度：所有頂點(diǎn)都會入隊(duì)并出隊(duì)一次，使用 O(|V|) 時間；在遍歷鄰接頂點(diǎn)的過程中，由于是無向圖，因此所有邊都會被訪問 2 次，使用 O(2|E|) 時間；總體使用 O(|V|+|E|) 時間。

空間復(fù)雜度：列表 res ，哈希表 visited ，隊(duì)列 que 中的頂點(diǎn)數(shù)量最多為 |V| ，使用 O(|V|) 空間。

9.3.2 深度優(yōu)先遍歷

深度優(yōu)先遍歷是一種優(yōu)先走到底、無路可走再回頭的遍歷方式。如圖 9-11 所示，從左上角頂點(diǎn)出發(fā)，訪問當(dāng)前頂點(diǎn)的某個鄰接頂點(diǎn)，直到走到盡頭時返回，再繼續(xù)走到盡頭并返回，以此類推，直至所有頂點(diǎn)遍歷完成。

圖的深度優(yōu)先遍歷

圖 9-11 圖的深度優(yōu)先遍歷

1. 算法實(shí)現(xiàn)

這種“走到盡頭再返回”的算法范式通?；谶f歸來實(shí)現(xiàn)。與廣度優(yōu)先遍歷類似，在深度優(yōu)先遍歷中我們也需要借助一個哈希表 visited 來記錄已被訪問的頂點(diǎn)，以避免重復(fù)訪問頂點(diǎn)。

graph_dfs.cpp

/* 深度優(yōu)先遍歷 DFS 輔助函數(shù) */
void dfs(GraphAdjList &graph, unordered_set<Vertex *> &visited, vector<Vertex *> &res, Vertex *vet) {
    res.push_back(vet);   // 記錄訪問頂點(diǎn)
    visited.emplace(vet); // 標(biāo)記該頂點(diǎn)已被訪問
    // 遍歷該頂點(diǎn)的所有鄰接頂點(diǎn)
    for (Vertex *adjVet : graph.adjList[vet]) {
        if (visited.count(adjVet))
            continue; // 跳過已被訪問過的頂點(diǎn)
        // 遞歸訪問鄰接頂點(diǎn)
        dfs(graph, visited, res, adjVet);
    }
}

/* 深度優(yōu)先遍歷 DFS */
// 使用鄰接表來表示圖，以便獲取指定頂點(diǎn)的所有鄰接頂點(diǎn)
vector<Vertex *> graphDFS(GraphAdjList &graph, Vertex *startVet) {
    // 頂點(diǎn)遍歷序列
    vector<Vertex *> res;
    // 哈希表，用于記錄已被訪問過的頂點(diǎn)
    unordered_set<Vertex *> visited;
    dfs(graph, visited, res, startVet);
    return res;
}

深度優(yōu)先遍歷的算法流程如圖 9-12 所示。