c++ - 有必要在向图形添加边的功能中进行检查

Question

我需要检查:

1) 我不插入现有边也就是说，如果我在图中有 5 个顶点 - 从 0 到 4 的索引，那么我不能通过索引 (0, 6) 添加反向

2) 检查避免插入相同的顶点但我不知道该怎么做才对

我的代码:

bool Graph::addEdge(const Edge& edge)
{
   if (edge.mStartIndex == edge.mEndIndex)
      return false;

  //if (mVertexList[edge.mEndIndex] != edge.mStartIndex)
    {
     mVertexList[edge.mStartIndex].emplace_back(edge.mEndIndex, edge.mWeight);
     mVertexList[edge.mEndIndex].emplace_back(edge.mStartIndex, edge.mWeight);
    }

    return true;
}

边缘:

struct Edge
{
  Edge(VertexIndex startIndex, VertexIndex endIndex, float weight);

  VertexIndex mStartIndex;
  VertexIndex mEndIndex;
  float mWeight;
};

 struct AdjacentVertex
{
    AdjacentVertex(VertexIndex index, float weight);

    VertexIndex mIndex;
    float mWeight;
};

class Graph
{
public:
   using AdjacencyList = std::vector<AdjacentVertex>;
   Graph(VertexIndex numVertices);

   VertexIndex numVertices() const;
   const AdjacencyList& adjacencyList(VertexIndex index) const;

   bool addEdge(const Edge& edge);
   void removeEdge(const Edge& edge);

   private:
     using VertexList = std::vector<AdjacencyList>;
     VertexList mVertexList;
};

Answer 1

1. 要检查边数是否不太高，您可以执行以下操作:

   if (edge.mStartIndex >= numVertices() || edge.mEndIndex >= numVertices()) 
   {
       // Handle situation when edge number is out of bound
   } 
   

2. 您可以使用find_if 检查邻接表是否已经包含这条边。 :

   auto it = std::find_if(
       mVertexList[edge.mStartIndex].cbegin(),
       mVertexList[edge.mStartIndex].cend(),
       [&edge](const AdjacentVertex& node) {
           /* Check if the current edge points to edge.mEndIndex */
           return node.mEnd == edge.mEndIndex;
       }
   );
   if (it != mVertexList[edge.mStartIndex].cend()) {
       // Handle situation when you already have this edge in the list
   }