C++邻接表实现图时PopulateGraph执行后指针异常崩溃问题求解

问题排查 #

1. 程序崩溃直接原因：PopulateGraph 函数缺少返回值 #

你声明该函数的返回类型为AdjVertex*，但函数执行完成后没有写return head;语句，导致返回值是内存中的随机垃圾值，赋值给G.head[i]后指针指向非法地址，访问时直接触发段错误。

2. 边权值逻辑错误 #

当前你把prob()<P的布尔值（0/1）直接作为权重传给AddNewVertex，不符合作业要求的1~10随机距离要求。虽然概率不通过时权重为0、跳过加边的逻辑是通顺的，但权值范围完全不符合需求。

3. 随机数种子未初始化 #

代码没有调用srand(time(NULL))，每次运行生成的随机序列都是固定的，不符合随机图的生成要求。

4. 无向图逻辑缺失 #

当前仅给顶点i的邻接表添加了j的边，没有同步给顶点j的邻接表添加i的边，最终生成的是有向图而非作业要求的无向图。

5. 命名冲突隐患 #

PopulateGraph的形参head和类的成员变量head重名，虽然当前逻辑下不会触发错误，但非常容易引发后续的逻辑混乱。

核心修复代码 #

// 新增生成1.0~10.0随机距离的函数
double randCost() {
    return 1.0 + static_cast<double>(rand()) / (RAND_MAX / 9.0);
}

// 修改PopulateGraph，补返回值、修正权值逻辑、避免命名冲突
AdjVertex* graph::PopulateGraph(AdjVertex *local_head,int pos,int size, double P){
    #ifdef DEBUG
    cout << "I'm filling adjiacency list of vertex"<< pos<<endl;
    #endif
    for (int j=0;j<size;++j){
        if(pos==j){
            #ifdef DEBUG
            cout << "I'm avoiding a loop"<<endl;
            #endif
        }else if(prob() < P){
            // 概率符合要求时生成1~10的随机权值加边
            local_head = AddNewVertex(j, randCost(), local_head);
        }
    }
    // 补返回值，这是修复崩溃的核心步骤
    return local_head;
}

int main(){
    //  main函数开头加随机数种子初始化
    srand(time(NULL));
    int SIZE=4;
    graph G(SIZE);
    // 其余原有逻辑不变
}

如果要实现无向图，建议调整生成逻辑：不要单顶点循环生成邻接表，而是全局遍历所有i<j的顶点对，符合概率要求时同时给i和j的邻接表加边即可。

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