Ritika Khanduri

Posted on

# Graphs and Types of Graphs🔥

`Hello Everyone👋. It is my first time blogging. I love to write about programming and development.

Hope you will like it✨

So Let's Start the Journey with the Topic: - GRAPHS
What is Graph and Why is it important to know it?🤔

The graph is one of the most important topics for those preparing for placements and coding interviews as most companies ask graph questions during the coding rounds.

Graphs are non-linear data structures consisting of a finite set of vertices (i.e. nodes) connected by a set of edges.
An edge is a line which connects two vertices. It is defined by G = (V,E)

Do you know different types of the graph in DSA ?? 🤔.

• If Yes, that's great. Continue to Revise the concept ✌️

• If No, Let's Understand this 🔥

Types of Graphs

• Finite Graph - As the name suggests (Finite), it is a graph with a finite number of vertices and edges.

• Infinite Graph - It is a graph with infinite vertices and edges.

• Trivial Graph - A finite graph is a trivial graph if it has only one vertex. It does not have any edge.

• Simple Graph - It is the graph if there exists one and only one edge between any pair of vertices.

• Multi Graph - It is the graph which contains more than one edge or loop between any two vertices.

• Null Graph - It is the case of a trivial graph having n isolated vertices but no connecting edge between them.

• Complete Graph - It is the simple undirected graph in which every pair of distinct vertices is connected by a unique edge. It is also known as a full graph, and the degree of each vertex must be n-1. Every pair of vertices should be connected.
1. An undirected complete graph with n vertices will have n(n-1)/2 edges

2. A directed complete graph with n vertices will have n(n-1) edges

• Pseudo Graph - It is the graph containing the self-loop along with other edges.

• Regular Graph - It is a simple graph with each vertex having the same degree. Therefore, every complete graph is a regular graph.

• Bipartite Graph - A graph is called a bipartite graph if its vertices can be partitioned into two non-empty disjoint sets. In bipartite graphs, there would be no edge that connects vertices from the same set.

• Labelled Graph - The graph is labelled graph if the edges are labelled with the name, data or weight. It is also known as weighted graph

• Digraph - It is the directed graph in which vertices are ordered in a particular sequence. The edges are represented by arrows. The arrow shows its direction. For example A->B means there is an edge from A to B, not vice versa.

• Subgraph - It is a graph whose vertices and edges are subsets of another graph.

Two Types of Subgraphs:-

1. Vertices Disjoint Subgraph:- A subgraph with no common vertex.

2. Edge Disjoint Subgraph:- A subgraph with no common edge.

• Connected or Disconnected Graph - The graph is called connected if there exists a path from one vertex of the graph to any other vertex of the graph. It has at least n-1 edges.

The graph is called disconnected if it is not connected.

• Cyclic Graph - A graph that has one or more cycles is called cyclic graph. It contains a path from at least one node back to itself.

• Vertex labelled - It is the graph that holds data in its vertices. It can help to determine the edges data like (key, value) pair mapping.

• Directed Acyclic Graph - The graph is called DAG if the edges are directed and don't contain a cycle. The edges are represented using an ordered pair of vertices.

`HURRAY🥳. You have learnt all the types of graph 🙌.`

```Thanks for your patience and I hope you enjoy reading this blog. Kindly share your feedback, it will motivate me to write more such blogs🙂.```