Given a directed weighted graph, report a negative-weight cycle in the graph if any. A negative-weight cycle is a cycle in graph whose edges sum to a negative value. Get great deals at Amazon
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.
Given a directed acyclic graph (DAG) and a source vertex, find the cost of shortest path from source vertex to all other vertices present in the graph. If vertex can’t be reached from given source vertex, print its distance as infinity.
Consider a directed graph where 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.
Given a graph, determine if given graph is bipartite graph 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.
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.
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.
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.
Given a undirected, connected and weighted graph, construct a minimum spanning tree out of it using Kruskal’s Algorithm.