通过相邻顶点列表添加和减去图中的边 [英] add and subtract the edges in the graph through the list of adjacent vertices

问题描述

通过相邻顶点
实现图形美好的一天。我通过相邻的添加边为图形添加了任务写入功能
删除边

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

pre $ $ $ $ $ $ $ $ $ $ $ $ $ $ $'
int mW;
float mWeight;
};

struct Node
{
int mEnd;
float mWeight;
};

使用AdjacencyList = std :: vector< Node>;
使用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））
{
节点节点;
mAdjacencyLists [edge.mV] = node.mEnd; // ???
mAdjacencyLists [edge.mW] = node.mWeight; // ???



$ b bool Graph :: removeEdge（const Edge& edge）
{
if（（mAdjacencyLists [edge.mV ] .mEnd == true）&& amp;（mAdjacencyLists [edge.mW] .mEnd == true）&& amp;（mAdjacencyLists [edge.mV] .mWeight == true）
&&（ mAdjacencyLists [edge.mW] .mEnd == true）&&（edge.mV！= edge.mW））
{
// ???






$ b

UPD（重写代码）：


$ 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）;

解决方案

在这个例子中，

  class G {
 struct Neighbor {
 int _结束; 
 int _weight; 
}; 
 
 std :: vector< std :: list< Neighbor>>形容词; 
 $ b $ 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 Neighbor& n）{return n._end == b;}）; 
 adj [a] .erase（ita）; 
 auto itb = find_if（adj [b] .cbegin（），adj [b] .cend（），[a]（const Neighbor& 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 Neighbor& n）{return n._end == b;}）; 
 //在这里你可能想要检查b的邻接表是否还包含边的入口
 return it！= adj [a] .cend（）; 
} 
 
 int edgeWeight（int a，int b）{
 auto it = find_if（adj [a] .cbegin（），adj [a] .cend（）， [b]（const Neighbor& n）{return n._end == b;}）; 
 //与hasEdge相同，可能需要进行一致性检查
 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（）; 
系统（暂停）; 
返回0; 
} 
  

true w = 10

true w = 20

true w = 30

false

存储图与邻接列表表示导致一些信息重复，所以一致性检查是很好的。

Implementation of the graph through the adjacent vertices Good day. I have a task-write function for the graph through the adjacent add edge Remove the edge

But I do not know how to implement it. Need your help.

 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))
   {
    // ???

    }

}

UPD(rewritten the code):

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

解决方案

In this example i expect that you know number of vertices in the graph in forward.

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
true w = 20
true w = 30
false

Storing graph with adjacency list representation leads to some information duplication, so it is good to have consistency checks.

这篇关于通过相邻顶点列表添加和减去图中的边的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！