# C++ Programming Examples on Graph Problems & Algorithms

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

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. A set of items connected by edges. Each item is called a vertex or node. If the graph is undirected, the adjacency relation defined by the edges is symmetric. A directed acyclic graph (DAG!) is a directed graph that contains no cycles. A rooted tree is a special kind of DAG and a DAG is a special kind of directed graph. The section contains C++ programs to check the connectivity of directed and undirected graph using BFS & DFS, programs to solve linear equations, 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 Undirected Graph Using BFS C++ Program to Check the Connectivity of Directed Graph Using BFS C++ Program to Check the Connectivity of Undirected Graph Using DFS C++ Program to Check the Connectivity of Directed 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 C++ Program to Find Strongly Connected Components in Graphs |

## 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. 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 C++ Program to Check Cycle in a Graph using Topological Sort C++ Program for Topological Sorting in Graphs |

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

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. Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. Kruskal’s algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. 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 C++ Program to Find MST(Minimum Spanning Tree) using Kruskal’s Algorithm C++ Program to Find MST(Minimum Spanning Tree) using Prim’s Algorithm |

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

Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph. Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights. Johnson’s algorithm helps to find shortest path between given source and destination nodes. This section contains C++ programs to find the shortest path by using dijkstra’s algorithm, bellmanford algorithm, floyd-warshall algorithm and johnson’s algorithm.

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

The C++ programs in this section computes the transitive closure of a graph using warshall-algorithm and evaluates the transpose of a graph matrix. Warshall algorithm is used for finding shortest paths in a weighted graph with positive or negative edge weights. The reachability of a particular node ‘i’ towards all node pairs (‘i’,’j’) is known as the transitive closure of a graph.

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

## 6. C++ Programming examples on “Matching”

Hungarian algorithm, also known as Munkres algorithm is a method for solving the assignment problem. Bipartite Graph is a set of the edges chosen in such a way that no two edges share an endpoint. Maximum cardinality matching is has maximum size over all matchings in the graph. Edmonds’ algorithm is an algorithm for finding a maximum or minimum optimum branchings. The following section contains C++ 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 path and circuit for undirected graph. Eulerian Path is a path in graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex. Euler Circuit in a Directed Graph. Eulerian Path is a path in graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex. The C++ programs in this section checks whether directed and undirected graph contains a eulerian cycle or eulerian path. It also explains implementation of chinese postman and euler circuit problems.

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 C++ Program to Implement Euler Circuit Problem |

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

An edge in an undirected connected graph is a bridge if removing it disconnects the 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. The C++ programs in this section whether graph is bipartite using BFS, DFS and color algorithm. The programs determine if the graph is weakly connected or strongly connected and also tests for edge connectivity and vertex connectivity of graphs.

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

Binary tree is made of nodes, where each node contains a left reference, a right reference, and a data element. The topmost node in the tree is called the root. AVL tree is a self balanced binary search tree. Cartesian tree is a binary tree derived from a sequence of numbers. Splay tree is a self-balancing data structure where the last accessed key is always at root. A fusion tree is a type of tree data structure that implements an associative array on w-bit integers. Red Black tree is a special type of binary tree, used in computer science to organize pieces of comparable data, such as text fragments or numbers. The C++ programs in this section deals with implementation of b tree, segment tree, splay tree, avl tree, aa tree, cartesian, splay, suffix, ternary, range and fusion trees, trie, tango tree, programs to perform operations in BST, programs to construct an expression tree for prefix, infix and postfix expressions.

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

The C++ programs in this section deals with implementation of hopcroft, tarjan algorithm, booth and lueker algorithms, check whether graph is planar or not. Hopcroft–Karp algorithm is an algorithm that takes as input a bipartite graph and produces as output a maximum cardinality matching.

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”

Beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. Bidirectional Search searches in two directions at the same time, one forward from the initial state and the other backward from the goal. The C++ programs in this section demonstrates the implementation of beam search algorithm, best first search, bidirectional search, depth limited search, iterative depending and uniform cost search. it also explains how to find forward, cross and back edges in a graph.

C++ Program to Implement Beam Search Algorithm C++ Program to Implement Best First Search C++ Program to Implement Bidirectional Search 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 |

## 12. C++ Programming examples on “Other”

This section contains a C++ programs to find the inverse and transpose of a graph matrix and implementation of network flow problem.

C++ Program to Find Inverse of a Graph Matrix C++ Program to Find Transpose of a Graph Matrix C++ Program to Implement Network_Flow Problem |

## 13. C++ Programming examples on “Network Flow”

Edmonds_Karp Algorithm which is used to compute the maximum flow between the sink and source vertex. Ford-Fulkersson Algorithm which computes the maximum flow present inside a network. The C++ programs in this section demonstrates the implementation of edmonds-karp and ford–fulkerson algorithm.

C++ Program to Implement The Edmonds-Karp Algorithm C++ Program to Implement Ford–Fulkerson Algorithm |

## 14. C++ Programming examples on “Graph Traversal”

Graph traversal is technique used for searching a vertex in a graph. The graph traversal is also used to decide the order of vertices to be visit in the search process. The following section contains C++ programs on graph traverse using BFS and DFS.

C++ Program to Traverse a Graph using BFS C++ Program to Traverse a Graph using DFS |

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