Check if Graph is Bipartite – Adjacency List using Breadth-First Search(BFS)

Objective: Given a graph represented by the adjacency List, write a Breadth-First Search(BFS) algorithm to check whether the graph is bipartite or not. Earlier we have solved the same problem using Depth-First Search (DFS). In this article, we will solve it using Breadth-First Search(BFS). Before we proceed, if you are new to Bipartite graphs, lets … Read more

Articulation Points OR Cut Vertices in a Graph

Objective: Given a graph, write an algorithm to find all the articulation points or cut vertices. Articulation Points: In a graph, a vertex is called an articulation point if removal of that vertex (along with all the edges associated with that vertex) increases the number of connected components or in other words, removal of that … Read more

Check If Given Undirected Graph is a tree

Objective: Given an undirected graph, Write an algorithm to determine whether its tree or not. An undirected graph is a tree if it has properties mentioned below There is no cycle present in the graph. The graph is connected. (All the vertices in the graph are connected) Example: Recommended articles to read before continue reading … Read more

Find the number of distinct Islands OR connected components.

Objective: Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of distinct or unique islands. Island: An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Assume all four edges of the grid are all surrounded by water. Given such a grid, write an … Read more

Print All Paths in Dijkstra’s Shortest Path Algorithm

Objective:  Given a graph and a source vertex write an algorithm to find the shortest path from the source vertex to all the vertices and print the paths all well. Example: We strongly recommend reading the following before continuing to read Graph Representation – Adjacency List Dijkstra’s shortest path algorithm – Priority Queue method We will … Read more

Number of Islands using BFS

Objective: Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Assume all four edges of the grid are all surrounded by water. Given such grid, write an algorithm using Breadth-First Search(BFS) to … Read more

Check if Graph is Bipartite – Adjacency List using Depth-First Search(DFS)

Objective: Given a graph represented by the adjacency List, write a Depth-First Search(DFS) algorithm to check whether the graph is bipartite or not. Earlier we have solved the same problem using Adjacency Matrix (Check if Graph is Bipartite – Adjacency Matrix) with Time complexity: O(V2) where V – No of vertices in the graph. In … Read more

Given Graph – Remove a vertex and all edges connect to the vertex

Objective: Given a graph represented by an adjacency list and a vertex, write a program to remove the given vertex and all edges connected to that vertex. Example: Approach:  Earlier we had seen Graph Implementation using Map. In this article, we will use this implementation. Delete the vertex from the indexes map (This map is … Read more

Maximum number edges to make Acyclic Undirected/Directed Graph

Given- Given V vertices, what is the maximum number of edges can be added to make Acyclic Undirected Graph. Follow up – what is the maximum number of edges that can be added to make Acyclic Directed Graph. Example:  Approach: For Undirected Graph – It will be a spanning tree (read about spanning tree) where … Read more

Number of Islands

Objective: Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Assume all four edges of the grid are all surrounded by water. Given such a grid, write an algorithm to find the … Read more

Check if Graph is Bipartite – Adjacency Matrix using Depth-First Search(DFS)

Objective: Given a graph represented by the adjacency matrix, write a Depth-First Search(DFS) algorithm to check whether the graph is bipartite or not. Bipartite Graphs OR Bigraphs is a graph whose vertices can be divided into two independent groups or sets so that for every edge in the graph, each end of the edge belongs … Read more