c++中如何实现图的邻接矩阵_c++图邻接矩阵实现方法-C++-PHP中文网

c++中如何实现图的邻接矩阵_c++图邻接矩阵实现方法

冰火之心

发布： 2025-10-03 16:04:02

原创

272人浏览过

邻接矩阵用二维数组存储图的边关系，适合顶点少且频繁查询边的场景。1. 使用vector<vector<int>>实现n×n矩阵；2. 无向图需双向设置matrixu和matrixv；3. 添加边时检查顶点合法性；4. 空间复杂度O(n²)，适用于稠密图；5. 可扩展为带权图。

c++中如何实现图的邻接矩阵_c++图邻接矩阵实现方法

在C++中实现图的邻接矩阵，核心是用二维数组存储顶点之间的连接关系。适用于顶点数量不多且需要频繁查询边存在性的场景。

邻接矩阵的基本结构

邻接矩阵使用一个二维数组 matrix[n][n] 表示图，其中 n 是顶点数。若顶点 i 到 j 有边，则 matrix[i][j] 为 1（或边权），否则为 0。对于无向图，矩阵是对称的。

常见实现方式是封装在一个类中，包含顶点数、二维数组（可用 vector>）和相关操作函数。

代码实现示例

以下是一个简单的无向图邻接矩阵实现：

乾坤圈新媒体矩阵管家

新媒体账号、门店矩阵智能管理系统

查看详情

立即学习“C++免费学习笔记（深入）”；

#include <iostream>
#include <vector>
using namespace std;

class Graph {
private:
    int vertexNum;
    vector<vector<int>> adjMatrix;

public:
    // 构造函数，初始化矩阵
    Graph(int n) : vertexNum(n) {
        adjMatrix.resize(n, vector<int>(n, 0));
    }

    // 添加边
    void addEdge(int u, int v) {
        if (u >= 0 && u < vertexNum && v >= 0 && v < vertexNum) {
            adjMatrix[u][v] = 1;
            adjMatrix[v][u] = 1;  // 无向图双向设置
        }
    }

    // 删除边
    void removeEdge(int u, int v) {
        if (u >= 0 && u < vertexNum && v >= 0 && v < vertexNum) {
            adjMatrix[u][v] = 0;
            adjMatrix[v][u] = 0;
        }
    }

    // 判断是否有边
    bool hasEdge(int u, int v) {
        if (u >= 0 && u < vertexNum && v >= 0 && v < vertexNum)
            return adjMatrix[u][v] == 1;
        return false;
    }

    // 打印矩阵
    void printMatrix() {
        for (int i = 0; i < vertexNum; ++i) {
            for (int j = 0; j < vertexNum; ++j) {
                cout << adjMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};

登录后复制