Эффективная структура данных для представления графика

Question

Я должен реализовать ориентированный граф (орграф), который может иметь несколько дуг (мультиграф), как в связанном изображении.График должен быть оптимизирован для обработки большого количества узлов, но нескольких ребер между двумя из них.График должен часто обновляться, и он должен поддерживать эффективный поиск пути.Какая структура данных эффективна для компромисса между используемым пространством и временем для запроса?Язык стандартный C (только libc).

пример графика

Answer 1

Предположим, у вас есть NODE_COUNT узлы.Вы создаете вектор GRAPH длины NODE_COUNT.На записи X у вас есть массив переменного размера (динамически распределяемый).Каждая запись выглядит как GRAPH[X]=[A1, A2, A3] для представления ребер { (X,A1), (X,A2), (X,A3) }.

Если вам нужно выполнить поиск некоторых ребер, также удобно использовать двоичное дерево поиска для записи GRAPH[X].Если у вас есть более 6 ребер для каждого узла, вы также можете рассмотреть эту возможность вместо использования неупорядоченного массива в позиции GRAPH[X].

Поскольку граф имеет много узлов и мало ребер, вы не должны использоватьматрица.

Если у вас миллионы или миллиарды узлов, проблема в другом, и вам следует подумать об использовании BDD .Это другая тема, я не вхожу в подробности в этой теме.Идея состоит в том, что граф может быть представлен как характеристическая функция множества, представляющего граф.

Answer 2

Вы можете использовать Матрицу Смежности. По сути, это двумерный массив, который показывает список смежности.

Вот пример. Я считаю, что они довольно быстрые, требуется it (1) времени, чтобы определить, существует ли ребро на графике.

Это было бы хорошо, если бы «частое обновление» относилось к обновлению ребер, поскольку для обновления одного из значений требуется постоянное время. (т.е. добавление ребра (3, 2) займет постоянное время, потому что вы просто увеличите значение на 3,2 в матрице)

Для определения кратчайшего пути лучше всего подойдет алгоритм Дейкстры.