struct Link;

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

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

基本上每个节点有两个双链表,一个用于传入链路,一个用于传出链接.每个链接知道起始和结束节点,并且还包含包含它的两个列表的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)),并且不再是常量.

还要注意,所示的结构不是缓存友好的,并且在现代台式计算机中可能是更加“强力”的方法,指针的代码而不是双向链表可以提供更好的速度,具体取决于列表的大小以及图形结构的变化频率.

拆分链接对象以将例如“从”节点中的前向链接数据嵌入到“从”节点中,将后向指针保留在“到”节点中甚至可能是有意义的.

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))来分配节点的空间.

使用这种方法,节点及其输出链路的所有数据将在相邻的存储器位置.