Graph Algorithms in C++: A Comprehensive Guide
Graph Algorithms in C++
Circular, Doubly, and Doubly Circular Linked Lists
Let’s explore various linked list structures and their C++ implementations:
Node Class
The foundation of our linked lists is the Node class, representing individual elements:
#include <iostream>
using namespace std;
// Node class represents each element in the linked lists
class Node {
public:
int data;
Node* prev;
Node* next;
Node(int data) {
this->data = data;
this->prev = nullptr;
this->next = nullptr;
}
};
Circular Linked List
In a circular linked list, the last node points back to the head, creating a continuous loop:
// CircularLinkedList class represents the circular linked list
class CircularLinkedList {
private:
Node* head;
public:
CircularLinkedList() { head = nullptr; }
// Appends a new node with the given data to the end of the list
void append(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
newNode->next = head;
} else {
Node* current = head;
while (current->next != head) {
current = current->next;
}
current->next = newNode;
newNode->next = head;
}
}
// Prints the elements of the list starting from the head
void printList() {
if (head == nullptr) {
cout << "List is empty" << endl;
return;
}
Node* current = head;
do {
cout << current->data << " -> ";
current = current->next;
} while (current != head);
cout << " (head)" << endl;
}
};
Doubly Linked List
Doubly linked lists provide bi-directional traversal with both prev and next pointers:
// DoublyLinkedList class represents the doubly linked list
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
DoublyLinkedList() { head = nullptr; tail = nullptr; }
// Appends a new node with the given data to the end of the list
void append(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
// Prints the elements of the list starting from the head
void printList() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " <-> ";
current = current->next;
}
cout << "NULL" << endl;
}
};
Doubly Circular Linked List
Combining the features of doubly linked lists and circular lists, we get a doubly circular linked list:
// DoublyCircularLinkedList class represents the doubly circular linked list
class DoublyCircularLinkedList {
private:
Node* head;
public:
DoublyCircularLinkedList() { head = nullptr; }
// Appends a new node with the given data to the end of the list
void append(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
newNode->next = head;
newNode->prev = head;
} else {
Node* tail = head->prev;
tail->next = newNode;
newNode->prev = tail;
newNode->next = head;
head->prev = newNode;
}
}
// Prints the elements of the list starting from the head
void printList() {
if (head == nullptr) {
cout << "List is empty" << endl;
return;
}
Node* current = head;
do {
cout << current->data << " <-> ";
current = current->next;
} while (current != head);
cout << "(head)" << endl;
}
};
Depth First Search (DFS) and Topological Sorting
#include <bits/stdc++.h>
using namespace std;
// Function to perform DFS and topological sorting
void topologicalSortUtil(int v, vector<vector<int> >& adj, vector<bool>& visited, stack<int>& Stack) {
// Mark the current node as visited
visited[v] = true;
// Recur for all adjacent vertices
for (int i : adj[v]) {
if (!visited[i])
topologicalSortUtil(i, adj, visited, Stack);
}
// Push current vertex to stack which stores the result
Stack.push(v);
}
// Function to perform Topological Sort
void topologicalSort(vector<vector<int> >& adj, int V) {
stack<int> Stack;
// Stack to store the result
vector<bool> visited(V, false);
// Call the recursive helper function to store
// Topological Sort starting from all vertices one by
// one
for (int i = 0; i < V; i++) {
if (!visited[i])
topologicalSortUtil(i, adj, visited, Stack);
}
// Print contents of stack
cout << "Topological sorting of the graph: ";
while (!Stack.empty()) {
cout << Stack.top() << " ";
Stack.pop();
}
cout << endl;
}
int main() {
// Number of nodes
int V = 4;
// Edges
vector<vector<int> > edges = {{0, 1}, {1, 2}, {3, 1}, {3, 2}};
// Graph represented as an adjacency list
vector<vector<int> > adj(V);
for (auto i : edges) {
adj[i[0]].push_back(i[1]);
}
topologicalSort(adj, V);
return 0;
}
Disjoint Set Data Structure
// C++ implementation of disjoint set
#include <bits/stdc++.h>
using namespace std;
class DisjSet {
int *rank, *parent, n;
public:
// Constructor to create and
// initialize sets of n items
DisjSet(int n)
{
rank = new int[n];
parent = new int[n];
this->n = n;
makeSet();
}
// Creates n single item sets
void makeSet()
{
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// Finds set of given item x
int find(int x)
{
// Finds the representative of the set
// that x is an element of
if (parent[x] != x) {
// if x is not the parent of itself
// Then x is not the representative of
// his set,
parent[x] = find(parent[x]);
// so we recursively call Find on its parent
// and move i's node directly under the
// representative of this set
}
return parent[x];
}
// Do union of two sets by rank represented
// by x and y.
void Union(int x, int y)
{
// Find current sets of x and y
int xset = find(x);
int yset = find(y);
// If they are already in same set
if (xset == yset)
return;
// Put smaller ranked item under
// bigger ranked item if ranks are
// different
if (rank[xset] < rank[yset]) {
parent[xset] = yset;
}
else if (rank[xset] > rank[yset]) {
parent[yset] = xset;
}
// If ranks are same, then increment
// rank.
else {
parent[yset] = xset;
rank[xset] = rank[xset] + 1;
}
}
};
// Driver Code
int main()
{
// Function Call
DisjSet obj(5);
obj.Union(0, 2);
obj.Union(4, 2);
obj.Union(3, 1);
if (obj.find(4) == obj.find(0))
cout << "Yes\n";
else
cout << "No\n";
if (obj.find(1) == obj.find(0))
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
Bellman-Ford Algorithm
// A C++ program for Bellman-Ford's single source
// shortest path algorithm.
#include <bits/stdc++.h>
using namespace std;
// a structure to represent a weighted edge in graph
struct Edge {
int src, dest, weight;
};
// a structure to represent a connected, directed and
// weighted graph
struct Graph {
// V-> Number of vertices, E-> Number of edges
int V, E;
// graph is represented as an array of edges.
struct Edge* edge;
};
// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->edge = new Edge[E];
return graph;
}
// A utility function used to print the solution
void printArr(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
// The main function that finds shortest distances from src
// to all other vertices using Bellman-Ford algorithm. The
// function also detects negative weight cycle
void BellmanFord(struct Graph* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[V];
// Step 1: Initialize distances from src to all other
// vertices as INFINITE
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
// Step 2: Relax all edges |V| - 1 times. A simple
// shortest path from src to any other vertex can have
// at-most |V| - 1 edges
for (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < E; j++) {
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
// Step 3: check for negative-weight cycles. The above
// step guarantees shortest distances if graph doesn't
// contain negative weight cycle. If we get a shorter
// path, then there is a cycle.
for (int i = 0; i < E; i++) {
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
printf("Graph contains negative weight cycle");
return; // If negative cycle is detected, simply
// return
}
}
printArr(dist, V);
return;
}
// Driver's code
int main()
{
/* Let us create the graph given in above example */
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
struct Graph* graph = createGraph(V, E);
// add edge 0-1 (or A-B in above figure)
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;
// add edge 0-2 (or A-C in above figure)
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;
// add edge 1-2 (or B-C in above figure)
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;
// add edge 1-3 (or B-D in above figure)
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;
// add edge 1-4 (or B-E in above figure)
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;
// add edge 3-2 (or D-C in above figure)
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;
// add edge 3-1 (or D-B in above figure)
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;
// add edge 4-3 (or E-D in above figure)
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
// Function call
BellmanFord(graph, 0);
return 0;
}
Union Find
class UnionFind {
public:
int * root, * size;
UnionFind(int NumElements) {
root = new int[NumElements];
size = new int[NumElements];
for (int i = 0; i < NumElements; i++) {
root[i] = i;
size[i] = 1;
}
}
void Union(int left, int right) {
int l = find(left), r = find(right);
if (size[l] <= size[r]) {
root[l] = r;
size[r] += size[l];
} else {
root[r] = l;
size[l] += size[r];
}
}
int find(int element) {
while (element != root[element]) {
element = root[element];
}
return element;
}
};
Iterative Binary Search
// C++ program to implement iterative Binary Search
#include <bits/stdc++.h>
using namespace std;
// An iterative binary search function.
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// If we reach here, then element was not present
return -1;
}
// Driver code
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? cout << "Element is not present in array" : cout << "Element is present at index " << result;
return 0;
}
Maximum Subarray Sum
// C++ program to print largest contiguous array sum
#include <bits/stdc++.h>
using namespace std;
int maxSubArraySum(int a[], int size)
{
int max_so_far = INT_MIN, max_ending_here = 0;
for (int i = 0; i < size; i++) {
max_ending_here = max_ending_here + a[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
// Driver Code
int main()
{
int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = sizeof(a) / sizeof(a[0]);
// Function Call
int max_sum = maxSubArraySum(a, n);
cout << "Maximum contiguous sum is " << max_sum;
return 0;
}
Heap Sort
// C++ program for implementation of Heap Sort
#include <iostream>
using namespace std;
// To heapify a subtree rooted with node i
// which is an index in arr[].
// n is size of heap
void heapify(int arr[], int N, int i)
{
// Initialize largest as root
int largest = i;
// left = 2*i + 1
int l = 2 * i + 1;
// right = 2*i + 2
int r = 2 * i + 2;
// If left child is larger than root
if (l < N && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest
// so far
if (r < N && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected
// sub-tree
heapify(arr, N, largest);
}
}
// Main function to do heap sort
void heapSort(int arr[], int N)
{
// Build heap (rearrange array)
for (int i = N / 2 - 1; i >= 0; i--)
heapify(arr, N, i);
// One by one extract an element
// from heap
for (int i = N - 1; i > 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// A utility function to print array of size n
void printArray(int arr[], int N)
{
for (int i = 0; i < N; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// Driver's code
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
heapSort(arr, N);
cout << "Sorted array is \n";
printArray(arr, N);
}
Merge Sort
#include using namespace std; // Merges two subarrays of array[]. // First subarray is arr[begin..mid] // Second subarray is arr[mid+1..end] void merge(int array[], int const left, int const mid, int const right) { auto const subArrayOne = mid – left + 1; auto const subArrayTwo = right – mid; // Create temp arrays auto *leftArray = new int[subArrayOne], *rightArray = new int[subArrayTwo]; // Copy data to temp arrays leftArray[] // and rightArray[] for (auto i = 0; i = end) return; auto mid = begin + (end – begin) / 2; mergeSort(array, begin, mid); mergeSort(array, mid + 1, end); merge(array, begin, mid, end); } // UTILITY FUNCTIONS // Function to print an array void printArray(int A[], int size) { for (auto i = 0; i
// A C++ program for Prim’s Minimum // Spanning Tree (MST) algorithm. The program is // for adjacency matrix representation of the graph #include using namespace std; // Number of vertices in the graph #define V 5 // A utility function to find the vertex with // minimum key value, from the set of vertices // not yet included in MST int minKey(int key[], bool mstSet[]) { // Initialize min value int min = INT_MAX, min_index; for (int v = 0; v
// C++ program for the above approach #include using namespace std; // DSU data structure // path compression + rank by union class DSU { int* parent; int* rank; public: DSU(int n) { parent = new int[n]; rank = new int[n]; for (int i = 0; i rank[s2]) { parent[s2] = s1; } else { parent[s2] = s1; rank[s1] += 1; } } } }; class Graph { vector > edgelist; int V; public: Graph(int V) { this->V = V; } // Function to add edge in a graph void addEdge(int x, int y, int w) { edgelist.push_back({ w, x, y }); } void kruskals_mst() { // Sort all edges sort(edgelist.begin(), edgelist.end()); // Initialize the DSU DSU s(V); int ans = 0; cout
// Boruvka’s algorithm to find Minimum Spanning // Tree of a given connected, undirected and weighted graph #include using namespace std; // Class to represent a graph class Graph { int V; // No. of vertices vector >graph; // default dictionary to store graph // A utility function to find set of an element i // (uses path compression technique) int find(vector& parent, int i) { if (parent[i] == i) { return i; } return find(parent, parent[i]); } // A function that does union of two sets of x and y // (uses union by rank) void unionSet(vector& parent, vector& rank, int x, int y) { int xroot = find(parent, x); int yroot = find(parent, y); // Attach smaller rank tree under root of high rank // tree (Union by Rank) if (rank[xroot] rank[yroot]) { parent[yroot] = xroot; } // If ranks are same, then make one as root and // increment its rank by one else { parent[yroot] = xroot; rank[xroot]++; } } public: Graph(int vertices) { V = vertices; graph = vector >(); } // function to add an edge to graph void addEdge(int u, int v, int w) { graph.push_back({ u, v, w }); } // The main function to construct MST using Kruskal’s // algorithm void boruvkaMST() { vector parent(V); // An array to store index of the cheapest edge of // subset. It store [u,v,w] for each component vector rank(V); vector > cheapest(V, vector(3, -1)); // Initially there are V different trees. // Finally there will be one tree that will be MST int numTrees = V; int MSTweight = 0; // Create V subsets with single elements for (int node = 0; node 1) { // Traverse through all edges and update // cheapest of every component for (int i = 0; i w) { cheapest[set1] = { u, v, w }; } if (cheapest[set2][2] == -1 || cheapest[set2][2] > w) { cheapest[set2] = { u, v, w }; } } } // Consider the above picked cheapest edges and // add them to MST for (int node = 0; node