Mumbai University > COMPS > Sem 3 > Data Structures

Marks: 5 M

Year: May 2014, Dec 2013, Dec 2014

There are two common ways of representing a graph data structure on a computer. They are as follows:

a. Sequential Representation

• This kind of representation is achieved by using the adjacency matrix.
• Adjacency matrix is used to represent which nodes are adjacent to each other i.e is there a edge connecting two nodes on a graph.
• The adjacency matrix is of dimension n×n where n is number of nodes.
• If an edge is present from i to j then Aij =1 else the value will be set to 0. If it is a weighted graph, we replace 1 with the weight of that edge.
• The memory use of an adjacency matrix is $O(n^2)$ where is the number of nodes.

• The C language representation is given as:

  #define MAX 6
  void main()
  {   
  printf("Enter the adj matrix");
  for(i=0;i<MAX;i++)
  {
      for(j=0;j<MAX;j++)
      {
          scanf("%d",&adj[i][j]);
      }
  }
  }
  

• An example of adjacency matrix is shown below

b. Linked representation

• It is implemented using a adjacency list
• It contains a linked list of all nodes in the graph.
• Moreover, each node is in turn linked to its own list that contains names of all other
  nodes that are adjacent to it.
• Such kind of representation is often used for small to moderate sized graphs.
• A main disadvantage of adjacency matrix is that it is difficult to carry out insetion/deletion as it requires a lot of shifting operations in the matrix.
• Here we can easily insert or delete as we use linked lists.
• Such kind of lists are easy to follow and clearly shows the adjacent nodes of a node.

• The C representation is :

  struct node 
  {
  char vertex;
  struct node *next;
  };