Что лучше, списки смежности или матрицы смежности для проблем графика в C++?

Если вы изучаете анализ графов в C ++, вероятно, первым делом стоит начать с библиотеки ускоренных графов , которая реализует ряд алгоритмов, включая BFS.

• Документы библиотеки графов ускорения

РЕДАКТИРОВАТЬ

Этот предыдущий вопрос по SO, вероятно, поможет:

как-создать-ac-boost-unirected-graph-and-traverse-it-in-depth- first-search h

It depends on the problem.

Adjacency Matrix

• Uses O(n^2) memory
• It is fast to lookup and check for presence or absence of a specific edge
  between any two nodes O(1)
• It is slow to iterate over all edges
• It is slow to add/delete a node; a complex operation O(n^2)
• It is fast to add a new edge O(1)

Adjacency List

• Memory usage depends on the number of edges (not number of nodes),
  which might save a lot of memory if the adjacency matrix is sparse
• Finding the presence or absence of specific edge between any two nodes
  is slightly slower than with the matrix O(k); where k is the number of neighbors nodes
• It is fast to iterate over all edges because you can access any node neighbors directly
• It is fast to add/delete a node; easier than the matrix representation
• It fast to add a new edge O(1)

Это зависит от того, что вы ищете.

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

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

Как правило, списки смежности являются правильной структурой данных для большинства приложений графов.