11

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

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

邻接列表不好，因为我必须保留有关已访问边的信息，并且当访问从 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 遍历）。

4

1 回答 1

4

一个有点复杂但提供高效本地操作的表示如下

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，并且还具有包含它的两个列表的 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))不再是恒定的。

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

甚至可以拆分链接对象以将前向链接数据嵌入到“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))为节点分配空间。

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

于 2012-12-24T15:09:23.170 回答