C++邻接表有向图顶点/边删除函数问题求助

我需要从邻接表实现的有向图中删除指定顶点u以及边<u,v>。思路是从图的顶点集合中删除u，同时移除其他节点邻接集合中指向u的边。

示例 #

想要删除顶点u：

u -> a b c d
x -> u   // u 应该被删除

Digraph类定义 #

template <class T>
class Digraph
{
public:
    Digraph();
    ~Digraph();

    void delete_vertex(T u);
    void delete_edge(T u, T v);

private:
    std::map<T, std::set<T>> graph;
};

我的错误实现 #

template <class T>
void Digraph<T>::delete_vertex(T u)
{
    graphe.erase(u);  // 拼写错误：graph写成了graphe

    for (auto const &pair : graphe)
    {
        for (auto const &elem : pair.second)
        {
            if(elem == u){
                pair->second.erase(u);  // const引用无法修改，且遍历方式冗余
            }
        }
    }
}

template <class T>
void Digraph<T>::delete_edge(T u, T v)
{
    std::set<T> s = graphe[u];  // 拷贝了集合，修改的是副本而非原数据
    s.erase(v);
}

问题分析与修正代码 #

错误点梳理 #

1. 变量名拼写错误：多处把成员变量graph写成了graphe，直接导致逻辑或编译错误
2. delete_vertex逻辑问题：使用const引用遍历顶点对，无法修改邻接集合；嵌套遍历查找u的方式冗余低效
3. delete_edge逻辑问题：拷贝邻接集合后修改副本，原图数据不会被更新；直接用graph[u]会在u不存在时自动插入空集合，不符合预期

修正后的代码 #

template <class T>
void Digraph<T>::delete_vertex(T u)
{
    // 1. 删除顶点u自身的条目
    graph.erase(u);

    // 2. 遍历所有顶点的邻接集合，移除指向u的边
    for (auto &pair : graph)  // 去掉const，允许修改邻接集合
    {
        pair.second.erase(u);  // set的erase方法可直接传入值，自动查找并删除
    }
}

template <class T>
void Digraph<T>::delete_edge(T u, T v)
{
    // 先检查u是否存在，避免map自动插入空集合
    auto it = graph.find(u);
    if (it != graph.end())
    {
        it->second.erase(v);  // 直接修改原邻接集合
    }
}

关键说明 #

• delete_vertex中利用std::set::erase(value)的特性，无需手动遍历查找，直接删除目标元素，效率更高
• delete_edge中用graph.find(u)替代graph[u]，避免不必要的默认插入操作，只在顶点存在时才执行删除边的操作

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