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.
