Graphs

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

by

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 Check if Graph is Bipartite – Adjacency List using Breadth-First Search(BFS)

Articulation Points OR Cut Vertices in a Graph

by

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 Articulation Points OR Cut Vertices in a Graph

Check If Given Undirected Graph is a tree

by

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 Check If Given Undirected Graph is a tree

Find the number of distinct Islands OR connected components.

by

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 Find the number of distinct Islands OR connected components.

Print All Paths in Dijkstra’s Shortest Path Algorithm

by

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 Print All Paths in Dijkstra’s Shortest Path Algorithm

Number of Islands using BFS

by

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 Number of Islands using BFS

Check if given undirected graph is connected or not

by

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 Check if given undirected graph is connected or not

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

by

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 Check if Graph is Bipartite – Adjacency List using Depth-First Search(DFS)

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

by

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 Graph – Remove a vertex and all edges connect to the vertex

Maximum number edges to make Acyclic Undirected/Directed Graph

by

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 Maximum number edges to make Acyclic Undirected/Directed Graph

Breadth-First Search in Disconnected Graph

by

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 Breadth-First Search in Disconnected Graph

Number of Islands

by

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 Number of Islands

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

by

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 Check if Graph is Bipartite – Adjacency Matrix using Depth-First Search(DFS)

Reverse the Directed Graph

by

Objective: Given a directed graph, write an algorithm to reverse the graph.  Example:  Approach: Create a new graph with the same number of vertices. Traverse the given graph. Here we are using the adjacency list to represent the graph. Traverse each adjacency list and while traversing keep adding the reverse edges (making source as destination … Read more Reverse the Directed Graph