通过相邻顶点列表添加和减去图中的边

Question

图的实现，通过相邻顶点的好日子。我有一个写任务的函数，用于通过相邻的图形添加边，删除边

但我不知道如何实现它。需要你的帮助。

 struct Edge 
 {
   int mV; 
   int mW;
   float mWeight;
 };

 struct Node
 { 
  int mEnd; 
  float mWeight; 
 };

 using AdjacencyList = std::vector<Node>;
 using VertexList = std::vector<AdjacencyList>;
 class Graph
 {
   public:
   bool addEdge(const Edge& edge);
   bool removeEdge(const Edge& edge);
   private:
    VertexList mVertexList;
 };

 bool Graph::addEdge(const Edge& edge)
 {
if ((mAdjacencyLists[edge.mV].mEnd == true) && (mAdjacencyLists[edge.mW].mEnd == true) 
    && (mAdjacencyLists[edge.mV].mWeight == false) && (mAdjacencyLists[edge.mW].mEnd == false) && (edge.mV != edge.mW))
{
    Node node;
    mAdjacencyLists[edge.mV] = node.mEnd; // ???
    mAdjacencyLists[edge.mW] = node.mWeight; //???

}
}

 bool Graph::removeEdge(const Edge& edge)
 {
  if ((mAdjacencyLists[edge.mV].mEnd == true) && (mAdjacencyLists    [edge.mW].mEnd == true) && (mAdjacencyLists[edge.mV].mWeight == true) 
    && (mAdjacencyLists[edge.mW].mEnd == true) && (edge.mV != edge.mW))
   {
    // ???

    }

}

更新(重写代码)：

 bool Graph::addEdge(const Edge& edge)
 {
  mVertexList[edge.mV].push_back({ edge.mW, edge.mWeight });
  mVertexList[edge.mW].push_back({ edge.mV, edge.mWeight });
 }

 bool Graph::removeEdge(const Edge& edge)
 {
   auto ita = find_if(mVertexList[edge.mV].cbegin(), mVertexList  [edge.mV].cend(), [edge.mW](const Node& n) { return n.mEnd == edge.mW; });
   mVertexList[edge.mV].erase(ita);
   auto itb = find_if(mVertexList[edge.mW].cbegin(), mVertexList[edge.mW].cend(), [edge.mV](const Node& n) { return n.mEnd == edge.mV; });
   mVertexList[edge.mW].erase(itb);
 }

Answer 1

在这个例子中，我希望你知道正向图中的顶点数。

class G {
    struct Neighbour{
        int _end;
        int _weight;
    };

    std::vector<std::list<Neighbour>> adj;

public:
    G(int verticesCount) : adj(verticesCount) {}

    void addEdge(int a, int b, int w) {
        assert(!hasEdge(a, b));
        adj[a].push_back({ b, w });
        adj[b].push_back({ a, w });
    }

    void dropEdge(int a, int b) {
        assert(hasEdge(a, b));
        auto ita = find_if(adj[a].cbegin(), adj[a].cend(), [b](const Neighbour& n) { return n._end == b; });
        adj[a].erase(ita);
        auto itb = find_if(adj[b].cbegin(), adj[b].cend(), [a](const Neighbour& n) { return n._end == a; });
        adj[b].erase(itb);
    }

    bool hasEdge(int a, int b) {
        auto it = find_if(adj[a].cbegin(), adj[a].cend(), [b](const Neighbour& n) { return n._end == b; });
        // here you might want to check if adjacency list for b also contains entry for the edge
        return it != adj[a].cend();
    }

    int edgeWeight(int a, int b) {
        auto it = find_if(adj[a].cbegin(), adj[a].cend(), [b](const Neighbour& n) { return n._end == b; });
        // the same as in hasEdge, some consistency check might be needed
        return it->_weight;
    }
};

void testG() {
    G g(4);

    g.addEdge(0, 1, 10);
    g.addEdge(1, 2, 20);
    g.addEdge(2, 3, 30);

    cout << boolalpha;
    cout << g.hasEdge(0, 1) << " w = " << g.edgeWeight(0, 1) << endl;
    cout << g.hasEdge(1, 2) << " w = " << g.edgeWeight(1, 2) << endl;
    cout << g.hasEdge(2, 3) << " w = " << g.edgeWeight(2, 3) << endl;
    g.dropEdge(1, 2);
    cout << g.hasEdge(1, 2) << endl;
}


int main() {
    testG();
    system("pause");
    return 0;
}

true w= 10

真w= 20

真w= 30

错误

用邻接表表示存储图会导致一些信息重复，因此进行一致性检查是很好的。