Category: Graphs

0

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

0

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

0

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

0

Check if given undirected graph is connected or not

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

0

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

0

Breadth-First Search in Disconnected Graph

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

0

Reverse the Directed Graph

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

%d bloggers like this: