Determine a negative-weight cycle in a graph
Given a directed weighted graph, report a negative-weight cycle in the graph, if any. A negative-weight cycle is a cycle in a graph whose edges sum to a negative value.
Category: Graph
Least cost path in a digraph from a given source to a destination having exactly `m` edges
Given a weighted digraph (directed graph), find the least-cost path from a given source to a given destination with exactly m edges.
Find maximum cost path in a graph from a given source to a given destination
Given a weighted graph, find the maximum cost path from a given source to a destination that is greater than a given integer k. The path should not contain any cycles.
Graph Implementation in Python
This post implements weighted and unweighted directed graph data structure in Python using an adjacency list representation of a graph, where each vertex in the graph stores a list of neighboring vertices.
Kahn’s Topological Sort Algorithm
Given a directed acyclic graph (DAG), print it in Topological order using Kahn’s topological sort algorithm. If the DAG has more than one topological ordering, print any of them.
Find the cost of the shortest path in DAG using one pass of Bellman–Ford
Given a directed acyclic graph (DAG) and a source vertex, find the shortest path’s cost from the source vertex to all other vertices present in the graph. If the vertex can’t be reached from the given source vertex, print its distance as infinity.
Compute the least cost path in a weighted digraph using BFS
Consider a directed graph where the weight of its edges can be one of x, 2x, or 3x (x is a given integer), compute the least-cost path from source to destination efficiently.
Determine whether a graph is Bipartite using DFS
Given a graph, determine if it is bipartite using DFS. 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.
Check if a graph is strongly connected or not using one DFS Traversal
Given a directed graph, check if it is strongly connected or not. A directed graph is said to be strongly connected if every vertex is reachable from every other vertex.
Print all k–colorable configurations of a graph (Vertex coloring of a graph)
Given a graph, find if it is k–colorable or not and print all possible configurations of assignment of colors to its vertices.
Print all Hamiltonian paths present in a graph
Given an undirected graph, print all Hamiltonian paths present in it. The Hamiltonian path in an undirected or directed graph is a path that visits each vertex exactly once.
Graph Coloring Problem
Graph coloring (also called vertex coloring) is a way of coloring a graph’s vertices such that no two adjacent vertices share the same color. This post will discuss a greedy algorithm for graph coloring and minimize the total number of colors used.