查找结构是否已存在于向量 C++ 中

Question

我必须找到图中所有边之间的权重，因此由于边是双向的，如果我已经有 1 -> 2，我不想包括 2 -> 1（因为它们具有相同的权重） .边存储在结构 Edge 的向量中。我最初的想法是向上看，是否已经存在起始位置和结束位置互换且权重相同的边，如果是这种情况，则不做任何事情。但是，我不完全知道如何将其放入代码中，因此将不胜感激。也欢迎任何可以优化解决方案的方法。

struct Vertex {
    Vertex(const int i = 0) : index {i}, key {max_key}, parent_index {undef}, processed {false} {}

    int index;        // vertex identifier
    int key;          // temporary minimal weight (Prim algorithm)
    int parent_index; // temporary minimal distance neighboor vertex (Prim algorithm)
    int processed;    // flag used to mark vertices that are already included in V'

    static constexpr int max_key = std::numeric_limits<int>::max();
    static const int undef = -1;
};

struct Edge {
    Edge(int va, int vb, int w) : vi1 {va}, vi2 {vb}, weight {w} { }

    int vi1;    //start point
    int vi2;    //end point 
    int weight;
};

struct Graph {
    int N;                    // number of vertices
    std::vector<Vertex> V;    // set of vertices
    std::vector<Edge> E;      // set of edges
    std::vector<Edge> MST;    // minimal spanning tree
    const int* weights_table; // weights given as distance matrix
};

问题出在 find 我知道这是很多不相关的代码，但我 post 这样做是为了让您更清楚地了解它。如果 2 个顶点之间没有连接，则它们的权重为 -1

// construct vertices and edges for a given graph
void createGraph(Graph& G) {
    // TODO 5.1a: clear V and E and insert all vertex objects and edge objects
    // - vertices are numbered (labeled) from 0 to N-1
    // - edges exist if and only if there is positive distance between two vertices
    // - edges are bidirectional, that is, edges are inserted only once between two vertices
    G.E.clear();
    G.V.clear();

    for(int i = 0; i < G.N; i++){
        Vertex V (i);
        G.V.push_back(V);
    }
  
    for(int i = 0; i < G.N; i++){
        for(int j = 0; j < G.N; j++){
            Edge Ed (i,j,0);
            int weight = getWeight(G,i,j);
            if(weight > 0){
                Ed.weight = weight;
                auto it = find(G.E.begin(), G.E.end(), ....);
                if( it != G.E.end() ) continue;
                G.E.push_back(Ed);
            }
        }
    }
}

谢谢！

Answer 1

好的，我想我明白了，通过将第二个 for 循环更改为这种方式，但我也很想知道如果使用 find 语法会是什么样子


    for(int i = 0; i < G.N; i++){
        for(int j = G.N - 1; j >= 0 + i; j--){
            Edge Ed (i, j , 0);
            int weight = getWeight(G,i,j);
            if(weight > 0){
                Ed.weight = weight;
                G.E.push_back(Ed);
            }
        }
    }

Answer 2

since the edges are bidirectional

您可以构建 Edges 使得 v1 <= v2，然后每个可能的边只有一个表示。

struct Edge {
    Edge(int va, int vb, int w) : vi1 {std::min(va, vb)}, vi2 {std::max(va, vb)}, weight {w} { }

    int vi1;    // earlier point
    int vi2;    // later point
    int weight;
};

旁白：更喜欢就地构建Edge

for(int i = 0; i < G.N; i++){
    for(int j = G.N - 1; j >= 0 + i; j--){
        int weight = getWeight(G,i,j);
        if(weight > 0){
            G.E.emplace_back(i, j, weight);
        }
    }
}

查找结构是否已存在于向量 C++ 中

find if a structure already exists in a vector c++

c++

iterator

structure