Data Structures-Graph Overview

Graph

A Graph is a non-linear data structure consisting of nodes and edges. The nodes are referred as vertices and the edges are lines or arcs that connect two nodes in the graph. The Graph can be also defined as,

A Graph consists of a finite set of vertices (or edges) and the set of Edges which connect a pair of nodes.

                                            

From the above graph,

  1. The set of Vertices in the graph is given by V = {A, B, C, D, E}.
  2. The set of Edges in the graph is given by E = {AB, BC, CD, DE, AE, AD, BD}.

The following two are the most commonly used graph representations:

  • Adjacency Matrix
  • Adjacency List

The other representations of Graph are Incident Matrix and Incident List. The choice of the graph representation is based on the situation or requirements. 

Applications of Graph

  • Graphs are used to solve many real-life problems.
  • Graphs are used to represent networks. The network may include circuit network, paths in a city or telephone network.
  • Graphs are also used in social networks like Instagram, Facebook, LinkedIn, etc. For example, in Facebook, each person is represented with a vertex (or node). Each node is a structure and contains information like person id, name, location, current ciry, etc.