What is better adjacency lists or adjacency matrix for graph problems in c++?

Question

What is better adjacency lists or adjacency matrix for graph problems in c++? And what are the advantages and disadvantages of each?

EDIT:can anyone provide a link with a clean code for say Breadth first search in linked lists format ??

Answer 1

It depends on the problem.

An adjacency matrix uses O(n*n) memory. It has fast lookups to check for presence or absence of a specific edge, but slow to iterate over all edges.

Adjacency lists use memory in proportion to the number edges, which might save a lot of memory if the adjacency matrix is sparse. It is fast to iterate over all edges, but finding the presence or absence specific edge is slightly slower than with the matrix.

Answer 2

It depends on what you're looking for.

With adjacency matrices you can answer fast to questions regarding if a specific edge between two vertices belongs to the graph, and you can also have quick insertions and deletions of edges. The downside is that you have to use excessive space, especially for graphs with many vertices, which is very efficient especially if your graph is sparse.

On the other hand, with adjacency lists it is harder to check whether a given edge is in a graph, because you have to search through the appropriate list to find the edge, but they are more space efficient.

Generally though, adjacency lists are the right data structure for most applications of graphs.

Answer 3

If you are looking at graph analysis in C++ probably the first place to start would be the boost graph library, which implements a number of algorithms including BFS.

• Boost Graph Library Docs

EDIT

This previous question on SO will probably help:

how-to-create-a-c-boost-undirected-graph-and-traverse-it-in-depth-first-search