EDUCBA Logo

EDUCBA

MENUMENU
  • Explore
    • EDUCBA Pro
    • PRO Bundles
    • Featured Skills
    • New & Trending
    • Fresh Entries
    • Finance
    • Data Science
    • Programming and Dev
    • Excel
    • Marketing
    • HR
    • PDP
    • VFX and Design
    • Project Management
    • Exam Prep
    • All Courses
  • Blog
  • Enterprise
  • Free Courses
  • Log in
  • Sign Up
Home Data Science Data Science Tutorials Data Structures Tutorial Types of Graph in Data Structure
 

Types of Graph in Data Structure

Savi Jagga
Article bySavi Jagga
EDUCBA
Reviewed byRavi Rathore

Updated March 23, 2023

Types of Graph in Data Structure

 

 

Introduction to Graph in Data Structure

A graph(V, E) is a set of vertices V1, V2…Vn and set of edges E = E1, E2,….En. Here, each distinct edge can identify using the unordered pair of vertices (Vi, Vj). 2 vertices Vi and Vj are said to be adjacent if there is an edge whose endpoints are Vi and Vj. Thus E is said to be a connect of Vi and Vj. Let’s discuss various types of graph in the data structure below.

Watch our Demo Courses and Videos

Valuation, Hadoop, Excel, Mobile Apps, Web Development & many more.

  • Order of the graph = The number of vertices in the graph.
  • Size of the graph = The number of edges in the graph.
  • Degree of a vertex of a graph = Number of edges incident to the vertex.

Graph Types1

Different Types of Graph in Data Structure

Following are the 17 different types of graph in the data structure explained below.

1. Finite Graph

A graph G= (V, E) in case the number of vertices and edges in the graph is finite in number.

Graph Types1

2. Infinite Graph

A graph G=(V, E) is said to infinite if the number of edges and vertices in the graph is infinite in number.

Graph Types3

3. Trivial Graph

A graph G= (V, E) is said to be trivial if there only exist single vertex in the graph without any edge.

Graph Types4

4. Simple Graph

A graph G=(V, E) is said to be a simple graph if there is one and only one edge between each pair of vertices. Thus there is only edge connecting 2 vertices and can be used to show one to one relationships between 2 elements.

Graph Types5

5. Multi Graph

A graph g= (V, E) is said to be a multigraph if there are multiple edges between a pair of vertices in the graph. A Multigraph does not contain any self-loop. For example, A Road Map.

Two kinds of edges exist in such scenarios:

  • Parallel Edges: Edges those are running parallel while going from a vertex Vi to Vj denoting parallel roads for going from one source to the same destination.
  • Loop: This denotes an edge whose source and destination vertices are the same.

Graph Types11

6. Null Graph

It is a modified version of a trivial graph. A graph G= (V, E) is said to a null graph if there are n number of vertices exist, but no Edge exists that connects then. This is the same as ordering food from a different city or farther places.

  • Order of G = n
  • Size of G = 0

Graph Types13

7. Complete Graph

A graph G= (V, E) is said to be a complete graph in case it is also a simple graph. With this n number of vertices must be attached to each of other vertices using the edges. It is also known as a full graph, and the degree of each vertex must be n-1.

Graph Types6

8. Pseudo Graph

A graph G= (V, E) is said to pseudo graph in case it contains a self-loop along with other edges.

Graph Types12

9. Regular Graph

A graph G= (V, E) is said to be a regular graph if it is a simple graph with each vertex of the graph having the same degree. Thus every complete graph is a regular graph.

Graph Types6

10. Bipartite Graph

A bipartite graph is having a set of vertices that can be partitioned into 2 non-empty disjoint subsets such that every edge of that graph has its endpoints from each of these subsets, i.e. lets V1 and V2 are subsets then each edge e between x and y vertices exist such as x ∈ V1 and y ∈ V2. V1 and V2 must be mutually exclusive as well as disjoint.

Here in the figure:
V1(G)={V5, V4, V3}
V2(G)={V1, V2}

Graph Types15

11. Labelled Graph

A graph G= (V, E) is said to be a labelled or weighted graph because each of the edges in the graph holds some value or weight that denotes traversal cost through that edge.

Graph Types7

12. Digraph Graph

A graph is said to a digraph or directed graph in case the order of pair of vertices changes the meaning of the graph. i.e. in case, G=(V, E) is the graph and Vi, Vj is a par of vertices is different from Vj, Vi. This can be seen in road maps when one of the roads is unidirectional or one-way. To denote such kind of cases directed graph is used. For each edge e between (Vi, Vj), an arrow exists to denote its direction.

Here in the figure:
e1 = (V1, V2)
e2 = (V2, V3)
e4 = (V2, V4)

Type of Graph - Digraph Graph

13. Subgraph

A graph G1 =(Vx, Ex) is said to be a subgraph of G=(V, E) if Vx ⊆ V and Ex ⊆ E.

Type of Graph - Subgraph

There are 2 Types of Subgraph

  • Vertex Disjoint Subgraph: A subgraph with no common vertex.
  • Edge Disjoint Subgraph: A subgraph with no common edge.
Note: Edge disjoint subgraph is always a vertex disjoint subgraph, but vice versa is not true.

Graph Types10

14. Connected or Disconnected Graph

In case one can find a path from one vertex of the graph to any of the other vertex, then the graph is said to be a connected graph. Thus a null graph is said to a disconnected graph as there is no edge connecting the vertices.

(A) – Connected Graph

Types of Graph - Connected Graph

(B) – Disconnected Graph

Types of Graph - Disconnected Graph

15. Cyclic Graph

A graph G= (V, E) is said to be a cyclic graph when one can reach its own while traversal. i.e. if V1, V2, and V3 are vertices in the graph then, there always exist edges connecting (V1, V2) and (V2, V3) and (V3, V1).

16. Vertex Labeled Graph

The graph that holds some data in its vertices, such as it can help to determine the edges data like (key, value) pair mapping.

Types of Graph - Vertex Labeled Graph

17. Directed Acyclic Graph

It’s also known as DAG, these are the graphs with directed edges, but they do not contain any cycle. Vertices also hold some data, and as it is directed; thus, edges are represented using an ordered pair of vertices.

Types of Graph in Data Structure

Conclusion

Graphs are an important data structure used in many algorithms to improve an application’s efficiency. There are many types of graphs, and their usage depends on the requirement of the application. At every step, data is analyzed and how the application is required to work helps to determine the suitable graph for running an algorithm. This improves the efficiency of the system a lot.

Recommended Articles

This is a guide to Types of Graph in Data Structure. Here we discuss the basic concept with the top 17 types of a graph in the data structure. You may also look at the following articles to learn more-

  1. Top 6 Types of Tree in Data Structure
  2. Top 5 Graphs in R with Examples
  3. How to Create a Queue in Data Structure?
  4. Guide to Searching in Data Structure

Primary Sidebar

Footer

Follow us!
  • EDUCBA FacebookEDUCBA TwitterEDUCBA LinkedINEDUCBA Instagram
  • EDUCBA YoutubeEDUCBA CourseraEDUCBA Udemy
APPS
EDUCBA Android AppEDUCBA iOS App
Blog
  • Blog
  • Free Tutorials
  • About us
  • Contact us
  • Log in
Courses
  • Enterprise Solutions
  • Free Courses
  • Explore Programs
  • All Courses
  • All in One Bundles
  • Sign up
Email
  • [email protected]

ISO 10004:2018 & ISO 9001:2015 Certified

© 2025 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA Login

Forgot Password?

🚀 Limited Time Offer! - 🎁 ENROLL NOW