This is a C++ Program to Check if a Given Graph is Bipartite. Problem Description The problem takes a graph as input and checks whether it is Bipartite or not. Bipartite Graph is a graph in which the set of vertices can be divided into two sets such that all vertex should be present in … Read more
This is a C++ Program to check whether graph is DAG. In mathematics and computer science, a directed acyclic graph (DAG Listeni/’dæg/), is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no … Read more
This is a C++ Program to find minimum number of edges to cut to make the graph disconnected. An edge in an undirected connected graph is a bridge if removing it disconnects the graph. For a disconnected undirected graph, definition is similar, a bridge is an edge removing which increases number of connected components. Here … Read more
This is a C++ Program to find longest path in DAG. Given a Weighted Directed Acyclic Graph (DAG) and a source vertex s in it, find the longest distances from s to all other vertices in the given graph. Following is complete algorithm for finding longest distances. 1) Initialize dist[] = {NINF, NINF, ….} and … Read more
This is a C++ Program to check whether an directed graph is tree or not. Graph is tree if it doesn’t contain cycles. Here is source code of the C++ Program to Check if an Directed Graph is a Tree or Not Using DFS. The C++ program is successfully compiled and run on a Linux … Read more
This is a C++ Program to find edge connectivity of a graph. An edge in an undirected connected graph is a bridge if removing it disconnects the graph. For a disconnected undirected graph, definition is similar, a bridge is an edge removing which increases number of connected components. Here is source code of the C++ … Read more
This is a C++ Program to find shortest path. Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate a SPT (shortest path tree) with given source as root. We maintain two sets, one set contains vertices included in shortest path tree, other set includes vertices not yet … Read more
This is a C++ Program to find vertex connectivity of a graph. A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 … Read more
This is a C++ Program to check whether a directed graph is weakly connected or not. We can do DFS V times starting from every vertex. If any DFS, doesn’t visit all vertices, then graph is not strongly connected. This algorithm takes O(V*(V+E)) time which can be same as transitive closure for a dense graph.Time … Read more
This is a C++ Program to check whether an undirected graph is tree or not. Graph is tree if it doesn’t contain cycles. Here is source code of the C++ Program to Check if an UnDirected Graph is a Tree or Not Using DFS. The C++ program is successfully compiled and run on a Linux … Read more
