c++ - 向使用 C++ 中的链表实现的有向图(邻接表)添加边

Question

我进行了搜索，但找不到与我的案例相关的任何内容。

我只想使用链表在 C++ 中实现一个图。我的结构如下:

---

 class Vertex
 {     
     public:
     Vertex(std::string name = "none");
     private:
         std::string name;
         Edge *edges;
         Vertex *next;
         Runnable *runnables;
};

---

 class Edge
 {
     public:
          Edge();
     private:
         Vertex *connectsTo;
         Edge *next;
 };

---

 class TaskGraph{
      public:
           TaskGraph();

      private:
           Vertex *head;
 };

---

我有一种方法可以将顶点添加到图中 void addVertex(TaskGraph* taskGraph, const std::string&);

这种方法效果很好，因为我可以打印出图中的所有顶点。另一方面，为了添加有向边，我做了这样的事情:

 void MyGraph::addEdge(TaskGraph* taskGraph, const string& src, const string& dest){

      //get to the source vertex: this is ok
      //get to the destination vertex: this is also ok 


      //add edge : the problem is here // s is source vertex while d is destination vertex.
      Edge *e = new Edge;
      e->connectsTo = d;
      if(s->edges == 0){
           s->edges = e;
      }else{
           s->edges->next = e;
      }
 }

在添加说 5 条边 之后，实际上只添加了两条(即第一条边和列表边，其他边被替换)。我发现这是因为这一行:“s->edges->next = e;”但无法弄清楚如何正确实现它。请帮忙!!!

谢谢

Answer 1

你打破了你的 list 。当你插入边缘时。所以你的第一个案例总是有效的。你只需添加 e 就是你的优势。

另一种情况将添加 e 作为第二条边，但会丢失之前添加的所有其他边。

试试这个:

  //add edge : the problem is here
  Edge *e = new Edge;
  e->connectsTo = d;
  //If there is already a list node pointing to in s->edges...
  if(s->edges != 0){
      //Then apply the existing list to the back of the new node.
      // this add the exiting edges to the new one so you do not break the list.  
      e->next = s->edges;  
  }
  //Apply e as the head of the list (pointing to it via s->edges).
  s->edges = e;

此算法将新边添加到列表的前面，因此它们将以与您添加它们的顺序相反的顺序出现。

要保持边的顺序与插入时的顺序相同，您可以按照下面的建议进行循环或为列表中的最后一条边添加尾指针。

这里最重要的是您了解自己哪里做错了。

你开始于

 S->edges->NULL

你添加了一条边 E1 你得到了

 S->edges->E1.next->NULL

现在您添加了第二条边 E2 并且:

 S->edges->E1.next->E2.next->NULL

到目前为止一切顺利。但是，当您添加 E3 时，发生了什么:

 S->edges->E1.next->E3.next->NULL        lost link to  E2.next->NULL

这就是为什么无论您尝试添加多少边，您的列表中都只有 2 条边。它也称为内存泄漏，因为您丢失了对 E2 实例的所有引用并且无法清理这些对象。

好的，这就是其他人在下面的评论中谈论的关于如何使列表与您添加的边保持相同顺序的示例实现。所以 E1 是第一个 E2 第二个，等等......:

class Vertex
{     
    public:
       Vertex(std::string name = "none");
    private:
       std::string name;
       Edge *edges;
       Edge *lastEdge;  // this will keep track of the last edge in the list. 
                        // with this pointer you avoid having to loop through all
                        // the edges every time to add to the end.
       Vertex *next;
       Runnable *runnables;
};

void MyGraph::addEdge(TaskGraph* taskGraph, const string& src, const string& dest)
{
   //get to the source vertex: this is ok
   //get to the destination vertex: this is also ok 


   //add edge : the problem is here // s is source vertex while d is destination vertex.
   Edge *e = new Edge;
   e->connectsTo = d;
   if(s->edges == 0)
   {
        s->edges = e;
        // set the last edge to point to the first item.
        s->lastEdge = e;
   }
   else
   {
       // In this case the logic is simple you already know that
       // the list is not empty and that lastEdge is pointing at the
       // last edge in the list so just make the current lastEdge
       // point to the new edge. This will grow your list with e at 
       // the end.
       // Then update lastEdge to point to the new edge you just added.
       // so that is it pointing to the end of the list again. 
       s->lastEdge->next = e;
       s->lastEdge = e;
   }
}