A Minimum Spanning Tree (MST) is a subset of edges in a connected, weighted graph that connects all vertices without forming a cycle and with the minimum possible total edge weight. In this blog post, we implement Prim’s Algorithm using a min-heap (priority queue) to efficiently calculate the MST. Minimum Spanning Tree in C++ Using …
Minimum Spanning Tree in C++ Using Prim’s Algorithm with Priority Queue Read More »
The Bellman-Ford algorithm is a classical approach for finding the shortest path from a single source node to all other vertices in a weighted graph, even when the graph contains negative weight edges. Unlike Dijkstra’s algorithm, Bellman-Ford is capable of detecting negative weight cycles.In this post, we implement Bellman-Ford using a simple nested loop structure, …
Bellman-Ford Algorithm in C++ – Shortest Path with Negative Weights Read More »
Dijkstra’s Algorithm is one of the most important and widely used algorithms for finding the shortest path in a weighted graph with non-negative edges. In this blog post, we’ll implement Dijkstra’s algorithm using a priority queue (min-heap) in C++. The input will be in the form of an edge list, and the algorithm will return …
Dijkstra’s Algorithm in C++ Using Priority Queue Read More »
Cycle detection in an undirected graph requires a slightly different approach. Since every edge connects both ways, we must carefully track visited nodes and their parents to avoid false positives. Detecting Cycles in an Undirected Graph using BFS Idea Perform a BFS from every unvisited node (to handle disconnected graphs). If a visited node is …
Detecting Cycles in an Undirected Graph using BFS Read More »
In graph theory, detecting cycles in a directed graph is a common problem with applications in scheduling, dependency resolution, and compiler design. One efficient way to solve this is using Kahn’s Algorithm, which is based on topological sorting. Detecting Cycles in a Directed Graph using Kahn’s Algorithm (Topological Sort) Idea We count how many nodes …
Detecting Cycles in a Directed Graph using Kahn’s Algorithm (Topological Sort) Read More »
BFS is a graph traversal method that explores all the neighbors of a node before going deeper. It’s ideal for finding the shortest path in an unweighted graph and is widely used in real-world applications like web crawling, routing, and level order traversal in trees. Breadth First Search (BFS) Traversal on Graph class Solution { …
DFS is a powerful graph traversal technique that explores a path as deeply as possible before backtracking. It is one of the most fundamental algorithms used in graph theory, and understanding it opens the door to solving a variety of problems like cycle detection, connected components, and more. Depth First Search (DFS) Traversal on Graph …
In this blog post, we’ll implement BFS traversal on a graph using an adjacency list representation in C++. What is BFS? BFS starts at a given source node (usually node 0) and explores all its neighbors before moving to the next level. It uses a queue to keep track of nodes to visit. Breadth First …
Breadth First Search (BFS) Traversal of a Graph in C++ Read More »
Depth First Search (DFS) is one of the most commonly used algorithms in graph theory. It’s used to explore all the vertices and edges of a graph systematically, and is a fundamental building block for many advanced problems in computer science. In this blog, we’ll write a simple and clean C++ program to perform DFS …
Depth First Search (DFS) Traversal of a Graph in C++ Read More »
This project is a stripped-down version of a contact book, great for beginners. We’ll use a map to store contacts (name → number) and simple file I/O to save and load data. Simple Contact Book in C++ Using map and File I/O What This Program Does Adds new contacts Displays all contacts Saves contacts to …
Simple Contact Book in C++ Using map and File I/O Read More »