Graphs in Data Structures: Overview and Types

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.

• 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 (V₁, V₂), the edge is said to be directed from V₁ to V₂.
• The first element of the pair V₁ is called the start vertex and the second element of the pair V₂ is called the end vertex.

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.

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.