Quick Facts

  • Represents graph with “V” nodes into a \(V x V\) binary matrix.
  • A 1 means the two vertices are connected; and a 0 means they are not connected.

Pros:

  • Easy to implement.
  • Adding and removing an edge, and checking whether there is an edge from one vertex to another is very efficient. Time complexity is \(O(1)\).
  • Good choice of implementation if the graph is dense and there are a large number of edges.
  • By performing operations on the adjacency matrix, we can get important insights into the nature of the graph and the relationship between its vertices.

Cons:

  • Takes up \(O(V^2)\) space. For large graphs, too much memory is consumed. Most real world applications for graphs do not have many connections. Therefore, in these situations, too much space is wasted.
  • Adding vertex takes \(O( V^2 )\) time.

References

Leave a Reply