表示多图的良好数据结构(C++)

Question

描述无定向多图的最佳数据结构是什么（针对速度和内存进行了优化）？

一个边的列表是不合适的，因为在我的代码中，获取顶点的邻居经常发生。

邻接列表是不好的，因为我必须保留关于已访问边的信息，并且当从1到3的边被访问时（假设我遍历1的邻居，发现一条边通向3并且具有weightw)，我必须在3的邻居列表中找到相同的边以将其标记为已访问，这很慢。

当每个单元格都是集 时，我考虑过邻接矩阵，其中edge是表示顶点是否被访问、边的权重等信息的结构。然而，当访问图[0][1][i]时，如果不进行线性搜索，我就不能在图[1][0]的边中设置相同的边。

当表示多图时，有什么好的方法和技术吗？我不想要像boost：：邻接列表这样的第三库解决方案；我得自己写。

编辑：抱歉误会。这是大学的练习，我只能用标准图书馆来做。图具有约束条件:0

我的内存限制为32 MB，时间限制为0.5秒（我必须使用DFS遍历）。

Answer 1

下面是一个稍微复杂的表示，但它提供了有效的本地操作

struct Link;

struct Node
{
    Link *firstIn, *lastIn, *firstOut, *lastOut;
    ... node data ...
};

struct Link
{
    Node *from, *to;
    Link *prevInFrom, *nextInFrom, *prevInTo, *nextInTo;
    ... link data ...
};

基本上每个节点都有两个双链表，一个用于传入链接，一个用于传出链接。每个链接都知道开始和结束节点并且还具有包含它的两个列表（“From”节点中的传出列表和“To”节点中的传入列表）的prev和next指针。

使用此方法，您将获得O(1)节点和链接创建和销毁，O(inbound_deg(node))用于查找哪些链接到达节点，O(outbound_deg(node))用于查找哪些链接离开节点。该结构还支持同一对节点之间的多个连接以及多个循环。

每个节点和每个链路所需的空间是固定的，但是开销可以根据应用程序（每个节点4个指针，每个链路6个指针）而定。使用简单列表而不是双链表，开销变为每个节点2个指针，每个链接4个指针，但是链接删除变为O(outbound_deg(from)+inbound_deg(to))，并且不再是常量。

还要注意，所示的结构不是缓存友好的，在现代台式计算机中，可能是一种更“暴力”的方法，例如，指针的向量而不是双链表，可以提供更好的速度，这取决于列表的大小和更改图结构的频率。

甚至可以拆分link对象来嵌入前向链接数据，例如在“From”节点中，将后向指针保留在“to”节点中。

struct Node
{
    struct OutgoingLink
    {
        Node *to;
        int incoming_index;
        ... link data ...
    };

    struct IncomingLink
    {
        Node *from;
        int outgoing_index;
    };

    std::vector<OutgoingLink> outgoing_links;
    std::vector<IncomingLink> incoming_links;

    ... node data ...
};

如果您大部分时间都在向前遍历链接，并且链接没有添加到现有节点，那么更好的做法是只为一个节点和传出的链接数据使用一个内存块，但不幸的是，C++不容易支持这一点。

在C中是

typedef struct TOutgoingLink
{
    struct TNode *to;
    int incoming_index;
    ... link data ...
} OutgoingLink;

typedef struct TIncomingLink
{
    struct TNode *from;
    int outgoing_index;
} IncomingLink;

typedef struct TNode
{
    ... node data ...
    int num_incoming_links;
    int num_outgoing_links;
    IncomingLink *incoming_links;   // separate array
    OutgoingLink outgoing_links[1]; // embedded array starting here
} Node;

使用malloc(sizeof(Node)+(num_outgoing_links-1)*sizeof(OutgoingLink))为节点分配空间。