Лучший способ реализовать граф в C ++?
Я пытаюсь реализовать постоянный, неупорядоченный, невзвешенный, разреженный граф (т. Е. Ребра не двигаются). Тем не менее, я буду выполнять множество операций по замене вершин, в результате чего порядок вершин меняется.
Например, один из способов — использовать вектор unordered_sets + структуру списка смежности:
0: 1 2 3
1: 0 2
2: 0 1
3: 0
поменяйте местами 0 и 3:
0: 3
1: 3 2
2: 3 1
3: 1 2 0
Какова лучшая реализация в C ++?
Решение
Заглянуть в Boost Graph Library. Вероятно, он будет работать для ваших нужд, но если это не так, его документация может стать хорошей отправной точкой для изучения предмета, прежде чем вы начнете пробовать свои собственные.
Изменить: Если вы ожидаете работать с разреженными графиками, список смежности Версия, вероятно, реализация, которую вы хотите изучить в первую очередь. Обратите внимание, что вы можете настроить характеристики производительности графа boost adjacency_list, изменив базовые структуры данных, используемые для его реализации (через аргумент шаблона).
Редактировать: Что касается перестановки вершин, которую вы описываете, вероятно, самый простой способ сделать это — установить тип вершины, где вершина может оставаться на месте, но ее свойства можно легко поменять с другой. Комплексная недвижимость Механизм является одним из способов реализации этого.
Другие решения
повышение :: график возможно.
Он имеет несколько реализаций, и вы можете указать несколько параметров для каждой вершины. Дальнейшее исследование оставлено в качестве упражнения для студента.
detector