定義

「圖 graph」是一種非線性數據結構，由「頂點 vertex」和「邊 edge」組成。我們可以將圖 G抽象地表示為一組頂點 V和一組邊 E 的集合。以下示例展示了一個包含 5 個頂點和 7 條邊的圖。

表示

鄰接矩陣和鄰接表兩種表示方法

鄰接矩陣代碼

#include <iostream>
#include <stdexcept>
#include <vector>
/**
 * @brief 
 * 基於鄰接矩陣實現的無向圖
 */
 using namespace std;
class GraphAdjMat {
    std::vector<int> vertices;
    std::vector<std::vector<int>> adjMat;
public:
    GraphAdjMat(const vector<int> &vertices,const vector<vector<int>> &edges) {
        for(int val:vertices) {
            addVertex(val);
        }
        // 添加邊
        // 請註意，edges 元素代表頂點索引，即對應 vertices 元素索引
        for (const vector<int> &edge : edges) {
            addEdge(edge[0],edge[1]);
        }
    }
    int size() {
        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);
        for(vector<int> &row :adjMat) {
            row.erase(row.begin() index);
        }
    }
    void addEdge(int i, int j) {
        if(i <0 || j<0|| i>size()|| j>size()|| i == j) {
            throw out_of_range("頂點不存在");
        }
        adjMat[i][j] = 1;
        adjMat[j][i] = 1;
    }
    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 << "頂點列表:" <<endl;
        printVector(vertices);
        cout << "鄰接矩陣:"<<endl;
        printVectorMatrix(adjMat);
    }
    void printVector(const vector<int> &vector) {
        for (int val : vector) {
            cout  << val << ",";
        }
        cout << endl;
    }
    void printVectorMatrix(const vector<vector<int>> &vectorMatrix) {
        for (auto &rowV : vectorMatrix) {
             for (auto&el : rowV) {
                cout  << el << " ";
             }
             cout << endl;
        }
    }
};
int main() {
    vector<int>  vertices = {1,2,5,4,6};
    std::vector<std::vector<int>> adjMat = {{0,1},{0,2},{1,0},{1,2},{1,3},{2,0},{2,1},{2,3},{3,1},{3,2},};
    GraphAdjMat *G = new GraphAdjMat(vertices,adjMat);//定義圖結構變量
    G->print();
    return 0;
}

輸出

頂點列表:
1,2,5,4,6,
鄰接矩陣:
0 1 1 0 0 
1 0 1 1 0 
1 1 0 1 0 
0 1 1 0 0 
0 0 0 0 0