当前位置：首页 > 其他 > 手搓邻接矩阵类代码注释与实现指南：从零开始理解图论数据结构（适合小白）

手搓邻接矩阵类代码注释与实现指南：从零开始理解图论数据结构（适合小白）

1个月前 (06-10)

一、简介和特点

邻接矩阵是用于表示图（Graph）的一种数据结构，通常用二维数组存储节点之间的关系。本文的graph类通过C++实现了一个基础的邻接矩阵结构，特点如下：

1. 动态创建：根据用户输入的节点数量（sum）动态分配内存，避免固定大小的限制。

2. 边权值存储：矩阵元素可存储边的权重（如距离、成本等），支持带权图。

3. 简洁接口：提供添加节点（边）、打印矩阵的公有方法，方便调用。

二、优点

1. 易理解性：相比链表实现的邻接表，矩阵结构更直观，适合新手入门图论。

2. 快速查询：通过索引直接访问节点关系（node[i][j]），时间复杂度为O(1)。

3. 灵活扩展：通过构造函数参数可动态调整图规模，适应不同问题需求。

三、实现步骤

1. 定义类结构：声明sum（节点总数）和node（指向二维数组的指针）。

2. 构造函数初始化：

接收节点数newsum，赋值给sum。

动态分配sum行指针数组：node = new int*[sum]。

为每行分配sum列的数组空间，并初始化所有元素为0。

3. 添加边方法addnode：

接收参数：行索引line、列索引row、边权值val。

将val赋值到对应矩阵位置：node[line][row] = val。

4. 打印方法print：

双层循环遍历矩阵，输出每个元素后换行，展示完整邻接矩阵。

四、代码与注释

#include <iostream>
using namespace std;

// 定义邻接矩阵类
class graph {
private:  
    // 节点总数（矩阵行列数）
    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];  // 为每行分配列数组
            for (int j = 0; j < sum; j++) {  // 初始化元素为0
                node[i][j] = 0;
            }
        }
    }
    // 添加边方法（设置节点i到j的权值）
    void addnode(int line, int row, int val) {
        node[line][row] = val;  // 将val写入指定位置
    }
    // 打印矩阵方法
    void print() {
        for (int i = 0; i < sum; i++) {  // 遍历行
            for (int j = 0; j < sum; j++) {
                cout << node[i][j] << " ";  // 输出元素
            }
            cout << endl;  // 换行
        }
    }
};