## BFS Program in C

What is BFS? Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structure. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the … Read more

## C Program to Implement Floyd Warshall Algorithm

The Floyd-Warshall algorithm in C is a graph algorithm that finds the shortest path between two vertices in a graph in a weighted graph with positive or negative edge weights but without negative cycles. The algorithm is named after the British mathematician Floyd Warshall. The algorithm is also known as the all-pairs shortest path algorithm. … Read more

## C Program to Find Minimum Spanning Tree using Prim’s Algorithm

This is a C Program to find the minimum spanning tree of the given graph using Prims algorihtm. Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. It finds a subset of the edges that forms a tree that includes every vertex, where the total weight … Read more

## C Program to Implement Johnson’s Algorithm

This is a C Program to implement Johnson’s Algorithm. This code implements Johnson’s algorithm to solve the “all pairs shortest path” problem, ie. given an input graph with general edge weights (can be negative) with no negative cycles, find the shortest (u, w) path for all pairs of vertices (u, w). If the input graph … Read more

## C Program to Create a Random Linear Extension for a DAG

This is a C Program to find topological sorting of a graph. For example:a1 < a0, a1 < a2 < a3. The problem is to determine a list of order, in which if ai < aj then ai will come before aj in the final sorted list. For example, our list could be : a1, ... Read more

## C Program to Find Minimum Spanning Tree using Kruskal’s Algorithm

This is a C Program to find the minimum spanning tree of the given graph. Kruskal’s algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. It finds a subset of the edges that forms a tree that includes every vertex, where the total weight of … Read more

## C Program to Check the Connectivity of Graph Using DFS

This is a C Program to check the connectivity of directed graph using DFS. Depth-first search is a systematic way to find all the vertices reachable from a source vertex, s. Historically, depth-first was first stated formally hundreds of years ago as a method for traversing mazes. Like breadth-first search, DFS traverse a connected component … Read more

## C Program to Check the Connectivity of Graph Using BFS

This is a C Program to check the connectivity of directed graph using BFS. Breadth-first search is a way to find all the vertices reachable from the a given source vertex, s. Like depth first search, BFS traverse a connected component of a given graph and defines a spanning tree. Intuitively, the basic idea of … Read more

## C Program to Check if a Graph is Strongly Connected or Not

This is a C Program to find the connected components of the undirected graph. This can be done using depth first search. If the number of connected components is greater than one graph is weakly connected else its strongly connected. Here is source code of the C Program to Check Whether a Graph is Strongly … Read more 