c++ 如何从有向图中删除边和顶点

643ylb08 于 2022-12-05 发布在其他

关注(0)|答案(1)|浏览(230)

给定u和v，我想从邻接列表图中删除u顶点和u，v边。我遵循的方法是从根和其他根的集合中删除顶点。
实施例：
我要删除顶点u

u -> a b c d
x -> u   // u should be deleted

下面是我的课程的简要描述：

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);

    for (auto const &pair : graphe)
    {
        for (auto const &elem : pair.second)
        {
            if(elem == u){
                pair->second.erase(u);
            }
        }
    }
}

template <class T>
void Digraph<T>::delete_edge(T u, T v)
{
    std::set<T> s = graphe[u];
    s.erase(v);
}

我想知道我在delete_vertex函数中所做的是否正确，因为它不起作用，也许我忘了什么，有人能帮我吗？

c++

来源：https://stackoverflow.com/questions/74673116/how-to-delete-edge-and-vertices-from-directed-graph

1条答案

按热度按时间

9jyewag01#

这两个函数都有bug。delete_edge的问题是你复制了一组边，然后你从副本中擦除了而不是原始的。这是C++初学者常见的错误，他们把对象当作引用，而实际上它们并不是。下面是真正使用引用的版本

template <class T>
void Digraph<T>::delete_edge(T u, T v)
{
    std::set<T>& s = graphe[u]; // s is a reference
    s.erase(v);
}

但仅仅消除变量就更简单了（恕我直言）

template <class T>
void Digraph<T>::delete_edge(T u, T v)
{
    graphe[u].erase(v);
}

delete_vertex的问题就像某个程序员说的那样，如果你在一个容器中迭代，你就不能从这个容器中擦除。

template <class T>
void Digraph<T>::delete_vertex(T u)
{
    graphe.erase(u);
    for (auto const &pair : graphe)
    {
        auto i = pair.second.begin();
        while (i != pair.second.end())
        {
            if (*i == u)
                i = pair.second.erase(i);
            else
                ++i;
        }
    }
}

甚至在一个迭代器上使用++指向一个被擦除的元素也是非法的，这就是为什么erase返回一个迭代器指向下一个元素。
未经测试的代码，所以道歉的任何错误。

赞(0）回复(0）举报 2022-12-05

我来回答

c++ 如何从有向图中删除边和顶点

1条答案

相关问题

热门标签

最新问答