Ответ 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, а также содержит предыдущие и следующие указатели для двух списков, которые его содержат (исходящий список в "от" node и входящий список от "до" node).
Используя этот подход, вы получаете O(1) node и создаете и уничтожаете связь, O(inbound_deg(node)), чтобы найти, какие ссылки прибывают в node, O(outbound_deg(node)) для нахождения ссылок, которые выходят из node. Структура также поддерживает несколько соединений между одной и той же парой узлов, а также несколькими циклами.
Требуемое пространство - фиксированная сумма за node и для каждой ссылки, но накладные расходы могут быть в порядке или нет в зависимости от приложения (4 указателя на node и 6 указателей на ссылку).
Используя простые списки вместо двусвязных списков, служебные данные становятся 2 указателями на node и 4 на ссылку, но удаление ссылок становится O(outbound_deg(from) + inbound_deg(to)) и больше не является константой.
Обратите также внимание на то, что показанная структура не кэширована, и в современных настольных компьютерах может быть более "грубой силы", например, например, векторы указателей вместо двусвязного списка могут обеспечить более высокую скорость в зависимости от того, насколько велика будет список и как часто вы мутируете структуру графика.
Возможно, даже имеет смысл разделить объект ссылки, чтобы вставлять данные прямой линии связи, например, в "from" node, сохраняя обратные указатели в диапазоне от "до" node.
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 ...
};
Если вы больше всего путешествуете по ссылкам в прямом направлении, и если ссылки не добавляются к существующим узлам, то еще лучше будет просто использовать один кусок памяти для node и данных исходящей связи, но это, к сожалению, не легко поддерживается С++.
В 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)), чтобы выделить пространство для node.
При таком подходе все данные для node и его исходящих ссылок будут находиться в соседних ячейках памяти.