c++ - 创建邻接表

Question

我正在学习创建邻接表，对此我还很陌生。我正在尝试在我的程序中测试一个。我想在链表中创建一个顶点，然后在该链表中创建一个列表或“边”。我在这里创建了一个链接，但不确定如何在链接列表中实际创建一个。我已经创建并测试了我的链接列表类，我知道它可以工作，我现在只需要创建一种方法来将其实现到邻接列表中。另外，我不能使用 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 类中有一个 neighbors 成员，我假设它包含指向相邻的其他 Vertex 的指针列表到这个。

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

您只需要实现 add()，将指针附加到您的链表。

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

你的家庭作业是:

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

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