Question: Define a graph. What are the methods to represent a graph?

Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

Marks: 3 M

Year: Dec 2014

modified 3.1 years ago  • written 3.1 years ago by gravatar for Yashbeer Yashbeer160
  • Graph is a non-linear data structure that is same as the mathematical (discrete mathematics) concept of graphs.
  • It is a collection of nodes(also called as vertices) and edges that connect these vertices.
  • Graphs are used to represent arbitrary relationship among objects.
  • A graph can be directed (where each edge has direction assigned to it with arrow-head) or undirected(no direction associated)
  • There are mainly two methods of representing graphs:

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 a edge is present from i to j then $A_{ij} =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.
  • An example of adjacency matrix is shown below

enter image description here

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.

enter image description here

written 3.1 years ago by gravatar for Yashbeer Yashbeer160
Please log in to add an answer.