图添加边函数的校验逻辑实现疑问及代码求助

我来帮你一步步完善这两个校验逻辑，把代码补全到位~

先明确校验顺序（快速失败原则） #

咱们按照先简单后复杂的顺序做校验，这样能尽早返回错误，避免不必要的计算：

1. 先检查是否是自环边（起点=终点）
2. 再检查顶点索引是否合法
3. 最后检查边是否已经存在

逐步实现校验 #

1. 自环边校验 #

你已经写了这部分，完全正确：

if (edge.mStartIndex == edge.mEndIndex) {
    return false;
}

2. 顶点索引合法性校验 #

需要确保起点和终点的索引都在图的合法顶点范围内（0 到 mVertexList.size() - 1）：

// 检查顶点索引是否在合法区间内
size_t vertexCount = mVertexList.size();
if (edge.mStartIndex >= vertexCount || edge.mEndIndex >= vertexCount || 
    edge.mStartIndex < 0 || edge.mEndIndex < 0) {
    return false;
}

注：如果你的索引是无符号类型（比如size_t），可以去掉<0的判断，但为了兼容有符号的索引类型，加上更稳妥。

3. 检查边是否已存在 #

遍历起点对应的邻接表，看看终点是否已经在列表里：

// 遍历起点的邻接表，检查边是否已存在
for (int neighbor : mVertexList[edge.mStartIndex]) {
    if (neighbor == edge.mEndIndex) {
        return false;
    }
}

完整的addEdge函数实现 #

把上面的逻辑整合起来，完整代码如下：

bool Graph::addEdge(const Edge& edge) {
    // 1. 禁止自环边
    if (edge.mStartIndex == edge.mEndIndex) {
        return false;
    }

    // 2. 校验顶点索引合法性
    size_t vertexCount = mVertexList.size();
    if (edge.mStartIndex >= vertexCount || edge.mEndIndex >= vertexCount ||
        edge.mStartIndex < 0 || edge.mEndIndex < 0) {
        return false;
    }

    // 3. 禁止插入已存在的边
    for (int neighbor : mVertexList[edge.mStartIndex]) {
        if (neighbor == edge.mEndIndex) {
            return false;
        }
    }

    // 所有校验通过，添加边
    mVertexList[edge.mStartIndex].emplace_back(edge.mEndIndex);
    // 如果是无向图，还要添加反向边哦！
    // mVertexList[edge.mEndIndex].emplace_back(edge.mStartIndex);

    return true;
}

小提示：如果你的图是无向图，记得添加完正向边后，还要添加一条反向边（终点到起点的边），上面的代码里我加了注释，你可以根据需要打开。

内容的提问来源于stack exchange，提问作者Оксана Волинець