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

Question

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

边缘列表是不合适的,因为获取顶点的邻居经常在我的代码中发生.

邻接列表并不好,因为我必须保留有关被访问边的信息,并且当访问1到3的边时(比如我遍历1的邻居并找到导致3并具有权重的边w),我必须在3的邻居列表中找到相同的边缘以将其标记为已访问,这很慢.

我已经考虑过邻接矩阵当每个小区将是set<Edge>其中Edge是表示关于如果顶点被访问信息的结构,重量边缘等.然而,具有当graph[0][1][i]为已访问我无法设置相同边缘中graph[1][0]的边缘没有线性搜索.

在表示多图时,有什么好的方法和技巧吗？我不想要第三个图书馆解决方案boost::AdjacencyList; 我必须自己写.

编辑:对不起有误.这是大学的练习,我只能使用标准库来完成它.该图有约束:0 <n≤300 - 顶点数0 <m≤20000 - 边数1≤w≤500

我的内存限制为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 ...
};

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

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

每个节点和每个链路所需的空间量是固定的，但开销可以或不可以，具体取决于应用程序（每个节点 4 个指针，每个链路 6 个指针）。使用简单列表而不是双链表，开销变为每个节点 2 个指针和每个链接 4 个指针，但链接删除O(outbound_deg(from) + inbound_deg(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))为节点分配空间。

通过这种方法，节点及其传出链接的所有数据都将位于相邻的内存位置。