一、简介和特点

邻接矩阵 是 图 数据结构 的一种经典实现方式，使用二维 数组 来表示图中顶点之间的连接关系。本文实现的邻接矩阵类可以高效地表示稠密图，并支持快速查询任意两顶点间的连接情况。

‌ 主要特点 ‌：

1. 直观表示：矩阵元素直接反映顶点连接

2. 快速查询：可在O(1)时间内判断两顶点是否相连

3. 权重支持：可以 存储 边的权重信息

4. 简单实现：基于二维数组的直观结构

5. 适合稠密图：顶点多且连接密集时效率高

二、与其他实现的优点

相比 邻接表实现 ，这种 邻接矩阵实现 有以下优势：

1. ‌ 查询高效 ‌：直接通过下标访问连接状态

2. ‌ 实现简单 ‌：仅需二维数组即可表示

3. ‌ 适合稠密图 ‌：空间利用率高

4. ‌ 算法 友好 ‌：许多 图算法 基于矩阵运算

5. ‌ 修改快速 ‌：添加/删除边操作简单

三、实现步骤解析

1. ‌1. 类成员定义 ‌：

• 顶点数量计数器

• 二维数组 指针 存储矩阵

2. ‌2. 构造函数实现 ‌：

• 接收顶点数量参数

• 动态分配二维数组

• 初始化所有元素为0

3. 3‌. 添加边操作 ‌：

• 通过行列下标设置矩阵值

• 支持设置权重值

4. ‌4. 打印功能 ‌：

• 遍历输出整个矩阵

• 按行列格式化显示

四、完整代码和注释

                      #include<iostream>
using namesp  AC  e std;

// 图类，使用邻接矩阵实现
class graph
{
    int sum = 0;    // 顶点数量计数器
    int** node;     // 二维数组指针，存储邻接矩阵
    
public:
    // 构造函数，初始化指定大小的邻接矩阵
    graph(int newsum){
        sum = newsum;  // 设置顶点数量
        node = new int* [sum];  // 分配行指针数组
        
        // 初始化每一行
        for (int i = 0;i < sum;i++){
            node[i] = new int[sum];  // 分配列数组
            // 初始化所有元素为0(表示无连接)
            for (int j = 0;j < sum;j++)
            {
                node[i][j] = 0;
            }
        }
    }
    
    // 添加/修改边的方法
    void addnode(int line, int row, int val){
        node[line][row] = val;  // 设置指定位置的边值
    }
    
    // 打印邻接矩阵
    void print(){
        // 遍历输出矩阵所有元素
        for (int i = 0;i < sum;i++){
            for (int j = 0;j < sum;j++){
                cout << node[i][j] << " ";  // 输出元素值
            }
            cout << endl;  // 换行
        }
    }
};
                    

五、总结

本文介绍了一种邻接矩阵实现的图数据结构，通过详细的代码注释和分步解析，展示了图的基本操作实现。邻接矩阵在表示稠密图时具有明显的查询优势，适合处理顶点间连接密集的图结构。理解这种实现方式对于学习 图论算法 和网络分析有重要意义。