Category: Graphs

Determine if a given graph is Bipartite Graph using DFS

Given a graph, check if given graph is bipartite graph or not. A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.

Greedy coloring of 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.

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.