What is better, adjacency lists or adjacency matrices for graph problems in C++?

by

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 more on the number of edges (and less on the 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)

More Related Contents:

  1. c++ error : Segmentation fault (core dumped)
  2. A proper way to create a matrix in c++
  3. Iterative DFS vs Recursive DFS and different elements order
  4. Cycles in family tree software
  5. Dijkstra Shortest Path with VertexList = ListS in boost graph
  6. Graph implementation C++
  7. Cut set of a graph, Boost Graph Library
  8. sizeof works unusual at c++ after array creation [duplicate]
  9. Unterminating c++ Program [closed]
  10. Where did I go wrong in my code for word count C++
  11. How can I read and parse CSV files in C++?
  12. Accessing an array out of bounds gives no error, why?
  13. Size of character (‘a’) in C/C++
  14. Pure virtual function with implementation
  15. Can I set a breakpoint on ‘memory access’ in GDB?
  16. Best C++ Code Formatter/Beautifier
  17. Fast ceiling of an integer division in C / C++
  18. Visual Studio 2015 “non-standard syntax; use ‘&’ to create a pointer to member”
  19. What C/C++ compiler can use push pop instructions for creating local variables, instead of just increasing esp once?
  20. structured bindings: when something looks like a reference and behaves similarly to a reference, but it’s not a reference
  21. Error: cannot bind non-const lvalue reference of type ‘int&’ to an rvalue of type ‘int’
  22. The Pimpl Idiom in practice
  23. “No appropriate default constructor available”–Why is the default constructor even called?
  24. How to break out of a loop from inside a switch?
  25. c++ sort with structs
  26. how to check string start in C++
  27. Can Google Mock a method with a smart pointer return type?
  28. How to convert a time into epoch time?
  29. C/C++: casting away volatile considered harmful?
  30. Error: undefined reference to `sqlite3_open’

Leave a Comment