基于邻接顶点的图实现：增删改查功能代码求助

看起来你在实现邻接表结构的图操作时遇到了卡点，我来帮你逐个拆解这些函数的实现思路和代码细节，你可以对照自己的现有代码来补充那些标注??????的部分：

您好，我的任务是编写基于邻接顶点的图的相关函数，包括添加顶点、添加边、添加边权重，删除顶点、删除边、删除边权重，以及查找邻接顶点或边。我已完成部分代码，但标注“??????”的部分不知如何实现，特向您求助。头文件代码如下：

//header//
#pragma once
#include <vector>
struct Edge {
    int mV;
    int mW;
};
struct Node {
    int mEnd;
    float mWeight;
};
// 假设图的核心结构是邻接表：std::vector<std::vector<Node>> adjList;

1. 添加顶点 #

• 实现逻辑：邻接表的本质是存储邻接列表的数组（vector），添加顶点只需在主vector中插入一个空的子vector即可，代表新顶点暂时没有邻接节点。
• 代码实现：

void addVertex(std::vector<std::vector<Node>>& adjList) {
    adjList.emplace_back(); // 插入空的邻接列表，新顶点的编号就是当前adjList的size()-1
}

2. 添加边（含权重） #

• 实现逻辑：先校验起点和终点的合法性（是否在现有顶点范围内），然后在起点对应的邻接列表中添加一个Node对象，存储终点编号和权重。如果是无向图，别忘了还要添加反向边。
• 代码实现：

bool addEdge(std::vector<std::vector<Node>>& adjList, int start, int end, float weight) {
    // 校验顶点是否存在
    if (start < 0 || start >= adjList.size() || end < 0 || end >= adjList.size()) {
        return false; // 顶点不合法，添加失败
    }
    // 添加起点到终点的边
    adjList[start].push_back({end, weight});
    // 如果是无向图，添加反向边
    // adjList[end].push_back({start, weight});
    return true;
}

3. 删除顶点 #

• 实现逻辑：这是相对复杂的操作，需要两步：
  1. 删除目标顶点对应的邻接列表项；
  2. 遍历所有剩余顶点的邻接列表，删除所有指向该顶点的边，同时还要更新所有编号大于目标顶点的终点编号（因为删除一个顶点后，后续顶点的编号会前移一位）。
• 代码实现：

bool removeVertex(std::vector<std::vector<Node>>& adjList, int vertex) {
    if (vertex < 0 || vertex >= adjList.size()) {
        return false; // 顶点不存在
    }
    // 第一步：删除目标顶点的邻接列表
    adjList.erase(adjList.begin() + vertex);
    // 第二步：清理所有指向原顶点的边，并更新终点编号
    for (auto& neighbors : adjList) {
        for (auto it = neighbors.begin(); it != neighbors.end(); ) {
            if (it->mEnd == vertex) {
                // 删除指向原顶点的边
                it = neighbors.erase(it);
            } else {
                // 如果原顶点编号小于当前终点，更新终点编号（因为顶点总数减少了1）
                if (it->mEnd > vertex) {
                    it->mEnd--;
                }
                ++it;
            }
        }
    }
    return true;
}

4. 删除边 #

• 实现逻辑：找到起点对应的邻接列表，遍历其中的Node，找到终点匹配的项并删除。如果是无向图，还要同步删除反向边。
• 代码实现：

bool removeEdge(std::vector<std::vector<Node>>& adjList, int start, int end) {
    if (start < 0 || start >= adjList.size() || end < 0 || end >= adjList.size()) {
        return false;
    }
    // 删除起点到终点的边
    auto& neighbors = adjList[start];
    for (auto it = neighbors.begin(); it != neighbors.end(); ) {
        if (it->mEnd == end) {
            it = neighbors.erase(it);
        } else {
            ++it;
        }
    }
    // 无向图需删除反向边
    // auto& reverseNeighbors = adjList[end];
    // for (auto it = reverseNeighbors.begin(); it != reverseNeighbors.end(); ) {
    //     if (it->mEnd == start) {
    //         it = reverseNeighbors.erase(it);
    //     } else {
    //         ++it;
    //     }
    // }
    return true;
}

5. 修改/删除边权重 #

• 实现逻辑：修改权重只需找到对应边，更新其mWeight字段；如果是“删除权重”，可以根据需求设置为默认值（比如0），或者直接删除边。
• 代码实现：

// 更新边的权重
bool updateEdgeWeight(std::vector<std::vector<Node>>& adjList, int start, int end, float newWeight) {
    if (start < 0 || start >= adjList.size() || end < 0 || end >= adjList.size()) {
        return false;
    }
    auto& neighbors = adjList[start];
    for (auto& node : neighbors) {
        if (node.mEnd == end) {
            node.mWeight = newWeight;
            return true;
        }
    }
    return false; // 边不存在
}

// 删除权重（设置为默认值，这里用0.0f举例）
bool removeEdgeWeight(std::vector<std::vector<Node>>& adjList, int start, int end) {
    return updateEdgeWeight(adjList, start, end, 0.0f);
}

6. 查找邻接顶点或边 #

• 查找邻接顶点：返回目标顶点对应的所有邻接终点编号；
• 查找边：检查起点的邻接列表中是否存在指向终点的边，存在则返回权重，不存在返回特殊标记（比如-1.0f）。
• 代码实现：

// 获取指定顶点的所有邻接顶点
std::vector<int> getNeighbors(const std::vector<std::vector<Node>>& adjList, int vertex) {
    std::vector<int> neighbors;
    if (vertex < 0 || vertex >= adjList.size()) {
        return neighbors;
    }
    for (const auto& node : adjList[vertex]) {
        neighbors.push_back(node.mEnd);
    }
    return neighbors;
}

// 查找指定边的权重，不存在返回-1.0f
float findEdgeWeight(const std::vector<std::vector<Node>>& adjList, int start, int end) {
    if (start < 0 || start >= adjList.size() || end < 0 || end >= adjList.size()) {
        return -1.0f;
    }
    for (const auto& node : adjList[start]) {
        if (node.mEnd == end) {
            return node.mWeight;
        }
    }
    return -1.0f;
}

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