# C Programming Examples on Graph Problems & Algorithms

## 1. C Programming examples on “Connected Components”

Breadth-first search and Depth First Search is an algorithm for traversing or searching tree or graph. The C programs in this section to check the connectivity of directed and undirected graph using BFS & DFS. The other programs to solve linear equations and testing whether the graphs is a tree or not and also explains how to find the connected components using graphs. The programs in this section perform topological sort using DFS and checks for cycles in graphs.

C Program to Solve any Linear Equation in One Variable C Program to Check the Connectivity of Graph Using BFS C Program to Check the Connectivity of Graph Using DFS C Program to Test Using DFS Whether a Directed Graph is Weakly Connected or Not C Program to Check Whether a Graph is Strongly Connected or Not C Program to Check if an UnDirected Graph is a Tree or Not Using DFS C Program to Check if a Directed Graph is a Tree or Not Using DFS C Program to Find the Connected Components of an UnDirected Graph C Program to Create a Minimal Set of All Edges Whose Addition will Convert it to a Strongly Connected DAG |

## 2. C Programming examples on “Topological Sorting”

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG. This section contains C programs on topological sorting in DAG and graph. It also generates random linear extension for DAG and generates all such possible linear extensions.

C Program to Apply DFS to Perform the Topological Sorting of a Directed Acyclic Graph C Program to Check Whether Topological Sorting can be Performed in a Graph C Program to Create a Random Linear Extension for a DAG C Program to Generate All the Possible Linear Extensions of a DAG C Program to Remove the Edges in a Given Cyclic Graph such that its Linear Extension can be Found |

## 3. C Programming examples on “Minimum Spanning Tree”

Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. Boruvka’s Algorithm is used to find the minimum or maximum spanning tree in the given graph. Minimum spanning tree is a subset of the edges of a connected, edge-weighted (un)directed graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. The C programs in this section to find the minimum spanning tree by applying prim’s, boruvka’s and kruskal’s algorithm.

C Program to Apply the Prim’s Algorithm to Find the Minimum Spanning Tree of a Graph C Program to Apply the Kruskal’s Algorithm to Find the Minimum Spanning Tree of a Graph C Program to Use Boruvka’s Algorithm to Find the Minimum Spanning Tree C Program to Create a MST of a Set of Points Spread in Two Dimensions Using Delaunay Triangulation C Program to Give an Efficient Algorithm to Compute the Second-Best Minimum Spanning Tree of G |

## 4. C Programming examples on “Shortest Path”

Johnson’s algorithm is a way to find the shortest paths between all pairs of vertices in a sparse, edge-weighted and directed graph. Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph. Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights. The C programs in this section to find the shortest path between two vertices using dijkstra’s algorithm, bellman-ford algorithm, topological sorting, floyd-warshall algorithm, and implements dijkstra algorithm using queue, heap and set and also performs implementation of bellmanford, floyd warshall and johnson’s algorithm.

C Program to Find the Shortest Path Between Two Vertices Using Dijkstra’s Algorithm C Program to Find the Shortest Path from Source Vertex to All Other Vertices in Linear Time C Program to Use the Bellman-Ford Algorithm to Find the Shortest Path Between Two Vertices Assuming that Negative Size Edges Exist in the Graph C Program to Implement Shortest Path Algorithm for DAG Using Topological Sorting C Program to Find Shortest Path Between All Vertices Using Floyd-Warshall’s Algorithm C Program to Find the Shortest Cycle in a Graph C Program to Implement Dijkstra’s Algorithm Using Queue C Program to Implement Dijkstra’s Algorithm Using Priority_queue (Heap) C Program to Implement Dijkstra’s Algorithm Using Set C Program to Implement Bellmanford Algorithm C Program to Implement Floyd-Warshall Algorithm C Program to Implement Johnson’s Algorithm |

## 5. C Programming examples on “Transitive Closure and Reduction”

Warshall algorithm is used for finding shortest paths in a weighted graph with positive or negative edge weights. The C programs in this section computes the transitive closure of a graph using warshall-algorithm.

C Program to Find the Transitive Closure of a Given Graph G C Program to Construct Transitive Closure Using Warshall’s Algorithm. |

## 6. C Programming examples on “Matching”

Hungarian algorithm is used to find the maximum-weight matchings in bipartite graphs. Edmond’s Algorithm is used to find the maximum or minimum optimum branchings. The following section contain programs on solving matching problems for given specific case and implements hungarian and edmond algorithm for bipartite and cardinality matching.

C Program to Solve a Matching Problem for a Given Specific Case C Program to Rearrange Letters of a String such that no More than 1 Letters should Retain the Same Position C Program to Solve a Matching Problem for a Given Specific Case C Program to Implement the Hungarian Algorithm for Bipartite Matching C Program to Implement the Edmond’s Algorithm for Maximum Cardinality Matching C Program to Solve a Matching Problem for a Given Specific Case |

## 7. C Programming examples on “Eulerian Cycle/Chinese Postman”

Eulerian Cycle and path uses every edge of a graph exactly once. Euler Cycle starts and ends at the same vertex. Eulerian Path starts and ends at different vertices. Chinese postman problem is to find a shortest closed path or circuit that visits every edge of a undirected graph. The C programs in this section checks if directed and undirected graphs contain eulerian cycle and path and performs implementation of euler circuit problem and chinese postman problem.

C Program to Check Whether an Undirected Graph Contains a Eulerian Cycle C Program to Check Whether an Undirected Graph Contains a Eulerian Path C Program to Check Whether a Directed Graph Contains a Eulerian Cycle C Program to Check Whether a Directed Graph Contains a Eulerian Path C Program to Give an Implementation of the Traditional Chinese Postman Problem |

## 8. C Programming examples on “Edge and Vertex Connectivity”

The C programs in this section determine whether a graph is weakly connected or strongly connected and also tests the edge connectivity and vertex connectivity of graphs. It also contains C programs to find global min cut in a graph.

C Program to Check Whether it is Weakly Connected or Strongly Connected for a Directed Graph C Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph or Check Whether G is Biconnected or Not C Program to Implement an Algorithm to Find the Global min Cut in a Graph C Program to Find the Edge Connectivity of a Graph C Program to Find the Vertex Connectivity of a Graph |

## 9. C Programming examples on “Drawing Trees”

BST is a binary tree which stores at the root of a subtree. Infix, Postfix and Prefix notations are three different but equivalent ways of writing expressions. Binary tree is made of nodes, where each node contains a left reference, a right reference, and a data element. AVL tree is a self balanced binary search tree. Splay tree is a self-balancing data structure where the last accessed key is always at root. The C programs in this section performs insertion, deletion, searching operations on a binary tree, constructs tree for different types of expressions like infix, prefix and postfix and performs respective inorder, preorder and postorder traversals for a tree with recursion and without recursion. The other programs carry left and right rotation operations on binary tree, checks if the given tree is AVL and implements different types of trees like segment, interval, range, ternary, binary, cartesian, AA, AVL and spaly trees. The programs also carry out implementation of types of trees like tango, threaded and suffix tree.

C Program to Perform Dictionary Operations in a Binary Search Tree C Program to Create a Balanced Binary Tree of the Incoming Data C Program to Perform Insertion in a BST C Program to Perform Deletion in a BST C Program to Perform Searching in a BST C Program to Construct an Expression Tree for a Given Prefix Expression C Program to Construct an Expression Tree for a Postfix Expression C Program to Construct an Expression Tree for an Infix Expression C Program to Perform Preorder Non-Recursive Traversal of a Given Binary Tree C Program to Perform Postorder Non-Recursive Traversal of a Given Binary Tree C Program to Perform Inorder Non-Recursive Traversal of a Given Binary Tree C Program to Perform Preorder Recursive Traversal of a Given Binary Tree C Program to Perform Postorder Recursive Traversal of a Given Binary Tree C Program to Perform Inorder Recursive Traversal of a Given Binary Tree C Program to Sort an Array of 10 Elements Using Heap Sort Algorithm C Program to Implement Double Order Traversal of a Binary Tree C Program to Perform Left Rotation on a Binary Search Tree C Program to Perform Right Rotation on a Binary Search Tree C Program to Print the Kind of Rotation the AVL Tree is Undergoing When you Add an Element or Delete an Element C Program to Print only Odd Numbered Levels of a Tree C Program to Check if a Given Binary Tree is an AVL Tree or Not C Program to Delete a Particular Node in a Tree Without Using Recursion C Program to Find Whether a Path Exists Between 2 Given Nodes C Program to Check Whether an Input Binary Tree is the Sub Tree of the Binary Tree C Program to Implement Segment Tree C Program to Implement Interval Tree C Program to Implement Range Tree C Program to Implement Ternary Tree C Program to Implement AA Tree C Program to Implement AVL Tree C Program to Implement Splay Tree C Program to Implement T Tree C Program to Implement Tango Tree C Program to Implement Threaded Binary Tree C Program to Implement Top Tree C Program to Implement Weight Balanced Tree C Program to Implement Trie C Program to Implement Suffix Tree C Program to Implement Randomized Binary Search Tree |

## 10. C Programming examples on “Planarity Detection and Embedding”

The C programs in this section demonstrates the implementation of hopcroft, tarjan algorithm, booth and lueker algorithms. The other programs check whether a graph is planar or not.

C Program to Check Whether a Graph is Planar or Not C Program to Implement the Hopcroft and Tarjan Algorithm C Program to Implement the Booth and Lueker Algorithm to Check for Planarity |

## 11. C Programming examples on “Graph Search”

The C programs in this section to find forward, cross and back edges in a graph. It also demonstrates the implementation of beam search algorithm, best first search, bidirectional search, depth limited search, iterative depending and uniform cost search.

C Program to Implement Beam Search Algorithm C Program to Implement Best First Search C Program to Implement Bidirectional Search C Program to Find SSSP (Single Source Shortest Path) in DAG C Program to Find All Forward Edges in a Graph C Program to Find All Cross Edges in a Graph C Program to Find All Back Edges in a Graph C Program to Implement Depth-Limited Search C Program to Implement Iterative Deepening C Program to Implement Uniform-Cost Search |

**Here’s the list of 1000 C Algorithms, Problems & Programming Examples.**