Ritika Khanduri

Posted on May 25, 2022

Graphs and Types of Graphs🔥

#cpp #programming #tutorial #career

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

Let's start with the definition of Graphs

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.

An undirected complete graph with n vertices will have n(n-1)/2 edges
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:-

Vertices Disjoint Subgraph:- A subgraph with no common vertex.
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.