Problem: Given a bipartite graph, write an algorithm to find the maximum matching. The maximum bipartite matching solves many problems in the real world like if there are M jobs and N applicants. Each applicant can do some jobs. Your task is to assign these jobs to the applicants so that maximum applicants get the … Read more
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
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
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
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
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
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
Objective: Given an undirected graph, write an algorithm to find out whether the graph is connected or not. Graph Connectivity: If each vertex of a graph is connected to one or multiple vertices then the graph is called a Connected graph whereas if there exists even one vertex which is not connected to any vertex … Read more
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
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
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
Objective: Given a disconnected graph, Write a program to do the BFS, Breadth-First Search or traversal. Example: Approach: Earlier we had seen the BFS for a connected graph. In this article, we will extend the solution for the disconnected graph. Use the Queue. Create a boolean array, mark the vertex true in the array once … Read more
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
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
Bipartite Graphs OR Bigraphs is a graph whose vertices can be divided into two independent groups or sets, U and V such that each edge in the graph has one end in set U and another end in set V or in other words each edge is either (u, v) which connects edge a vertex … Read more