Graph definition and declaration


What is a graph ?

The graph is a set of vertices connected with the help of edges. A graph may be directed or undirected, and all the vertices are connected to each other in the graph. We can represent a graph using an array of vertices and a two-dimensional array for edges. Basic operations we can perform on graphs are adding a vertex, displaying vertex, adding edges, etc.

Graph : The formal definition of a graph is that a graph is a set of items or nodes connected by edges.

Declaration of graph

The graph is declared or represented using the most common two ways :

  1. Adjacency matrix : Adjacency matrix is a 2D array that contains V*V, where V means the number of vertices in a graph. Adj[i][j] = 1 indicates that there is an edge between i and j vertices. An adjacency matrix is always symmetric for an undirected graph.
  2. Pros :Easy to implement and takes less time to process, like it takes o(1) to remove an edge.

    Cons :It takes much space even if there is less number of edges are there.

  3. Adjacency list :In the adjacency list, the array is used. The size of the array is equal to the number of vertices. This method is also used to represent weighted graphs.
  4. Pros : Saves the space.

    Cons : Queries can be done at o(v).