Graphs in Data Structures: Overview and Types

Rumman Ansari   Software Engineer   2024-07-05 06:01:06   7471  Share
Subject Syllabus DetailsSubject Details 2 Questions
☰ TContent
☰Fullscreen

Table of Content:

What is Graph?

  • Graph is an abstract data type.
  • It is a pictorial representation of a set of objects where some pairs of objects are connected by links.
  • Graph is used to implement the undirected graph and directed graph concepts from mathematics.
  • It represents many real life application. Graphs are used to represent the networks. Network includes path in a city, telephone network etc.
  • It is used in social networks like Facebook, LinkedIn etc.

Graph consists of two following components:

1. Vertices

2. Edges

  • Graph is a set of vertices (V) and set of edges (E).
  • V is a finite number of vertices also called as nodes.
  • E is a set of ordered pair of vertices representing edges.
  • For example, in Facebook, each person is represented with a vertex or a node. Each node is a structure and contains the information like user id, user name, gender etc.


graphs

  • The above figures represent the graphs. The set representation for each of these graphs are as follows:

Graph 1:

V = {A, B, C, D, E, F}
E = {(A, B), (A, C), (B, C), (B, D), (D, E), (D, F), (E, F)}

Graph 2:

V = {A, B, C, D, E, F}
E = {(A, B), (A, C), (B, D), (C, E), (C, F)}

Graph 3:

V = {A, B, C}
E = {(A, B), (A, C), (C, B)}

Directed Graph

  • If a graph contains ordered pair of vertices, is said to be a Directed Graph.
  • If an edge is represented using a pair of vertices (V1, V2), the edge is said to be directed from V1 to V2.
  • The first element of the pair V1 is called the start vertex and the second element of the pair V2 is called the end vertex.


directed graph

Set of Vertices V = {1, 2, 3, 4, 5, 5}
Set of Edges W = {(1, 3), (1, 5), (2, 1), (2, 3), (2, 4), (3, 4), (4, 5)}

Undirected Graph

  • If a graph contains unordered pair of vertices, is said to be an Undirected Graph.
  • In this graph, pair of vertices represents the same edge.


undirected graph

      Set of Vertices V = {1, 2, 3, 4, 5}

 

    Set of Edges E = {(1, 2), (1, 3), (1, 5), (2, 1), (2, 3), (2, 4), (3, 4), (4, 5)}
  • In an undirected graph, the nodes are connected by undirected arcs.
  • It is an edge that has no arrow. Both the ends of an undirected arc are equivalent, there is no head or tail.