# Category: Graphs

## Print All Hamiltonian Path present in a graph

Given an undirected graph, print all Hamiltonian paths present in it. Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once.

Read More Print All Hamiltonian Path present in a graph

## Greedy coloring of graph

The graph coloring (also called as vertex coloring) is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color. In this post we will discuss a greedy algorithm for graph coloring and try to minimize the number of colors used.

Read More Greedy coloring of graph

## Best online courses for Data Structures And Algorithms

Friends, this article lists some the of best courses available online on Data Structures and Algorithms. We recommend to go through them to have strong basics.   Data Structures and Algorithms by Dr. Naveen Garg Lecture Series on Data Structures and Algorithms by Dr. Naveen Garg, Department of Computer Science and Engineering, IIT Delhi. Playlist details …

Read More Best online courses for Data Structures And Algorithms

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

Read More Single-Source Shortest Paths – Bellman Ford Algorithm

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

Read More Single-Source Shortest Paths – Dijkstra’s 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.

Read More Check if given Graph is Strongly Connected or not

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

Read More Disjoint-Set Data Structure (Union Find Algorithm)

## 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.   Below graph contains a cycle A-B-D-A, so it is not DAG. If we remove edge 3-0 from it, it will become a DAG.

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

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

Read More 2-Vertex Connectivity in the graph