7.

Aim: Compare the performance of single source shortest paths using greedy method when the
graph is represented by adjacency matrix and adjacency lists

Program:

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

#include <time.h>

#define V 5 // Number of vertices in the graph

// Function to find the minimum distance vertex

int minDistance(int dist[], int visited[]) {

int min = INT_MAX, min_index = -1;

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

if (!visited[v] && dist[v] <= min)

min = dist[v], min_index = v;

return min_index;

// Dijkstra's algorithm using an adjacency matrix representation

void dijkstraMatrix(int graph[V][V], int src) {

int dist[V]; // dist[i] will hold the shortest distance from src to i

int visited[V]; // visited[i] will be 1 if vertex i is included in the shortest path

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

dist[i] = INT_MAX;

visited[i] = 0;

dist[src] = 0;

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

int u = minDistance(dist, visited);

visited[u] = 1;

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

if (!visited[v] && graph[u][v] && dist[u] != INT_MAX &&

dist[u] + graph[u][v] < dist[v]) {

// Node in adjacency list

struct Node {

int dest;

int weight;

struct Node* next;

};

// Adjacency list

struct AdjList {

struct Node* head;

};

// Graph structure containing adjacency lists

struct Graph {

struct AdjList* array;

};

// Function to create a new adjacency list node

struct Node* newAdjListNode(int dest, int weight) {

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

newNode->dest = dest;

newNode->weight = weight;

newNode->next = NULL;

return newNode;

// Function to create a graph

struct Graph* createGraph(int vertices) {

struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));

graph->array = (struct AdjList*)malloc(vertices * sizeof(struct AdjList));

graph->array[i].head = NULL;

return graph;

// Function to add an edge to the graph

void addEdge(struct Graph* graph, int src, int dest, int weight) {

struct Node* newNode = newAdjListNode(dest, weight);

newNode->next = graph->array[src].head;

graph->array[src].head = newNode;

// Dijkstra's algorithm using an adjacency list representation

void dijkstraList(struct Graph* graph, int src) {

int dist[V];

int visited[V];

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

dist[i] = INT_MAX;

visited[i] = 0;

dist[src] = 0;

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

int u = minDistance(dist, visited);

visited[u] = 1;

struct Node* temp = graph->array[u].head;

while (temp) {

int v = temp->dest;

if (!visited[v] && dist[u] != INT_MAX &&

dist[u] + temp->weight < dist[v]) {

dist[v] = dist[u] + temp->weight;

temp = temp->next;

}
 }

int main()

// Adjacency matrix for the graph

int matrix[V][V] = {

{0, 10, 20, 0, 0},

{10, 0, 0, 50, 10},

{20, 0, 0, 20, 33},

{0, 50, 20, 0, 2},

{0, 10, 33, 2, 0},

};

// Creating the adjacency list representation of the same graph

struct Graph* graph = createGraph(V);

addEdge(graph, 0, 1, 10);

addEdge(graph, 0, 2, 20);

addEdge(graph, 1, 3, 50);

addEdge(graph, 1, 4, 10);

addEdge(graph, 2, 3, 20);

addEdge(graph, 2, 4, 33);

addEdge(graph, 3, 4, 2);

addEdge(graph, 4, 3, 2);

// Measure time for adjacency matrix representation

clock_t start = clock();

dijkstraMatrix(matrix, 0);

clock_t end = clock();

double time_used_matrix = ((double)(end - start)) / CLOCKS_PER_SEC;

printf("Time taken by adjacency matrix: %f seconds\n", time_used_matrix);

// Measure time for adjacency list representation

start = clock();

dijkstraList(graph, 0);
 end = clock();

double time_used_list = ((double)(end - start)) / CLOCKS_PER_SEC;

printf("Time taken by adjacency list: %f seconds\n", time_used_list);

return 0;

Output:

Time taken by adjacency matrix: 0.000002 seconds

Time taken by adjacency list: 0.000001 seconds

Aim: To Implement Job Sequencing with deadlines using greedy strategy

Program:

#include <stdio.h>

#include <stdlib.h>

struct Job {

int id; // Job ID

int deadline; // Deadline of the job

int profit; // Profit if the job is completed within its deadline

};

// Comparison function to sort jobs by profit in descending order

int compare(const void *a, const void *b) {

struct Job *job1 = (struct Job *)a;

struct Job *job2 = (struct Job *)b;

return job2->profit - job1->profit;

// Function to find the maximum deadline among all jobs

int findMaxDeadline(struct Job jobs[], int n) {

int maxDeadline = 0;

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

if (jobs[i].deadline > maxDeadline) {

return maxDeadline;

// Function to perform Job Sequencing with Deadlines

void jobSequencing(struct Job jobs[], int n) {

// Sort jobs by profit in descending order

qsort(jobs, n, sizeof(struct Job), compare);

// Find the maximum deadline to size the schedule array

int maxDeadline = findMaxDeadline(jobs, n);

// Array to store the result (sequence of jobs) and keep track of free time slots

int result[maxDeadline];

int slot[maxDeadline];

// Initialize all slots as free

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

slot[i] = 0;

int maxProfit = 0; // Total profit by the scheduled jobs

// Iterate through all given jobs

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

// Find a free slot for this job (starting from the last possible slot)

for (int j = jobs[i].deadline - 1; j >= 0; j--) {

if (slot[j] == 0) {

// Assign job to this slot

result[j] = i; // Store the job index in result

slot[j] = 1; // Mark this slot as occupied

maxProfit += jobs[i].profit; // Update max profit

break;

}
 }

// Display the result

printf("Selected jobs for maximum profit:\n");

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

if (slot[i] == 1) {

printf("Job ID: %d, Profit: %d\n", jobs[result[i]].id, jobs[result[i]].profit);

printf("Total Profit: %d\n", maxProfit);

int main() {

// List of jobs with their IDs, deadlines, and profits

struct Job jobs[] = {

{1, 2, 100}, {2, 1, 19}, {3, 2, 27}, {4, 1, 25}, {5, 3, 15}

};

int n = sizeof(jobs) / sizeof(jobs[0]);

// Execute job sequencing

jobSequencing(jobs, n);

return 0;

Output:

Selected jobs for maximum profit:

Job ID: 3, Profit: 27

Job ID: 1, Profit: 100

Job ID: 5, Profit: 15

Total Profit: 142

Program:

#include <stdio.h>

int max(int a, int b)

return (a > b) ? a : b;

// Function to solve the 0/1 Knapsack problem using Dynamic Programming

int knapsack(int W, int weights[], int values[], int n) {

int dp[n + 1][W + 1];

// Build table dp[][] in bottom-up manner

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

for (int w = 0; w <= W; w++) {

if (i == 0 || w == 0) {

dp[i][w] = 0;

} else if (weights[i - 1] <= w) {

dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);

} else {

dp[i][w] = dp[i - 1][w];

// Find which items were included in the knapsack

int max_value = dp[n][W];

printf("Items included in the knapsack:\n");

int w = W;

for (int i = n; i > 0 && max_value > 0; i--) {

// If the item is included

if (max_value != dp[i - 1][w]) {

printf("Item %d (Weight: %d, Value: %d)\n", i, weights[i - 1], values[i - 1]);

// Reduce max_value and remaining weight

w -= weights[i - 1];

// The maximum value that can be attained with given capacity

return dp[n][W];

int main() {

int n, W;

// Input number of items and knapsack capacity

printf("Enter the number of items: ");

scanf("%d", &n);

printf("Enter the knapsack capacity: ");

scanf("%d", &W);

int weights[n], values[n];

// Input weights and values of each item

printf("Enter the weights of the items:\n");

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

scanf("%d", &weights[i]);

printf("Enter the values of the items:\n");

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

scanf("%d", &values[i]);

int max_value = knapsack(W, weights, values, n);

printf("The maximum value in the knapsack is: %d\n", max_value);

return 0;

Output:

Enter the number of items: 3

Enter the weights of the items:

10 20 30

Enter the values of the items:

60 100 120

Items included in the knapsack:

Item 3 (Weight: 30, Value: 120)

Item 2 (Weight: 20, Value: 100)

The maximum value in the knapsack is: 220

______________________________________________________________________________

10. Aim : Implement N-Queens problem using Backtracking

Program:

#include <stdio.h>

#include <stdbool.h>

#define N 8 // Change this to any value of N for an NxN chessboard

void printSolution(int board[N][N]) {

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

for (int j = 0; j < N; j++) {

printf("%c ", board[i][j] ? 'Q' : '.');

printf("\n");

printf("\n");

// Function to check if a queen can be placed at board[row][col]

bool isSafe(int board[N][N], int row, int col) {

// Check this column on upper side

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

return false;

// Check upper diagonal on left side

for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)

if (board[i][j])

return false;

// Check upper diagonal on right side

for (int i = row, j = col; i >= 0 && j < N; i--, j++)

if (board[i][j])

return false;

return true;

// Recursive function to solve N-Queens problem

bool solveNQueensUtil(int board[N][N], int row) {

// If all queens are placed, return true

if (row >= N)

return true;

// Try placing queen in all columns for the current row

for (int col = 0; col < N; col++) {

// Check if placing queen at board[row][col] is safe

if (isSafe(board, row, col)) {

// Place queen at board[row][col]

board[row][col] = 1;

// Recur to place rest of the queens

if (solveNQueensUtil(board, row + 1))

return true;

// If placing queen here does not lead to a solution, backtrack

board[row][col] = 0;

}
 // If queen cannot be placed in any column in this row, return false

return false;

// Solves the N-Queens problem and prints one solution

void solveNQueens() {

int board[N][N] = {0};

if (!solveNQueensUtil(board, 0)) {

printf("Solution does not exist\n");

return;

printSolution(board);

int main()

solveNQueens();

return 0;

Output: (Output for N=8)

Q.......

....Q...

......Q.

..Q.....

.....Q..

.Q......

...Q....

.......Q
11. Aim : To use backtracking strategy to solve 0/1 knapsack problem

Program:

#include <stdio.h>

int maxProfit = 0; // Variable to store the maximum profit

int bestItems[100]; // Array to store items in the best solution

int currentItems[100]; // Array to store items in the current solution

// Recursive function to solve 0/1 Knapsack problem using Backtracking

void knapsackBacktracking(int index, int weight, int profit, int capacity, int weights[], int profits[], int
n, int count) {

// If weight exceeds capacity, return

if (weight > capacity) return;

// Update maxProfit and bestItems if the current profit is greater

if (profit > maxProfit) {

maxProfit = profit;

// Update bestItems array to store the current selection of items

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

bestItems[i] = currentItems[i];

bestItems[count] = -1; // Mark the end of the selected items

// If no more items are left, return

if (index == n) return;

// Include the current item and move to the next item

currentItems[count] = index + 1; // Store item index (1-based)

knapsackBacktracking(index + 1, weight + weights[index], profit + profits[index], capacity, weights,

// Exclude the current item and move to the next item

knapsackBacktracking(index + 1, weight, profit, capacity, weights, profits, n, count);

int main() {

int n, capacity;

// Input number of items and knapsack capacity

scanf("%d", &n);

printf("Enter the knapsack capacity: ");

scanf("%d", &capacity);

int weights[n], profits[n];

// Input weights and profits of each item

printf("Enter the weights of the items:\n");

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

scanf("%d", &weights[i]);

printf("Enter the profits of the items:\n");

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

scanf("%d", &profits[i]);

// Solve the 0/1 Knapsack problem using Backtracking

knapsackBacktracking(0, 0, 0, capacity, weights, profits, n, 0);

// Output the maximum profit found

printf("The maximum profit is: %d\n", maxProfit);

// Display the items that contribute to the maximum profit

printf("Items included in the knapsack:\n");

for (int i = 0; bestItems[i] != -1; i++) {

printf("Item %d (Weight: %d, Profit: %d)\n", bestItems[i], weights[bestItems[i] - 1],

return 0;

Output:

Enter the number of items: 4

Enter the knapsack capacity: 10

Enter the weights of the items:

Enter the profits of the items:

3456

The maximum profit is: 10

Items included in the knapsack:

Item 2 (Weight: 3, Profit: 4)

Item 4 (Weight: 5, Profit: 6)

________________________________________________________________________

12. Aim : To implement Travelling Salesman problem using Branch and Bound approach

Program:

#include <stdio.h>

#include <limits.h>

#include <stdbool.h>

#define N 4 // Number of cities; adjust this for different graph sizes

// Function to print the final solution

void printPath(int path[]) {

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

printf("%d -> ", path[i]);

printf("%d\n", path[0]);

// Function to calculate the minimum edge cost

int findMinEdge(int graph[N][N], int u) {

int min = INT_MAX;

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

if (graph[u][i] != 0 && graph[u][i] < min) {

min = graph[u][i];

}
 return min;

// Function to calculate the second minimum edge cost

int findSecondMinEdge(int graph[N][N], int u) {

int first = INT_MAX, second = INT_MAX;

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

if (graph[u][i] != 0) {

if (graph[u][i] <= first) {

second = first;

first = graph[u][i];

} else if (graph[u][i] < second) {

second = graph[u][i];

return second;

// Recursive function to solve TSP using Branch and Bound

void tspBranchAndBound(int graph[N][N], int currBound, int currWeight, int level, int currPath[], bool
visited[], int *minCost, int finalPath[]) {

// Base case: If all cities are visited, return to the starting city

if (level == N) {

if (graph[currPath[level - 1]][currPath[0]] != 0) {

int currRes = currWeight + graph[currPath[level - 1]][currPath[0]];

// Update minimum cost and final path if needed

if (currRes < *minCost) {

*minCost = currRes;

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

finalPath[i] = currPath[i];

finalPath[N] = currPath[0];
 }

return;

// Iterate through all cities to build the path

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

if (graph[currPath[level - 1]][i] != 0 && !visited[i]) {

int temp = currBound;

currWeight += graph[currPath[level - 1]][i];

// Calculate the new bound for the path

if (level == 1) {

currBound -= (findMinEdge(graph, currPath[level - 1]) + findMinEdge(graph, i)) / 2;

} else {

currBound -= (findSecondMinEdge(graph, currPath[level - 1]) + findMinEdge(graph, i)) / 2;

// If the cost is promising, proceed with the path

if (currBound + currWeight < *minCost) {

currPath[level] = i;

visited[i] = true;

tspBranchAndBound(graph, currBound, currWeight, level + 1, currPath, visited, minCost,

// Backtracking

currWeight -= graph[currPath[level - 1]][i];

currBound = temp;

visited[i] = false;

}
// Function to set up and start the TSP solution

void solveTSP(int graph[N][N]) {

int currPath[N + 1];

int finalPath[N + 1];

bool visited[N];

int currBound = 0;

// Initialize visited array and calculate initial bound

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

visited[i] = false;

currBound += (findMinEdge(graph, i) + findSecondMinEdge(graph, i));

// Initial bound should be rounded down

currBound = (currBound & 1) ? currBound / 2 + 1 : currBound / 2;

// Start at the first city

visited[0] = true;

currPath[0] = 0;

int minCost = INT_MAX;

// Run the recursive TSP Branch and Bound function

tspBranchAndBound(graph, currBound, 0, 1, currPath, visited, &minCost, finalPath);

// Print the results

printf("Minimum cost: %d\n", minCost);

printf("Path taken: ");

printPath(finalPath);

int main() {

// Example graph (distance matrix)

int graph[N][N] = {

{0, 10, 15, 20},

{10, 0, 35, 25},

{15, 35, 0, 30},

};

// Solve TSP for the given graph

solveTSP(graph);

return 0;

Output:

Minimum cost: 80

Path taken: 0 -> 1 -> 3 -> 2 -> 0