基于指针实现邻接矩阵的代码实现与技术咨询

我帮你梳理下这段基于指针的邻接矩阵实现里的几个关键问题，然后给出修正后的实现方案：

现有代码的核心问题 #

• 内存越界风险：
  你创建的Adj_Matrix是大小为lines的指针数组，但循环里i从1跑到columns+1，如果columns >= lines，访问Adj_Matrix[i]会直接超出数组范围，触发未定义行为；另外Adj_Matrix_block的偏移逻辑也有问题，每次+= columns+1会很快超出分配的lines * columns +1内存区域，同样会导致越界。
• 内存泄漏严重：
  函数里分配的Adj_Matrix_block连续内存块，在delete_Mat_adj中完全没有释放；同时Adj_Matrix[0]在循环里反复new int，之前分配的内存直接丢失，都是典型的内存泄漏。
• 逻辑设计混乱：
  你想把Adj_Matrix[0]作为图像分割的源/汇节点，但当前实现没有把它和后续的邻接矩阵行正确关联，完全不符合邻接矩阵的结构逻辑。

修正后的实现方案 #

下面是调整后的代码，既保留你需要的源/汇节点设计，又解决了内存管理和越界问题：

#include <iostream>

// 创建邻接矩阵：lines包含源/汇行（索引0），columns为列数
int** create_Mat_adj(int lines, int columns) {
    // 1. 分配指针数组，存储每一行的地址
    int** Adj_Matrix = new int*[lines];
    
    // 2. 为源/汇行单独分配内存（假设需要columns个元素）
    Adj_Matrix[0] = new int[columns];
    
    // 3. 为剩余lines-1行分配连续内存块，减少内存碎片
    int* continuous_block = new int[(lines - 1) * columns];
    for (int i = 1; i < lines; ++i) {
        // 第i行指向连续块的对应偏移位置
        Adj_Matrix[i] = continuous_block + (i - 1) * columns;
    }
    
    return Adj_Matrix;
}

// 释放邻接矩阵的所有内存
void delete_Mat_adj(int** Adj_Matrix, int lines) {
    // 释放源/汇行的内存
    delete[] Adj_Matrix[0];
    // 释放连续内存块（取第一行节点的起始地址即可）
    delete[] Adj_Matrix[1];
    // 释放指针数组本身
    delete[] Adj_Matrix;
}

// 测试示例
int main() {
    int total_rows = 5; // 含源/汇行共5行
    int cols = 4;
    int** mat = create_Mat_adj(total_rows, cols);
    
    // 初始化源/汇行
    for (int j = 0; j < cols; ++j) {
        mat[0][j] = 0;
    }
    // 初始化其他行的邻接关系
    for (int i = 1; i < total_rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            mat[i][j] = i * cols + j;
        }
    }
    
    // 输出验证
    for (int i = 0; i < total_rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            std::cout << mat[i][j] << " ";
        }
        std::cout << std::endl;
    }
    
    delete_Mat_adj(mat, total_rows);
    return 0;
}

额外建议（针对图像分割场景） #

如果不是必须使用原始指针，更推荐用C++的std::vector来实现，它会自动管理内存，避免手动释放的麻烦，代码也更简洁安全：

#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> create_Mat_adj(int lines, int columns) {
    vector<vector<int>> mat(lines, vector<int>(columns));
    // 一键初始化源/汇行
    fill(mat[0].begin(), mat[0].end(), 0);
    return mat;
}

// 不需要手动写delete函数，vector会自动释放内存

内容的提问来源于stack exchange，提问作者spacing