## Single-Source Shortest Paths – Bellman Ford Algorithm

Given a source vertex s from set of vertices V in a weighted graph where its edge weights w(u, v) can be negative, find the shortest-path weights d(s, v) from given source s for all vertices v present in the graph. If the graph contains negative-weight cycle, report it.

## Single-Source Shortest Paths – Dijkstra’s Algorithm

Given a source vertex s from set of vertices V in a weighted graph where all its edge weights w(u, v) are non-negative, find the shortest-path weights d(s, v) from given source s for all vertices v present in the graph.

## Kruskal’s Algorithm for finding Minimum Spanning Tree

Given a undirected, connected and weighted graph, construct a minimum spanning tree out of it using Kruskal’s Algorithm.

## Union-Find Algorithm for Cycle Detection in a graph

Given an connected graph, find if it contains any cycle or not using Union-Find algorithm.

## Check if given Graph is Strongly Connected or not

Given a directed graph, check if it is strongly connected or not. A directed graphs is said to be strongly connected if every vertex is reachable from every other vertex.

## Chess Knight Problem | Find Shortest path from source to destination

Given a chess board, find the shortest distance (minimum number of steps) taken by a Knight to reach given destination from given source.

## Disjoint-Set Data Structure (Union Find Algorithm)

Explain the working of disjoint-set data structure and efficiently implement it. Problem: We have some number of items. We are allowed to merge any two items to consider them equal. At any point, we are allowed to ask whether two items are considered equal or not.

## Check if given digraph is a DAG (Directed Acyclic Graph) or not

Given an directed graph, check if it is a DAG (Directed Acyclic Graph) or not. A DAG is a digraph (directed graph) that contains no cycles.

## 2-Vertex Connectivity in the graph

Given a undirected connected graph, check if the graph is 2-vertex connected or not. A connected graph G is said to be 2-vertex-connected (or 2-connected) if it has more than 2 vertices and remains connected on removal of any vertices. Any such vertex whose removal will disconnected the graph is called Articulation point.

## 2-Edge Connectivity in a Graph

Given a undirected connected graph, check if the graph is 2-edge connected or not.