c++ - 表示 multimap 的良好数据结构(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 ...
};

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

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

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

另请注意，显示的结构不是缓存友好的，在现代台式计算机中可能是一种更“蛮力”的方法，例如指针 vector 而不是双向链表可以提供更好的速度，具体取决于列表的大小以及您改变图结构的频率。

拆分链接对象以嵌入前向链接数据甚至可能是有意义的，例如在“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)) 为节点分配空间。

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