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

C++圖的遍歷

2023-09-20 09:20 更新

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

圖和樹都都需要應(yīng)用搜索算法來實現(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é)點出發(fā)，始終優(yōu)先訪問距離最近的頂點，并一層層向外擴張。如圖 9-9 所示，從左上角頂點出發(fā)，先遍歷該頂點的所有鄰接頂點，然后遍歷下一個頂點的所有鄰接頂點，以此類推，直至所有頂點訪問完畢。

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

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

1. 算法實現(xiàn)

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

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

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

graph_bfs.cpp

/* 廣度優(yōu)先遍歷 BFS */
// 使用鄰接表來表示圖，以便獲取指定頂點的所有鄰接頂點
vector<Vertex *> graphBFS(GraphAdjList &graph, Vertex *startVet) {
    // 頂點遍歷序列
    vector<Vertex *> res;
    // 哈希表，用于記錄已被訪問過的頂點
    unordered_set<Vertex *> visited = {startVet};
    // 隊列用于實現(xiàn) BFS
    queue<Vertex *> que;
    que.push(startVet);
    // 以頂點 vet 為起點，循環(huán)直至訪問完所有頂點
    while (!que.empty()) {
        Vertex *vet = que.front();
        que.pop();          // 隊首頂點出隊
        res.push_back(vet); // 記錄訪問頂點
        // 遍歷該頂點的所有鄰接頂點
        for (auto adjVet : graph.adjList[vet]) {
            if (visited.count(adjVet))
                continue;            // 跳過已被訪問過的頂點
            que.push(adjVet);        // 只入隊未訪問的頂點
            visited.emplace(adjVet); // 標(biāo)記該頂點已被訪問
        }
    }
    // 返回頂點遍歷序列
    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)”的順序遍歷，而多個相同距離的頂點的遍歷順序是允許被任意打亂的。以圖 9-10 為例，頂點 1、3 的訪問順序可以交換、頂點 2、4、6 的訪問順序也可以任意交換。

2. 復(fù)雜度分析

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

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

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

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

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

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

1. 算法實現(xiàn)

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

graph_dfs.cpp

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

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

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