Different Types of Graphs in Data Structure

Introduction

A graph data structure defined is a non-linear data structure that has nodes and edges. A node in a graph has a value and all these nodes are interconnected with each other using vertices. Every graph has a finite set of nodes and vertices. Graphs are used to solve real-life problems.

Some of the real-world examples where a graph is implemented are telephone lines or a circuit network. The concept of a mutual friend on a social media platform like LinkedIn, Facebook, Instagram, etc. internally implements a graph.

We implement graphs in such a way that each node is a person in the network and it has attributes like id, name, age, etc.

Just like graph theory in mathematics, every graph is an abstract type that is directed or undirected. Depending on the basis of nodes and vertices, there are many types of graph data structures mentioned below -

Null Graph

A null graph contains zero order. In this type of graph, there exist nodes but no edges or vertices. It means, there is no interconnection between the nodes. All the nodes are isolated in a null graph.

If you want to import an item from a foreign to India, it is an example of the null graph as these are two different countries.

Trivial Graph

A graph that has only one vertex is known as a trivial graph. Such graphs have only one vertex and no edges.

Non-directed Graph

A graph is called non-directed if all the edges connected between the nodes have no connection flow between them. The edges are non-directed but connected.

For example, A, B, C, and D are nodes of a graph and they are connected in a circle but the flow of edges is not defined. It can be ABCD or BCDA or DCBA, etc.

Directed Graph

A graph is called directed when a flow of direction is defined between two nodes. These are also known as digraphs. In directed graphs, there is a predefined start point and an endpoint.

For example, A graph contains 4 nodes A, B, C, D. The directions are given are as follows -

A → B, B → C, C → D, A → C

If I want to go from A to D the path can be -

A → B → C → D or A → C → D

Connected Graph

A graph comes under the category of the connected graph when there is an interconnection between two graphs. In short, there must be a vertex via which we can traverse from one graph to another and so on.

For example, there are two graphs ABCD and EFGH. There is a vertex that connects Node D and Node E.

Disconnected Graph

A disconnected graph is just the opposite of a connected graph. A graph is said to be disconnected if there is no at least one edge that connects both the graphs. Both the graphs are separated and no interconnection exists between them.

From taking the example of a connected graph, if we remove the vertex that is connecting D and E. It then becomes a disconnected graph having two graph structures (ABCD and EFGH).

Regular Graph

A graph falls under the category of the regular graph if it follows at least one in the below two conditions -

a) The degree should be the same of all the vertices. If all the nodes of the graph have the same degree then it's called a regular graph.

b) Every vertex of the graph must be adjacent.

A graph is also called a ‘k-regular graph’ where k is the number of degrees all the nodes of the graph hold. For example, a graph having degree 6 is called a 6-regular graph.

Complete Graph

In a complete graph, each vertex in the graph is adjacent to all its vertices. It means there exists an edge connecting pair of vertices in a graph. A complete graph having n vertices has nC2 edges and this complete graph is represented as kn.

For example, if a graph has 3 vertices and each vertex has at least one edge with the rest of the vertices then it is a k3 graph.

Cyclic Graph

If a graph consists of at least one cycle it is called a cyclic graph. A cycle here represents the loops by which we can be redirected to the starting node while traversing through other nodes.

Acyclic Graph

A graph is called acyclic if there is no cycle present in it. For example, if we start from a node and do not return back to it while traversing in the graph, it is acyclic in nature.

Finite Graph

A graph is called a finite graph if a definite number of nodes and vertices exist in the graph. By finite, it means that the nodes and vertices present in the graph are countable.

For example, a graph ABCD has four nodes and four edges connected in a cyclic manner is a finite graph.

Infinite Graph

An infinite graph is defined as a graph in which the number of nodes and edges are uncountable.

Bipartite Graph

For a graph to fall under the category of a bipartite graph, the following conditions must be satisfied -

a) All the vertices of the graph should be divided into two distinct sets of vertices X and Y.

b) All the vertices present in the set X should only be connected to the vertices present in the set Y with some edges. That means the vertices present in a set should not be connected to the vertex that is present in the same set.

c) Both the sets that are created should be distinct, which means both should not have the same vertices in them.

Planar Graph

A graph is called planar if it can be embedded in the plane. It means that the graph is drawn in such a way that their edges intersect only at their endpoints. In this type of graph, no edges cross each other.

It is used in rotation systems and combinatorial maps.

Simple Graph

If a graph contains no self-loops and parallel edges, it is termed a simple graph. For example, A graph having nodes ABC and edges as A → B, B → C and C → A, is a simple graph.

Multi Graph

A multi-graph is somewhat similar to a simple graph. The difference here is that a multi-graph can have parallel edges and no self-loops. If there exists more than an edge for a node, it comes under the category of a multigraph.

Pseudo Graph

A graph is called a pseudo graph if it contains self-loops but no parallel edges. A self-loop here is whose starting and endpoint is the node only.

For example, A graph has nodes ABC and edges as A → B, B → C and C → A, and a self node from A → A is a pseudo graph.

Euler Graph

A graph is termed a Euler if all the vertices in the graph have a degree. In other words, there is an edge associated with every node in the graph. To be an Euler graph, all the vertices should have an even number of degrees of the node.

To know in-depth about graphs read this article by Scaler Topics.

Conclusion

Graphs in Data structure have a variety and so is the application. There are several sorts of graphs each having different properties. It is used in computer networks, computational devices, sociology, geometry, conservation, and other fields. The most common uses of graphs are as follows:

• To demonstrate the flow of computation graphs are used.
• In google maps, graphs are used to locate the shortest distance by using Prim's and Kruskal's algorithms.
• Facebook mutual friend connection is an example of an undirected graph.
• Maps can be represented by graphs to show the roadways between various locations.