创建邻接表

Question

我正在学习创建邻接表，对此我还很陌生。我正在尝试在我的程序中测试一个。我想在链表中创建一个顶点，然后在该链表中创建一个列表或 "edge"。我在这里创建了一个链接，但不确定如何在链接列表中实际创建一个。我已经创建并测试了我的链接列表 class 并且我知道它有效，我现在只需要创建一种方法将其实现到邻接列表中。另外，我不能使用 C++ 库中的任何列表函数。

我的代码是否朝着正确的方向前进？

#include "Vertex.h"

Vertex::Vertex(){
    neighbors = new LinkedList();
    discover = 0;
    finish = 0;
    pi = NULL;
    color = "white";
}

Vertex::~Vertex(){
   delete neighbors;
}

void Vertex::insert(Vertex* vertex){

    LinkedList *temp = new LinkedList();

if(index == 0){
    temp->insertElement(vertex);
    index++;
    if(index != 0){
        neighbors->insertElement(vertex);
    }
}

} 这是我的主要。提前致谢！

 #include <cstdlib>
#include <iostream> //to use cin and cout
#include <string> //to use strings
#include "LinkedList.h"

using namespace std;

int main (){

Vertex *vertex1 = new Vertex();

for (int i =0; i < 10; i++){
   vertex1->insert(vertex1);
}

编辑修复了一些问题

Answer 1

最直接的方法是每个顶点的 LinkedList 将包含该顶点与之相邻的所有其他顶点的列表。

你没有提供你的LinkedList实现的细节，我推测你的insert()方法的目的是记录两个顶点相邻，this相邻vertex 参数。

如果这些假设是正确的，那么我希望您的 insert() 方法应该如下所示：

void Vertex::insert(Vertex* vertex)
{
    neighbors->add(vertex);
    vertex->neighbors->add(this);
}

您在 Vertex class 中有一个 neighbors 成员，我假设它包含一个指向其他 Vertex 与此相邻的指针的列表.

因此，要记录两个顶点彼此相邻，您必须在另一个顶点的neighbors方法中记录每个顶点。

您只需实施 add()，将指针附加到您的 linked 列表。

现在，当您需要查找与给定 Vertex 相邻的所有顶点时，您只需遍历其 neighbors link 列表中的顶点。因此，迭代对中的每个顶点最终也会包含另一个顶点。

你的家庭作业是：

1) 你的析构函数不完整。仅当您始终删除矩阵中的所有顶点时，简单地删除 neighbors 成员才有效。如果您希望能够从邻接矩阵中删除顶点，但仍保留其余部分，您显然需要从所有 neighbors 列表中删除 Vertex 被销毁 Vertex被破坏的顶点与之相邻。

2) 一些基本的错误检查，如果您的代码试图 link 两个相邻的顶点，它们已经被 link 编辑为彼此相邻，那么做一些明智的事情。

创建邻接表

Creating an adjacency lists

c++

linked-list

adjacency-list

data-structures