邻接表实现的有向图中顶点前驱与后继的获取方法求助

问题背景 #

你用std::map<T, std::set<T>>实现有向图的邻接表，尝试编写获取前驱和后继节点的函数时出现错误，以下是你的类定义及错误实现：

原类定义

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

    void predecessor(T u);
    void successor(T u, T v);

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

错误实现代码

template <class T>
const std::set<T> Digraph<T>::predecessor(T u) const
{
    std::set<T> p;

    int index = 0;
    for (auto it = graphe.begin(); it != graphe.end(); ++it, index++)
    {
        for(T el : *it) // 错误发生在这里
        {
            if (el == u)
                p.insert(index);
        }
    }
    return p;
}

template <class T>
const std::set<T> Digraph<T>::successor(T u) const
{
    return graphe.at(u);
}

错误分析 #

1. 函数签名不匹配：
   • 类声明中predecessor返回void，但实现中返回const std::set<T>；successor声明有两个参数且返回void，实现却返回std::set<T>，两者完全不匹配。
2. 迭代器遍历错误：
   • graphe是std::map<T, std::set<T>>，迭代器it指向的是std::pair<const T, std::set<T>>类型，直接用for(T el : *it)遍历这个pair是非法的，你需要遍历的是pair中的second成员（即邻接节点集合）。
3. 顶点值混淆：
   • 你用index（循环计数）作为前驱节点插入集合，但index不是图的顶点值，正确的做法是插入当前遍历到的顶点it->first。

修正后的实现 #

首先修正类声明中的函数签名，匹配实际需求：

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

    // 返回u的所有前驱节点集合
    const std::set<T> predecessor(T u) const;
    // 返回u的所有后继节点集合
    const std::set<T> successor(T u) const;

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

然后实现正确的predecessor和successor函数：

template <class T>
const std::set<T> Digraph<T>::predecessor(T u) const
{
    std::set<T> predecessors;

    // 遍历每个顶点及其邻接表
    for (const auto& pair : graphe)
    {
        const T& vertex = pair.first;
        const std::set<T>& adj_nodes = pair.second;

        // 如果当前顶点的邻接表包含u，说明vertex是u的前驱
        if (adj_nodes.find(u) != adj_nodes.end())
        {
            predecessors.insert(vertex);
        }
    }

    return predecessors;
}

template <class T>
const std::set<T> Digraph<T>::successor(T u) const
{
    // 用find避免at()抛出异常，也可以根据需求保留at()
    auto it = graphe.find(u);
    if (it != graphe.end())
    {
        return it->second;
    }
    // 如果u不存在，返回空集合
    return std::set<T>();
}

补充说明 #

• 如果你需要处理顶点不存在的情况，successor中用find比at()更安全，at()会在顶点不存在时抛出std::out_of_range异常，而find可以返回空集合。
• 前驱节点的判断逻辑：遍历所有顶点，若某个顶点的邻接集合包含目标节点u，则该顶点是u的前驱。

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