Types of Graphs in Data Structure.

Graphs are non-linear data structures used to represent interconnected objects called vertices and nodes. A vertex represents a single entity in the graph, such as a person in a social network. An edge represents a connection between two vertices, such as a friendship between two people. We covered graph data structure in our previous post.

Here is the list of some common types of graphs:

1. Undirected Graph.

A graph in which edges have no direction associated with them is called an undirected graph. Example: A network of roads connecting various cities in a country.

2. Directed Graph.

A graph in which edges have a direction associated with them is called a directed graph or digraph. Example: A social network where people follow each other on Twitter.

3. Weighted Graph.

A graph in which edges have weights or costs associated with them is called a weighted graph. Example: A graph representing a road network where the weight of each edge could represent the distance between two cities.

4. Complete Graph.

A graph in which every pair of vertices is connected by an edge is called a complete graph. Example: A graph representing a round-robin tournament where every participant plays against another participant exactly once.

5. Cyclic Graph.

A graph in which all vertices are connected in a cycle is called a cyclic graph. Example: A graph representing a circular arrangement of objects.

6. Bipartite Graph.

A bipartite graph is a graph in which vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. Example: We have Set X = {A, B, C} and Set Y = {1, 2, 3, 4} and in the graph, the vertices of Set X are only connected with vertices of Set Y and visa-versa.

7. Tree.

A connected acyclic graph is called a tree. Example: A family tree representing relationships between members of a family.

8. Planar Graph.

A graph that can be drawn on a plane without any edges crossing is called a planar graph. Example: A graph representing a geographical map of a city.

9. Sparse Graph.

A graph with few edges compared to the maximum number of edges possible is called a sparse graph. Example: A graph representing a social network where most people are only connected to a few others.

10. Dense Graph.

A graph with many edges compared to the maximum number of edges possible is called a dense graph. Example: A graph representing a road network where most cities are connected to several others.