圖基礎(chǔ)操作

圖的基礎(chǔ)操作可分為對(duì)“邊”的操作和對(duì)“頂點(diǎn)”的操作。在“鄰接矩陣”和“鄰接表”兩種表示方法下，實(shí)現(xiàn)方式有所不同。

9.2.1   基于鄰接矩陣的實(shí)現(xiàn)

給定一個(gè)頂點(diǎn)數(shù)量為 n 的無向圖，則各種操作的實(shí)現(xiàn)方式如圖 9-7 所示。

• 添加或刪除邊：直接在鄰接矩陣中修改指定的邊即可，使用 O(1) 時(shí)間。而由于是無向圖，因此需要同時(shí)更新兩個(gè)方向的邊。
• 添加頂點(diǎn)：在鄰接矩陣的尾部添加一行一列，并全部填 0 即可，使用 O(n) 時(shí)間。
• 刪除頂點(diǎn)：在鄰接矩陣中刪除一行一列。當(dāng)刪除首行首列時(shí)達(dá)到最差情況，需要將 (n?1)2 個(gè)元素“向左上移動(dòng)”，從而使用 O(n2) 時(shí)間。
• 初始化：傳入 n 個(gè)頂點(diǎn)，初始化長(zhǎng)度為 n 的頂點(diǎn)列表 vertices ，使用 O(n) 時(shí)間；初始化 n×n 大小的鄰接矩陣 adjMat ，使用 O(n2) 時(shí)間。

圖 9-7   鄰接矩陣的初始化、增刪邊、增刪頂點(diǎn)

以下是基于鄰接矩陣表示圖的實(shí)現(xiàn)代碼。

graph_adjacency_matrix.cpp

/* 基于鄰接矩陣實(shí)現(xiàn)的無向圖類 */
class GraphAdjMat {
    vector<int> vertices;       // 頂點(diǎn)列表，元素代表“頂點(diǎn)值”，索引代表“頂點(diǎn)索引”
    vector<vector<int>> adjMat; // 鄰接矩陣，行列索引對(duì)應(yīng)“頂點(diǎn)索引”

  public:
    /* 構(gòu)造方法 */
    GraphAdjMat(const vector<int> &vertices, const vector<vector<int>> &edges) {
        // 添加頂點(diǎn)
        for (int val : vertices) {
            addVertex(val);
        }
        // 添加邊
        // 請(qǐng)注意，edges 元素代表頂點(diǎn)索引，即對(duì)應(yīng) vertices 元素索引
        for (const vector<int> &edge : edges) {
            addEdge(edge[0], edge[1]);
        }
    }

    /* 獲取頂點(diǎn)數(shù)量 */
    int size() const {
        return vertices.size();
    }

    /* 添加頂點(diǎn) */
    void addVertex(int val) {
        int n = size();
        // 向頂點(diǎn)列表中添加新頂點(diǎn)的值
        vertices.push_back(val);
        // 在鄰接矩陣中添加一行
        adjMat.emplace_back(vector<int>(n, 0));
        // 在鄰接矩陣中添加一列
        for (vector<int> &row : adjMat) {
            row.push_back(0);
        }
    }

    /* 刪除頂點(diǎn) */
    void removeVertex(int index) {
        if (index >= size()) {
            throw out_of_range("頂點(diǎn)不存在");
        }
        // 在頂點(diǎn)列表中移除索引 index 的頂點(diǎn)
        vertices.erase(vertices.begin() + index);
        // 在鄰接矩陣中刪除索引 index 的行
        adjMat.erase(adjMat.begin() + index);
        // 在鄰接矩陣中刪除索引 index 的列
        for (vector<int> &row : adjMat) {
            row.erase(row.begin() + index);
        }
    }

    /* 添加邊 */
    // 參數(shù) i, j 對(duì)應(yīng) vertices 元素索引
    void addEdge(int i, int j) {
        // 索引越界與相等處理
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
            throw out_of_range("頂點(diǎn)不存在");
        }
        // 在無向圖中，鄰接矩陣沿主對(duì)角線對(duì)稱，即滿足 (i, j) == (j, i)
        adjMat[i][j] = 1;
        adjMat[j][i] = 1;
    }

    /* 刪除邊 */
    // 參數(shù) i, j 對(duì)應(yīng) vertices 元素索引
    void removeEdge(int i, int j) {
        // 索引越界與相等處理
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
            throw out_of_range("頂點(diǎn)不存在");
        }
        adjMat[i][j] = 0;
        adjMat[j][i] = 0;
    }

    /* 打印鄰接矩陣 */
    void print() {
        cout << "頂點(diǎn)列表 = ";
        printVector(vertices);
        cout << "鄰接矩陣 =" << endl;
        printVectorMatrix(adjMat);
    }
};

基于鄰接表的實(shí)現(xiàn)

設(shè)無向圖的頂點(diǎn)總數(shù)為 n、邊總數(shù)為 m ，則可根據(jù)圖 9-8 所示的方法實(shí)現(xiàn)各種操作。

• 添加邊：在頂點(diǎn)對(duì)應(yīng)鏈表的末尾添加邊即可，使用 O(1) 時(shí)間。因?yàn)槭菬o向圖，所以需要同時(shí)添加兩個(gè)方向的邊。
• 刪除邊：在頂點(diǎn)對(duì)應(yīng)鏈表中查找并刪除指定邊，使用 O(m) 時(shí)間。在無向圖中，需要同時(shí)刪除兩個(gè)方向的邊。
• 添加頂點(diǎn)：在鄰接表中添加一個(gè)鏈表，并將新增頂點(diǎn)作為鏈表頭節(jié)點(diǎn)，使用 O(1) 時(shí)間。
• 刪除頂點(diǎn)：需遍歷整個(gè)鄰接表，刪除包含指定頂點(diǎn)的所有邊，使用 O(n+m) 時(shí)間。
• 初始化：在鄰接表中創(chuàng)建 n 個(gè)頂點(diǎn)和 2m 條邊，使用 O(n+m) 時(shí)間。

圖 9-8   鄰接表的初始化、增刪邊、增刪頂點(diǎn)

以下是基于鄰接表實(shí)現(xiàn)圖的代碼示例。細(xì)心的同學(xué)可能注意到，我們?cè)卩徑颖碇惺褂?nbsp;Vertex 節(jié)點(diǎn)類來表示頂點(diǎn)，而這樣做是有原因的。

1. 如果我們選擇通過頂點(diǎn)值來區(qū)分不同頂點(diǎn)，那么值重復(fù)的頂點(diǎn)將無法被區(qū)分。
2. 如果類似鄰接矩陣那樣，使用頂點(diǎn)列表索引來區(qū)分不同頂點(diǎn)。那么，假設(shè)我們想要?jiǎng)h除索引為 i 的頂點(diǎn)，則需要遍歷整個(gè)鄰接表，將其中 >i 的索引全部減 1 ，這樣操作效率較低。
3. 因此我們考慮引入頂點(diǎn)類 Vertex ，使得每個(gè)頂點(diǎn)都是唯一的對(duì)象，此時(shí)刪除頂點(diǎn)時(shí)就無須改動(dòng)其余頂點(diǎn)了。

graph_adjacency_list.cpp

/* 基于鄰接表實(shí)現(xiàn)的無向圖類 */
class GraphAdjList {
  public:
    // 鄰接表，key: 頂點(diǎn)，value：該頂點(diǎn)的所有鄰接頂點(diǎn)
    unordered_map<Vertex *, vector<Vertex *>> adjList;

    /* 在 vector 中刪除指定節(jié)點(diǎn) */
    void remove(vector<Vertex *> &vec, Vertex *vet) {
        for (int i = 0; i < vec.size(); i++) {
            if (vec[i] == vet) {
                vec.erase(vec.begin() + i);
                break;
            }
        }
    }

    /* 構(gòu)造方法 */
    GraphAdjList(const vector<vector<Vertex *>> &edges) {
        // 添加所有頂點(diǎn)和邊
        for (const vector<Vertex *> &edge : edges) {
            addVertex(edge[0]);
            addVertex(edge[1]);
            addEdge(edge[0], edge[1]);
        }
    }

    /* 獲取頂點(diǎn)數(shù)量 */
    int size() {
        return adjList.size();
    }

    /* 添加邊 */
    void addEdge(Vertex *vet1, Vertex *vet2) {
        if (!adjList.count(vet1) || !adjList.count(vet2) || vet1 == vet2)
            throw invalid_argument("不存在頂點(diǎn)");
        // 添加邊 vet1 - vet2
        adjList[vet1].push_back(vet2);
        adjList[vet2].push_back(vet1);
    }

    /* 刪除邊 */
    void removeEdge(Vertex *vet1, Vertex *vet2) {
        if (!adjList.count(vet1) || !adjList.count(vet2) || vet1 == vet2)
            throw invalid_argument("不存在頂點(diǎn)");
        // 刪除邊 vet1 - vet2
        remove(adjList[vet1], vet2);
        remove(adjList[vet2], vet1);
    }

    /* 添加頂點(diǎn) */
    void addVertex(Vertex *vet) {
        if (adjList.count(vet))
            return;
        // 在鄰接表中添加一個(gè)新鏈表
        adjList[vet] = vector<Vertex *>();
    }

    /* 刪除頂點(diǎn) */
    void removeVertex(Vertex *vet) {
        if (!adjList.count(vet))
            throw invalid_argument("不存在頂點(diǎn)");
        // 在鄰接表中刪除頂點(diǎn) vet 對(duì)應(yīng)的鏈表
        adjList.erase(vet);
        // 遍歷其他頂點(diǎn)的鏈表，刪除所有包含 vet 的邊
        for (auto &adj : adjList) {
            remove(adj.second, vet);
        }
    }

    /* 打印鄰接表 */
    void print() {
        cout << "鄰接表 =" << endl;
        for (auto &adj : adjList) {
            const auto &key = adj.first;
            const auto &vec = adj.second;
            cout << key->val << ": ";
            printVector(vetsToVals(vec));
        }
    }
};

效率對(duì)比

設(shè)圖中共有 n 個(gè)頂點(diǎn)和 m 條邊，表 9-2 對(duì)比了鄰接矩陣和鄰接表的時(shí)間和空間效率。

表 9-2   鄰接矩陣與鄰接表對(duì)比

觀察表 9-2 ，似乎鄰接表（哈希表）的時(shí)間與空間效率最優(yōu)。但實(shí)際上，在鄰接矩陣中操作邊的效率更高，只需要一次數(shù)組訪問或賦值操作即可。綜合來看，鄰接矩陣體現(xiàn)了“以空間換時(shí)間”的原則，而鄰接表體現(xiàn)了“以時(shí)間換空間”的原則。