Facebook

Representation of Graphs

Graphs can be represented by

  • Adjacency Matrix by Sequential Representation
  • Linked Representation by using an adjacency list that stores neighbors of a node using linked list.

Adjacency Matrix

  • It represents which nodes are adjacent to each other i.e. which nodes have edge connecting between them.
  • Rows and Columns are labeled by graph vertices.
  • a is the adjacency matrix,i represents row, j represents column,v i and vj represents vertices.
  • aij is 1 if  v i and vj are adjacent to each other and 0 if they are not.
  • Adjacency Matrix is also known as Bit matrix or Boolean Matrix since it contains only o's and 1's.

 

Undirected Graph

The graph is shown in Fig 1 and matrix is shown in Fig 2.

Fig 1 : An Undirected Graph
Fig 1 : An Undirected Graph
Screen Shot 2014-05-13 at 2.31.29 PM
Fig 2 : Adjacency Matrix of Fig 1

 

Directed Graph

The graph is shown in Fig 3 and matrix is shown in Fig 4.

Screen Shot 2014-05-13 at 12.58.35 PM
Fig 3 : An Undirected Graph
Screen Shot 2014-05-13 at 2.29.56 PM
Fig 4 : Adjacency matrix of Fig 3

 

 

Weighted Graph

The graph is shown in Fig 5 and matrix is shown in Fig 6.

 

Screen Shot 2014-05-13 at 2.37.22 PM
Fig 5 : A Weighted Graph
Screen Shot 2014-05-13 at 2.39.24 PM
Fig 6 : Adjacency matrix of Fig 6

 

 

Adjacency List

It is an another way to represent graphs in computer memory.It is a linked representation in which every node is linked to its own list that contains he names of all other nodes which are adjacent to itself.The graph is shown in Fig 7 and list is shown in Fig 8.

Screen Shot 2014-05-09 at 4.28.14 PM
Fig 7 : A Graph
Screen Shot 2014-05-13 at 3.55.37 PM
Fig 8 : Adjacency list of Fig 7

 

Advantages of Adjacency List

  • It clearly shows the adjacent nodes of a particular node.
  • Adding new nodes in the list is easy as compared to adding nodes in the adjacency matrix.
Rate this post

Comments

So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar