圖基礎(chǔ)操作

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

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

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

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

圖 9-7   鄰接矩陣的初始化、增刪邊、增刪頂點

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

graph_adjacency_matrix.cpp

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

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

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

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

    /* 刪除頂點 */
    void removeVertex(int index) {
        if (index >= size()) {
            throw out_of_range("頂點不存在");
        }
        // 在頂點列表中移除索引 index 的頂點
        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 對應(yīng) vertices 元素索引
    void addEdge(int i, int j) {
        // 索引越界與相等處理
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
            throw out_of_range("頂點不存在");
        }
        // 在無向圖中，鄰接矩陣沿主對角線對稱，即滿足 (i, j) == (j, i)
        adjMat[i][j] = 1;
        adjMat[j][i] = 1;
    }

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

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

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

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

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

圖 9-8   鄰接表的初始化、增刪邊、增刪頂點

以下是基于鄰接表實現(xiàn)圖的代碼示例。細心的同學(xué)可能注意到，我們在鄰接表中使用 Vertex 節(jié)點類來表示頂點，而這樣做是有原因的。

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

graph_adjacency_list.cpp

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

    /* 在 vector 中刪除指定節(jié)點 */
    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) {
        // 添加所有頂點和邊
        for (const vector<Vertex *> &edge : edges) {
            addVertex(edge[0]);
            addVertex(edge[1]);
            addEdge(edge[0], edge[1]);
        }
    }

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

    /* 添加邊 */
    void addEdge(Vertex *vet1, Vertex *vet2) {
        if (!adjList.count(vet1) || !adjList.count(vet2) || vet1 == vet2)
            throw invalid_argument("不存在頂點");
        // 添加邊 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("不存在頂點");
        // 刪除邊 vet1 - vet2
        remove(adjList[vet1], vet2);
        remove(adjList[vet2], vet1);
    }

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

    /* 刪除頂點 */
    void removeVertex(Vertex *vet) {
        if (!adjList.count(vet))
            throw invalid_argument("不存在頂點");
        // 在鄰接表中刪除頂點 vet 對應(yīng)的鏈表
        adjList.erase(vet);
        // 遍歷其他頂點的鏈表，刪除所有包含 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));
        }
    }
};

效率對比

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

表 9-2   鄰接矩陣與鄰接表對比

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