Graph is a data structure that consists of following two components:

  1. A finite set of vertices also called as nodes.
  2. A finite set of ordered pair of the form (u, v) called as an edge.

 

  • The pair is ordered because (u, v) is not same as (v, u) in the case of a directed graph(di-graph).
  • The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost.
    • V -> Number of Vertices.
    • E -> Number of Edges.

 

Graph Classification:

The graph can be classified on the basis of many things, below are the two most common classifications:

  1. Direction Graph:
    • Undirected Graph: The graph in which all the edges are bidirectional.
    • Directed Graph: The graph in which all the edges are unidirectional.
  2. Weight Graph:
    • Weighted Graph: The Graph in which weight is associated with the edges.
    • Unweighted Graph: The Graph in which there is no weight associated with the edges.

 

Time Complexities:

  • Time Complexities in a case of Adjacency Matrix:
    • Traversal :(By BFS or DFS) O(V^2)
    • Space: O(V^2)
  • Time Complexities in the case of Adjacency List:
    • Traversal :(By BFS or DFS) O(ElogV)
    • Space: O(V+E)

Examples :

  • Google map
  • Represent network
    • Telephone
    • Social Networking sites

Representations of Graph:

  1. Adjacency Matrix
    • It is a 2D array of size V x V where V is the number of vertices in a graph.
  2. Adjacency List
    • Implemented using array of linked list.
    • Size of the array is equal to number of vertices
    • Used to represent a weighted graph
      • Weights of edges can be stored in nodes of linked lists
  3. Incidence Matrix
  4. Incidence Lis