Какова лучшая реализация для мультиграфа?

Question

Как по пространству, так и по стоимости эксплуатации, какой лучший способ реализовать мультиграф, имеющий больше ребер, чем вершин?

В худшем случае это будет 5000 ребер и 1000 вершин.Я думал о списке смежности, потому что он прекрасно подходит для большинства операций, таких как add edges, check adjacency between edges, add vertices (почти все время) и т. Д ...., но он все еще занимает пространство |v^2|.

Я на правильном пути?Есть ли лучшая реализация?Какие-нибудь советы по наилучшему способу реализации списка смежности?

Answer 1

Соотношение E/V = 5 означает действительно очень разреженные графики, что является плюсом для списков. В общем, списки смежности в целом лучше, чем матрицы смежности.

Теперь стоимость вставки составляет O(degree(vertex)), но с таким небольшим количеством ребер она будет незначительной. Не смотрите дальше, используйте списки смежности.