Learnerslesson
   JAVA   
  SPRING  
  SPRINGBOOT  
 HIBERNATE 
  HADOOP  
   HIVE   
   ALGORITHMS   
   PYTHON   
   GO   
   KOTLIN   
   C#   
   RUBY   
   C++   
   HTML   
   CSS   
   JAVA SCRIPT   
   JQUERY   




ADJACENCY MATRIX DATA STRUCTURE


Adjacency Matrix Data Structure is another implementation fo Graph that is the most easy data structure to understand.


Let's understand with the below undirected graph :


java_Collections

Let us suppose, there are 5 vertices. a, b, c, d and e.


Now, there is an edge between 'a' and 'b' or 'b' and 'a'. i.e. (a,b) or (b,a).


Similarly, there are other edges like (a,c) or (c,a), (c,e) or (e,c), (e,b) or (b,e), (e,d) or (d,e), (d,c) or (c,d) and (d,a) or (a,d).


Now, we will see an elegant solution to represent the edges.


java_Collections

If you look at the extreme left, you can find, each row is represented by a vertex (i.e. a, b, c, d and e).


Again, if you have a look at the top. Each column is also represented by a vertex (i.e. a, b, c, d and e).


Now, if you look at the intersection of a row and column. You can find the number '1' represents an edge and number '0' represents there is no edge.


Say for example, we know that there is an edge between a and b or b and a.


So, if we look at the intersection of a and b. We can find the number '1' in it.


java_Collections

Similarly, if we see the intersection of b and a. We can also find the number '1' in it.


java_Collections

Now, we know that there is no edge between b and c. So, if you check the intersection, you can find number '0' in it.


java_Collections

Now, just pause! Think for a moment!


Can the above structure in the form of a 2D array?


Yes, off course we can.


For our convenience, let us represent the vertices in the form of numbers.


Say,


a - 0
b - 1
c - 2
d - 3
e - 4

So, let us change the graph in the same form.


What I meant was instead of a, b, c, d and e. Let us represent it as 0, 1, 2, 3 and 4.


And the graph becomes :


java_Collections

And the below Adjacency Matrix becomes :


java_Collections

Now, can we represent the above as a 2d array?


If the name of the array is 'arr'. Then arr[0,1] has the number 1. That represents an edge between.


Similarly, there is an edge between vertex 0 and 3. And arr[0,3] has the number 1 in it.


What would be the space needed for Adjacency Matrix Data structure?


Just think for a moment. Although there is just 1 edge in a graph, still you have to construct a 2D array as mentioned above.


As the edge that is present will be represent by the number '1' and the even though there is no edge. We still have to represent it with number '0'.


Space needed for Adjacency Matrix Data Structure : O(n)


What would be the time required to search or remove an edge?


To remove an edge just go to that edge and set it to '0'.


Example :


If you want to remove an edge from 3 to 4.

Just go to arr[3][4] and initialise with 1.

Similarly to search if an edge is present or not. You need to go to that edge and check if the value is '1' or not.

Example :


If you want to check, if there is an edge from 3 to 4.

Just go to arr[3][4] and check if it has '1' in it or not.

Time needed for Adjacency Matrix Data Structure to search or remove an edge : O(1)


Note :If your space is not a constraint then the Adjacency Matrix Data Structure is the best representation of Graphs.