Graphs : Introduction & Representation of Graphs with example

 Graphs : Introduction 

• A Graph is a non-linear data structure consisting of vertices and edges.  
• The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. 
• More formally a Graph is composed of a set of vertices( V ) and a set of edges( E ). 
• The graph is denoted by G(E, V). 

Representation of Graphs :-

--There are two ways to store a graph: 

• 1)Adjacency Matrix 

• 2)Adjacency List 

 

 

 

1)ADJACENCY MATRIX :

• 1)In sequential representation, there is a use of an adjacency matrix to represent the mapping between vertices and edges of the graph. 

 

• 2)If an Undirected Graph G consists of n vertices, then the adjacency matrix for that graph is n x n, and the matrix A = [aij] can be defined as - 

  aij = 1 {if there is a path exists from Vi to Vj} 

  aij = 0 {Otherwise} 

 

• 3)It means that, in an adjacency matrix, 0 represents that there is no association exists between the nodes, whereas  

2)ADJACENCY LIST 

• An adjacency list is used in the linked representation to store the Graph in the computer's memory. 
• It is efficient in terms of storage as we only have to store the values for edges. 
• We have an array of vertices which is indexed by the vertex number and for each vertex v, the corresponding array element points to a singly linked list of neighbours of v.