Representation of Graph

Introduction of Representation of Graph

• Graphs are believed to be a way of expressing relationships between pairs of items and are one of the most important abstractions in computer science.

Definition

• The representation of a graph is a way to store graphical format inside the computer’s memory in the binary form either statically or dynamically.

Characteristics

• The representation of the graph occurs in sequence in memory.

Types

• There are two common ways to represent graphs in a computer’s memory. These are as follows:-
  • Adjacency matrix(as Array)
  • Adjacency list(as Linked List)

Adjacency Matrix

• • Adjacency Matrix is the representation of a graph inside memory in the form of a 2D array/matrix of size V x V (where V is the number of vertices available in a graph).
  • An adjacency matrix is applied for both directed or undirected as well as weighted or non-weighted graphs.
  • The adjacency matrix for undirected graphs is always symmetric.
  • In a weighted graph, adj[i][j] = w  i.e., there is an existence of edge from vertex i to vertex j with weight value w in their matrix representation but for non-weighted graph instead of weight values we use 1s for edge existing and 0s for no edge existing.
  • It is easier to implement and follow.
  • The matrix representation easily determines the connection of vertices in the graph.
  • This representation consumes more space O(V²).

Adjacency Lists

• • Adjacency Lists is the representation of a graph inside memory in the form of an array of Linked Lists.
  • An array of lists is used. The size of the array is equal to the number of vertices.
  • Adjacency Lists are applied for both directed or undirected as well as weighted or non-weighted graphs.
  • The weights of edges can be represented as lists of pairs.
  • This representation saves memory space and time.
  • It can be represented in two forms. In one form, the array is used to store n vertices, and the chain is used to store its adjacencies/edges.
  • Adding a new vertex/data value is easier in adjacency lists.
  • Traversing all the neighbors’ vertex from a source takes optimal time.

Use/Application

• The Graph representation is used in statistical work to determine, relate, and compare different data. This gives various information in facts and figures for analysis