将边添加到使用链表实现的有向图(邻接列表)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

你正在打破你的列表。 当您插入边缘时。所以你的第一种情况总是有效的。你只需添加 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;
   }
}