Data Structure

Assignment#4

22F-8802

Hussan Bano

Task 1:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

void printHeap(const vector<int>& heap) {

for (int i : heap) {

cout << i << " ";

cout << endl;

void buildMinHeap(vector<int>& heap) {

make_heap(heap.begin(), heap.end(), greater<int>());

void insertTask(vector<int>& heap, int task) {

heap.push_back(task);

push_heap(heap.begin(), heap.end(), greater<int>());

int extractMin(vector<int>& heap) {

pop_heap(heap.begin(), heap.end(), greater<int>());

int top = heap.back();

heap.pop_back();

return top;

vector<int> extractTop3(vector<int>& heap) {

vector<int> top3;

for (int i = 0; i < 3 && !heap.empty(); ++i) {

top3.push_back(extractMin(heap));

return top3;

int main() {

system("color F5");

vector<int> tasks = { 15, 10, 20, 8, 12, 25, 18 };

buildMinHeap(tasks);

cout << "Heap after building: ";

printHeap(tasks);

insertTask(tasks, 5);

cout << "Heap after inserting task with priority 5: ";

printHeap(tasks);

int highestPriorityTask = extractMin(tasks);

cout << "Highest-priority task extracted: " <<

highestPriorityTask << endl;

cout << "Heap after extracting the highest-priority task: ";

printHeap(tasks);

vector<int> top3Tasks = extractTop3(tasks);

cout << "Top 3 priority tasks extracted: ";

for (int task : top3Tasks) {

cout << task << " ";

cout << endl;

cout << "Heap after extracting the top 3 priority tasks: ";

printHeap(tasks);

system("pause");

return 0;

Output:

Task 2:

#include <iostream>

#include <climits>

#include <vector>

using namespace std;

int findNearestCity(int currentCity, const vector<bool>&

visited, const int graph[4][4], int numCities) {

int nearestCity = -1;

int minDistance = INT_MAX;

for (int i = 0; i < numCities; ++i) {

if (!visited[i] && graph[currentCity][i] < minDistance) {

minDistance = graph[currentCity][i];

nearestCity = i;
}

return nearestCity;

int main() {

int graph[4][4] = {

{0, 10, 15, 20},

{10, 0, 35, 25},

{15, 35, 0, 30},

{20, 25, 30, 0}

};

int numCities = 4;

vector<bool> visited(numCities, false);

vector<int> route(numCities + 1);

int currentCity = 0;

int totalCost = 0;

visited[currentCity] = true;

route[0] = currentCity;

for (int i = 1; i < numCities; ++i) {

int nextCity = findNearestCity(currentCity, visited, graph,

numCities);

totalCost += graph[currentCity][nextCity];

currentCity = nextCity;

visited[currentCity] = true;

route[i] = currentCity;
}

totalCost += graph[currentCity][route[0]];

route[numCities] = route[0];

cout << "Approximate shortest route: ";

for (int i = 0; i <= numCities; ++i) {

cout << route[i] << " ";

cout << endl;

cout << "Approximate total cost: " << totalCost << endl;

system("pause");

return 0;

Output:

Task 3:

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

const int MAX_NODES = 6;

const char nodes[MAX_NODES] = { 'A', 'B', 'C', 'D', 'E', 'F' };

struct Node {

char neighbors[MAX_NODES];

int count;

Node() : count(0) {}

};
Node graph[MAX_NODES];

int findIndex(char node) {

for (int i = 0; i < MAX_NODES; ++i) {

if (nodes[i] == node) {

return i;

return -1;

void addEdge(char u, char v) {

int uIndex = findIndex(u);

int vIndex = findIndex(v);

graph[uIndex].neighbors[graph[uIndex].count++] = v;

graph[vIndex].neighbors[graph[vIndex].count++] = u;

void BFS(char start) {

bool visited[MAX_NODES] = { false };

char queue[MAX_NODES];

int front = 0, rear = 0;

cout << "BFS Traversal: ";

queue[rear++] = start;

visited[findIndex(start)] = true;

while (front < rear) {

char current = queue[front++];

cout << current << " ";

int currentIndex = findIndex(current);

for (int i = 0; i < graph[currentIndex].count; ++i) {

char neighbor = graph[currentIndex].neighbors[i];

int neighborIndex = findIndex(neighbor);

if (!visited[neighborIndex]) {

queue[rear++] = neighbor;

visited[neighborIndex] = true;

cout << endl;

void DFS(char start) {

bool visited[MAX_NODES] = { false };

char stack[MAX_NODES];

int top = -1;

cout << "DFS Traversal: ";

stack[++top] = start;

while (top >= 0) {

char current = stack[top--];

int currentIndex = findIndex(current);

if (!visited[currentIndex]) {

cout << current << " ";

visited[currentIndex] = true;

for (int i = graph[currentIndex].count - 1; i >= 0; --i) {

char neighbor = graph[currentIndex].neighbors[i];

int neighborIndex = findIndex(neighbor);

if (!visited[neighborIndex]) {

stack[++top] = neighbor;

cout << endl;

void shortestPathBFS(char start, char end) {

bool visited[MAX_NODES] = { false };

char queue[MAX_NODES];

int parent[MAX_NODES];

memset(parent, -1, sizeof(parent));

int front = 0, rear = 0;

queue[rear++] = start;

visited[findIndex(start)] = true;

while (front < rear) {

char current = queue[front++];

int currentIndex = findIndex(current);

if (current == end) {

break;

for (int i = 0; i < graph[currentIndex].count; ++i) {

char neighbor = graph[currentIndex].neighbors[i];

int neighborIndex = findIndex(neighbor);

if (!visited[neighborIndex]) {

queue[rear++] = neighbor;

visited[neighborIndex] = true;

parent[neighborIndex] = currentIndex;

cout << "Shortest path from " << start << " to " << end << ":

";

int endIndex = findIndex(end);

if (parent[endIndex] == -1) {

cout << "No path found." << endl;

return;

char path[MAX_NODES];

int pathSize = 0;

for (int i = endIndex; i != -1; i = parent[i]) {

path[pathSize++] = nodes[i];

reverse(path, path + pathSize);

for (int i = 0; i < pathSize; ++i) {

cout << path[i] << " ";

}
cout << endl;

int main() {

system("color F4");

addEdge('A', 'B');

addEdge('A', 'C');

addEdge('B', 'D');

addEdge('B', 'E');

addEdge('C', 'F');

char start = 'A';

BFS(start);

DFS(start);

char end = 'F';

shortestPathBFS(start, end);

system("pause");

return 0;

Output:

Task 4:

#include <iostream>

#include <vector>

#include <limits>

using namespace std;

#define V 5

int minKey(const vector<int>& key, const vector<bool>&

mstSet) {

int min = numeric_limits<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;

void printMST(const vector<int>& parent, const int

graph[V][V]) {

cout << "Edge \tWeight\n";

int totalCost = 0;

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

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

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

totalCost += graph[i][parent[i]];

cout << "Total cost of the MST: " << totalCost << endl;

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

vector<int> parent(V);

vector<int> key(V, numeric_limits<int>::max());

vector<bool> mstSet(V, false);

key[0] = 0;

parent[0] = -1;

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

int u = minKey(key, mstSet);

mstSet[u] = true;

for (int v = 0; v < V; ++v) {

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

key[v]) {

parent[v] = u;

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

printMST(parent, graph);

int main() {

system("color F3");

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}

};

primMST(graph);
system("pause");

return 0;

Output: