Каков эффективный способ реализации представления графа списком смежности в C ++?
На мой взгляд, это должен быть вариант 3 или 4, но я не нашел никаких минусов в его использовании ... Есть ли?
Может ли кто-нибудь помочь мне, что будет наиболее эффективным способом реализации списка смежности, а также для конкурентного программирования?
Каков эффективный способ реализации представления графа списком смежности в C ++
Многие типичные проблемы графа применимы к данному статическому графу, который необходимо будет представить один раз, после чего данное представление может быть повторно использовано при решении связанной проблемы. В этом случае std::unordered_map<int, std::vector<int>> - подходящая структура; где значение для данного ключа на неупорядоченной карте представляет (однонаправленные / двунаправленные) связанные вершины для данной вершины. Не должно быть причин использовать упорядоченный std::map вместо амортизированного контейнера постоянного поиска std::unordered_map.
Ассоциативные контейнеры std::unordered_map и std::unordered_set быстро ищут (что вам здесь нужно), но могут иметь последствия для производительности, если им нужно часто видоизменяться (например, для проблемы с динамическим графом). Как всегда, профилирование и измерение времени выполнения и памяти для поиска узких мест для реальной реализации проблемы являются ключевыми, если вы реализуете программу высокопроизводительных вычислений.
