基于链表的图，顶点可以有多个边吗？

Question

我正在考虑实现基于 linked 列表的图形的方法。但是，据我所知，linked 列表只能访问下一个列表（如果是双重列表，也可以访问上一个列表）并且图中的顶点可以访问任何其他顶点，除非它没有到某个顶点的边。这两个不同的特征打破了我构建图表的想法。

如果我的顶点（或节点）class（或结构）有指向另一个顶点的指针，

class Vertex
{
  Vertex *link; //edge to another veretex
  int item;     //item in vertex
}

我的图表 class 看起来像

class GraphClass
{
  Vertex **Graph;     //Graph itself
  int VertexQuantity; // number of vertex in graph
}

我可以使用函数 addVertex() 将顶点添加到图形中，但是当尝试连接两个顶点时，我开始失去理智。我考虑构建 addEdge() 函数的是

图中必须存在两个顶点
两个顶点还没有连接

下面的函数是我正在使用的 addEdge() 函数。

void addEdge(Graph *g, Vertex *source, Vertex *destination)
{
    unsigned index, sourceIndex;
    Vertex *temp;

    // if source or destination is not exist in graph
    if((sourceIndex = searchVertex(g, source) < 0 || searchVertex(g, destination) < 0))
        return;
    // if source and destination are already connected
    if(checkConnection(g, sourceIndex, source, destination) < 0 || sourceIndex < 0)
        return;

    temp = g->Graph[sourceIndex];
    temp->link = destination;
}

这是我的问题。比方说，v1 是顶点并连接到 v2。如果我想在v1和v3之间建立联系，我该怎么办？ v1 只有它的 link 指向某个顶点，如果我将顶点的下一个指针更改为数组以指向多个顶点，它打破了 linked 列表的规则。

Answer 1

通常这是通过拥有当前节点所连接的所有节点的链表来完成的。如果这太令人困惑，请从指向当前节点连接到的所有节点的向量或指针数组开始，然后使用链表实现 vector/array。

基于链表的图，顶点可以有多个边吗？

Linked list based Graph, Can vertex has a multiple edge?

c++

data-structures