LINKED LIST:

// Linked list operations in C++

#include <stdlib.h>

#include <iostream>

using namespace std;

// Create a node

struct Node {

int data;

struct Node* next;

};

void insertAtBeginning(struct Node** head_ref, int new_data) {

// Allocate memory to a node

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

// insert the data

new_node->data = new_data;

new_node->next = (*head_ref);

// Move head to new node

(*head_ref) = new_node;

// Insert a node after a node

void insertAfter(struct Node* prev_node, int new_data) {

if (prev_node == NULL) {

cout << "the given previous node cannot be NULL";

return;
 }

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

new_node->data = new_data;

new_node->next = prev_node->next;

prev_node->next = new_node;

// Insert at the end

void insertAtEnd(struct Node** head_ref, int new_data) {

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

struct Node* last = *head_ref; /* used in step 5*/

new_node->data = new_data;

new_node->next = NULL;

if (*head_ref == NULL) {

*head_ref = new_node;

return;

while (last->next != NULL) last = last->next;

last->next = new_node;

return;

// Delete a node

void deleteNode(struct Node** head_ref, int key) {

struct Node *temp = *head_ref, *prev;

if (temp != NULL && temp->data == key) {

free(temp);

return;

// Find the key to be deleted

while (temp != NULL && temp->data != key) {

prev = temp;

temp = temp->next;

// If the key is not present

if (temp == NULL) return;

// Remove the node

prev->next = temp->next;

free(temp);

// Search a node

bool searchNode(struct Node** head_ref, int key) {

struct Node* current = *head_ref;

while (current != NULL) {

if (current->data == key) return true;

current = current->next;

return false;

// Sort the linked list

void sortLinkedList(struct Node** head_ref) {

int temp;

if (head_ref == NULL) {

return;

} else {

while (current != NULL) {

// index points to the node next to current

index = current->next;

while (index != NULL) {

if (current->data > index->data) {

temp = current->data;

current->data = index->data;

index->data = temp;

index = index->next;

current = current->next;

// Print the linked list

void printList(struct Node* node) {

while (node != NULL) {

cout << node->data << " ";

node = node->next;

// Driver program
int main() {

struct Node* head = NULL;

insertAtEnd(&head, 1);

insertAtBeginning(&head, 2);

insertAtBeginning(&head, 3);

insertAtEnd(&head, 4);

insertAfter(head->next, 5);

cout << "Linked list: ";

printList(head);

cout << "\nAfter deleting an element: ";

deleteNode(&head, 3);

printList(head);

int item_to_find = 3;

if (searchNode(&head, item_to_find)) {

cout << endl << item_to_find << " is found";

} else {

cout << endl << item_to_find << " is not found";

sortLinkedList(&head);

cout << "\nSorted List: ";

printList(head);

}
KRUSAL ALGO

// C++ program for the above approach

#include <bits/stdc++.h>

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 < n; i++) {

parent[i] = -1;

rank[i] = 1;

// Find function

int find(int i)

if (parent[i] == -1)

return i;

return parent[i] = find(parent[i]);

// Union function

void unite(int x, int y)

int s1 = find(x);

int s2 = find(y);

if (s1 != s2) {

if (rank[s1] < rank[s2]) {

parent[s1] = s2;

else if (rank[s1] > rank[s2]) {

parent[s2] = s1;

else {

parent[s2] = s1;

rank[s1] += 1;

};

class Graph {

vector<vector<int> > 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 << "Following are the edges in the "

"constructed MST"

<< endl;

for (auto edge : edgelist) {

int w = edge[0];

int x = edge[1];

int y = edge[2];

// Take this edge in MST if it does

// not forms a cycle

if (s.find(x) != s.find(y)) {

s.unite(x, y);

ans += w;

cout << x << " -- " << y << " == " << w

<< endl;

cout << "Minimum Cost Spanning Tree: " << ans;

};
// Driver code

int main()

Graph g(4);

g.addEdge(0, 1, 10);

g.addEdge(1, 3, 15);

g.addEdge(2, 3, 4);

g.addEdge(2, 0, 6);

g.addEdge(0, 3, 5);

// Function call

g.kruskals_mst();

return 0;

PRIM’S ALGO

// A C++ program for Prim's Minimum

// Spanning Tree (MST) algorithm. The program is

// for adjacency matrix representation of the graph

#include <bits/stdc++.h>

using namespace std;

// Number of vertices in the graph

#define V 5

// A utility function to find the vertex with

// 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 < V; v++)

if (mstSet[v] == false && key[v] < min)

min = key[v], min_index = v;

return min_index;

// A utility function to print the

// constructed MST stored in parent[]

void printMST(int parent[], int graph[V][V])

cout << "Edge \tWeight\n";

for (int i = 1; i < V; i++)

cout << parent[i] << " - " << i << " \t"

<< graph[i][parent[i]] << " \n";

// Function to construct and print MST for

// a graph represented using adjacency

// matrix representation

void primMST(int graph[V][V])

// Array to store constructed MST

int parent[V];
// Key values used to pick minimum weight edge in cut

int key[V];

// To represent set of vertices included in MST

bool mstSet[V];

// Initialize all keys as INFINITE

for (int i = 0; i < V; i++)

key[i] = INT_MAX, mstSet[i] = false;

// Always include first 1st vertex in MST.

// Make key 0 so that this vertex is picked as first

// vertex.

key[0] = 0;

// First node is always root of MST

parent[0] = -1;

// The MST will have V vertices

for (int count = 0; count < V - 1; count++) {

// Pick the minimum key vertex from the

// set of vertices not yet included in MST

int u = minKey(key, mstSet);

// Add the picked vertex to the MST Set

mstSet[u] = true;

// Update key value and parent index of

// the adjacent vertices of the picked vertex.

// Consider only those vertices which are not

// yet included in MST

// graph[u][v] is non zero only for adjacent

// vertices of m mstSet[v] is false for vertices

// not yet included in MST Update the key only

// if graph[u][v] is smaller than key[v]

if (graph[u][v] && mstSet[v] == false

&& graph[u][v] < key[v])

parent[v] = u, key[v] = graph[u][v];

// Print the constructed MST

printMST(parent, graph);

// Driver's code

int main()

int graph[V][V] = { { 0, 2, 0, 6, 0 },

{ 2, 0, 3, 8, 5 },

{ 0, 3, 0, 0, 7 },

{ 6, 8, 0, 0, 9 },

{ 0, 5, 7, 9, 0 } };

// Print the solution

primMST(graph);

return 0;

// This code is contributed by rathbhupendra

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

// Function to perform Breadth First Search on a graph

// represented using adjacency list

void bfs(vector<vector<int> >& adjList, int startNode,

vector<bool>& visited)

// Create a queue for BFS

queue<int> q;

// Mark the current node as visited and enqueue it

visited[startNode] = true;

q.push(startNode);

// Iterate over the queue

while (!q.empty()) {

// Dequeue a vertex from queue and print it

int currentNode = q.front();

q.pop();

cout << currentNode << " ";

// Get all adjacent vertices of the dequeued vertex

// then mark it visited and enqueue it

for (int neighbor : adjList[currentNode]) {

if (!visited[neighbor]) {

visited[neighbor] = true;

q.push(neighbor);

// Function to add an edge to the graph

void addEdge(vector<vector<int> >& adjList, int u, int v)

adjList[u].push_back(v);

int main()

// Number of vertices in the graph

int vertices = 5;

// Adjacency list representation of the graph

vector<vector<int> > adjList(vertices);

// Add edges to the graph

addEdge(adjList, 0, 1);

addEdge(adjList, 0, 2);

addEdge(adjList, 1, 3);

addEdge(adjList, 1, 4);

addEdge(adjList, 2, 4);
 // Mark all the vertices as not visited

vector<bool> visited(vertices, false);

// Perform BFS traversal starting from vertex 0

cout << "Breadth First Traversal starting from vertex "

"0: ";

bfs(adjList, 0, visited);

return 0;

DFS

// C++ program to print DFS traversal from

// a given vertex in a given graph

#include <bits/stdc++.h>

using namespace std;

// Graph class represents a directed graph

// using adjacency list representation

class Graph {

public:

map<int, bool> visited;

map<int, list<int> > adj;

// Function to add an edge to graph

void addEdge(int v, int w);

// DFS traversal of the vertices

// reachable from v
 void DFS(int v);

};

void Graph::addEdge(int v, int w)

// Add w to v’s list.

adj[v].push_back(w);

void Graph::DFS(int v)

// Mark the current node as visited and

// print it

visited[v] = true;

cout << v << " ";

// Recur for all the vertices adjacent

// to this vertex

list<int>::iterator i;

for (i = adj[v].begin(); i != adj[v].end(); ++i)

if (!visited[*i])

DFS(*i);

// Driver code

int main()

// Create a graph given in the above diagram

Graph g;

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);
 g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

cout << "Following is Depth First Traversal"

" (starting from vertex 2) \n";

// Function call

g.DFS(2);

return 0;

// improved by Vishnudev C

HEAP

// Max-Heap data structure in C++

#include <iostream>

#include <vector>

using namespace std;

void swap(int *a, int *b)

int temp = *b;

*b = *a;

*a = temp;

void heapify(vector<int> &hT, int i)

int size = hT.size();

int largest = i;

int l = 2 * i + 1;

int r = 2 * i + 2;

if (l < size && hT[l] > hT[largest])

largest = l;

if (r < size && hT[r] > hT[largest])

largest = r;

if (largest != i)

swap(&hT[i], &hT[largest]);

heapify(hT, largest);

void insert(vector<int> &hT, int newNum)

int size = hT.size();

if (size == 0)

hT.push_back(newNum);

else

hT.push_back(newNum);

for (int i = size / 2 - 1; i >= 0; i--)

heapify(hT, i);

}
void deleteNode(vector<int> &hT, int num)

int size = hT.size();

int i;

for (i = 0; i < size; i++)

if (num == hT[i])

break;

swap(&hT[i], &hT[size - 1]);

hT.pop_back();

for (int i = size / 2 - 1; i >= 0; i--)

heapify(hT, i);

void printArray(vector<int> &hT)

for (int i = 0; i < hT.size(); ++i)

cout << hT[i] << " ";

cout << "\n";

int main()

vector<int> heapTree;

insert(heapTree, 3);

insert(heapTree, 4);

insert(heapTree, 9);

insert(heapTree, 5);
 insert(heapTree, 2);

cout << "Max-Heap array: ";

printArray(heapTree);

deleteNode(heapTree, 4);

cout << "After deleting an element: ";

printArray(heapTree);