Graphs: Adjacency Matrix

What is adjacency matrix

• It is one of the ways of implementing the graph.
• It's also called 2D-array.

How the connections are represented

• Here John is connected to Mary,Bob, and Alice.
• Adjacency matric is easy to implement. All we need is a 2-dimensional array.

Operations of adjacency matrix

Operation->Adding a Vertex

• Here we create a new matrix with one extra row and one extra column.
• Then copy all the elements from the old matrix to a new matrix.
• There are n-items and add operation is n2.
• ADD-OPERATION is V2

Operation->Removing a Vertex

• Here also, We need to create a new smaller matrix and copy the elements
• This is also O(V2)

Operation->Adding an Edge

• Here we store the item and their index in the HashMap.
• So we will get the position of the index of them and map the position of the edge.
• Adding the edge is also O(1).

Operation->Removing an Edge

• Removing the edge is also O(1).

Operation->Finding all the nodes adjacent to a node or the nodes that are directly connected to that node

• First we will use the HashTable to find the index of the Alice which is 3.
• Then we check every item in this row to find the connected nodes.
• So finding the neighbors runs in O(V).

Complexities reference

Problems with Adjacency Matrix

• The problem with adjacent matric is the size needed to allocate the nodes.
• Say there are n-items in the matrix ---> The space-complexity is O(n2).
• If the matrix has 1000 nodes the entries would be 1000000 entries.