EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Types of Graph in Data Structure
Secondary Sidebar
Data Structures Tutorial
  • Basics
    • Linked List Advantages
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Hashing in Data Structure
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Bitonic Sort
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Radix Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Priority Queue in Data Structure
    • Asymptotic Analysis
    • Tree Traversal in Data Structure
    • Tree Traversal Techniques
    • Trie Data Structure
    • Splay Tree in Data Structure
    • Spanning Tree Algorithm
    • Sparse Matrix in Data Structure
    • Radix Sort Algorithm
    • Counting Sort Algorithm
    • Skip List Data Structure
    • Linked List Algorithm
    • Linked List Types
    • Inorder Traversal of Binary Tree
    • Kruskals Algorithm
    • Prims Algorithm
    • BFS VS DFS
    • BCNF
    • Skip List
    • Hash Table?in Data Structure
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview
    • AVL Tree Deletion
    • B+ Tree Deletion
    • Decision Tree Advantages and Disadvantages
    • Data Architect Skills
    • Data Architecture Principles
    • Data Engineer Jobs
    • Data Engineer Roadmap
    • Fundamentals of Data Structure
    • Circular queue in Data Structure
    • Spanning Tree in Data Structure
    • Tree traversal types
    • Deque in Data structure
    • Shell Sort in Data Structure
    • Heap sort in data structure
    • Heap data structure C++
    • Heap data structure in Java
    • Binary Search Tree Types
    • Binary Tree in Data Structure
    • Binary Tree Types
    • Binary search tree in data structure
    • Binary Search Tree Advantages
    • Binary Search Tree Properties
    • Binary Search in Data Structure
    • Binary Tree Deletion
    • Sparse Matrix Multiplication
    • Preorder Traversal of Binary Tree
    • Postorder traversal
    • Decision Tree Hyperparameters
    • PostOrder Traversal without Recursion
    • AVL Tree Rotation
    • Avro File Format
    • Decision Tree Types
    • Binomial heap
    • Confluence Jira Integration
    • Timm Sort
    • Depth First Search

Related Courses

All in One Data Science Course

Oracle DBA Course

SQL Certification Course

Types of Graph in Data Structure

By Savi JaggaSavi Jagga

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.

  • 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.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

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.

All in One Data Science Bundle(360+ Courses, 50+ projects)
Python TutorialMachine LearningAWSArtificial Intelligence
TableauR ProgrammingPowerBIDeep Learning
Price
View Courses
360+ Online Courses | 50+ projects | 1500+ Hours | Verifiable Certificates | Lifetime Access
4.7 (86,471 ratings)

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
Popular Course in this category
Data Scientist Training (85 Courses, 67+ Projects)
  85 Online Courses |  67 Hands-on Projects |  660+ Hours |  Verifiable Certificate of Completion
4.8
Price

View Course

Related Courses

All in One Data Science Bundle (360+ Courses, 50+ projects)4.9
Oracle DBA Database Management System Training (2 Courses)4.8
SQL Training Program (7 Courses, 8+ Projects)4.7
0 Shares
Share
Tweet
Share
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

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

EDUCBA
Free Data Science Course

SPSS, Data visualization with Python, Matplotlib Library, Seaborn Package

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

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

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

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

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

By signing up, you agree to our Terms of Use and Privacy Policy.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more