Какова лучшая структура данных для представления мультиграфа с использованием STL в C ++?

Question

Я ищу некоторую структуру данных для хранения мультиграфа в C ++, но я хочу максимально использовать STL.В настоящее время я использую нечто похожее на отдельную хэш-таблицу цепочки: std::map<int,std::vector<int>>.Ключом карты является вершина, а значением является std::vector<int>, который содержит все различные вершины, которые образуют ребро с ключом.

Меня в основном интересует поиск O (1), чтобы увидетьразделяет ли вершина ребро с другой вершиной.Поскольку это невзвешенный мультиграф, вершина может иметь несколько ребер с другой вершиной.

График гарантированно имеет эйлерово и гамильтонову контуры, но я не уверен, уместно ли это.

Ребята, есть ли у вас какие-либо рекомендации по улучшению структуры данных с использованием STL, чем std::map<int,std::vector<int>>?

Answer 1

Если число вершин N невелико, возможно, проще всего использовать матрицу смежности unordered_map<int, unordered_map<int, int>> graph, где graph[u][v] - это число ребер от u до v.

Если вашвсе числа вершин находятся в диапазоне от 0 до N – 1, или от 1 до N, или аналогичные, вы можете упростить это до vector<vector<int>> graph или даже int graph[][], если N известно во время компиляции.

Если N равнобольшой, и если график разреженный, как вы указали (так как M ≈ N), вероятно, лучше использовать набор для каждой вершины: unordered_map<int, unordered_set<int>> graph или vector<unordered_set<int>> graph, где graph[u] - это множество всех вершин v с ребром от u до v.

Обратите внимание, что я использую коллекции unordered_map и unordered_set, которые в среднем обеспечивают доступ O (1).В худшем случае их производительность линейна по размеру карты или набора, как и для любого контейнера на основе хеша.

И если вы не хотите со всем этим разбираться и хотите получить готовыйВ качестве решения используйте библиотеку графов ускорения, NGraph, LEMON или Google OR-Tools.