c++ - 使用给定路径查找 MST (C++)

Question

我有一个用于查找 MST 的代码，其中包括一个给定的 MST 路径，它给了我正确的 MST 权重（我知道输出应该是什么）。我试图重写代码的一部分以使用std::map而不是std::vector进行更有效的查找（从下面的代码中可以清楚地看出），但现在它给出了错误的答案，尽管研究了几个小时，我还是无法理解我在哪里做错了。任何有关定位错误的帮助将不胜感激。

旧版本使用vector<Edge>. 遍历所有边的向量 ( m_all_edges)。如果边e在 中vector<Edge> path，则将其添加到 MST ( m_mst)。m_edges否则，将其添加到 MST ( )的候选边。

void MSTPath::m_add_shortest_path_old(vector<Edge> path){
    for (auto e : path){
        m_graph->union_vu(e.get_node(),e.get_opposite_node(-1));
    }
    for (auto e : m_all_edges){
        if (tempfunc(e,path)) m_mst.push_back(e);
        else m_edges.push_back(e);
    }
}

bool MSTPath::tempfunc(Edge e, vector<Edge> path){
    for (auto edge : path){
        if((edge.get_node()==e.get_node())&&(edge.get_opposite_node(-1)==e.get_opposite_node(-1))) return true;
    }
    return false;
}

版本与std::map.

void MSTPath::m_add_shortest_path(map<Edge,int> path_map){
    for (auto const& x : path_map){
        Edge e = x.first;
        m_graph->union_vu(e.get_node(),e.get_opposite_node(-1));
    }
    for (auto const& x : m_all_edges_map){
        if ((path_map.count(x.first)>0)||(path_map.count(x.first.reversed())>0)) m_mst.push_back(x.first);
        else m_edges.push_back(x.first);
    }
}

查找 MST 的函数（在调用m_add_shortest_path/之后调用m_add_shortest_path_old）。

int MSTPath::m_compute_mst(){
    sort(m_edges.begin(),m_edges.end(),[](Edge e1, Edge e2) { return e1.weight < e2.weight; });
    int i = 0;
    int mst_size = m_mst.size();

    int mst_weight = 0;
    int v,u;
    for (Edge e : m_mst) mst_weight += e.weight;

    while (mst_size<m_N-1){
        Edge edge = m_edges[i++];
        v = m_graph->find(edge.get_node());
        u = m_graph->find(edge.get_opposite_node(-1));
        if (u!=v){
            mst_size++;
            mst_weight += edge.weight;
            if (mst_weight>=min_mst_weight) return numeric_limits<int>::max();
            m_mst.push_back(edge);
            m_graph->union_vu(v,u);
        }
    }
    return mst_weight;
}

据我所知，这两个函数都完全相同m_mst（并且开始mst_weight）和相同m_edges（但顺序不同）。但是排序对算法来说应该不是问题（除了按重量排序，但这是句柄m_compute_mst），对吧？

Edge班级：

class Edge{
public:
    Edge(int v_e, int u_e, int w){
        v = v_e;
        u = u_e;
        weight = w;
    }

    int get_node() const { return v; }
    int get_opposite_node(int k) const {
        if ((k==v) || (k==-1)) return u;
        else return v;
    }

    Edge reversed() const {
        return Edge(u,v,weight);
    }

    bool operator<(const Edge& e) const {
        if (this->get_node()<e.get_node()) return true;
        else if (this->get_node()==e.get_node()) return this->get_opposite_node(-1)<e.get_opposite_node(-1);
        else return false;
    }

    int v, u, weight;
};

是的，我知道按值传递会产生额外的副本。这是一个临时版本。

标签： c++graph-theoryminimum-spanning-tree