3a.
✅ C Program: BFT and DFT using Adjacency Matrix
#include <stdio.h>
#define MAX 10
int adj[MAX][MAX]; // adjacency matrix
int visited[MAX]; // visited array
int n; // number of vertices
// Function to perform DFS
void DFS(int v) {
int i;
printf("%d ", v);
visited[v] = 1;
for (i = 0; i < n; i++) {
if (adj[v][i] == 1 && visited[i] == 0) {
DFS(i);
}
}
}
// Function to perform BFS
void BFS(int start) {
int queue[MAX], front = 0, rear = -1;
int i, v;
for (i = 0; i < n; i++)
visited[i] = 0;
printf("%d ", start);
visited[start] = 1;
queue[++rear] = start;
while (front <= rear) {
v = queue[front++];
for (i = 0; i < n; i++) {
if (adj[v][i] == 1 && visited[i] == 0) {
printf("%d ", i);
visited[i] = 1;
queue[++rear] = i;
}
}
}
}
int main() {
int i, j, start;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter adjacency matrix (%d x %d):\n", n, n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &adj[i][j]);
printf("Enter starting vertex (0 to %d): ", n - 1);
scanf("%d", &start);
// DFS
for (i = 0; i < n; i++)
visited[i] = 0;
printf("\nDepth First Traversal (DFT): ");
DFS(start);
// BFS
printf("\nBreadth First Traversal (BFT): ");
BFS(start);
return 0;
}
---
🧠 Example Input
Enter number of vertices: 4
Enter adjacency matrix (4 x 4):
0110
1001
1001
0110
Enter starting vertex (0 to 3): 0
📤 Output
Depth First Traversal (DFT): 0 1 3 2
Breadth First Traversal (BFT): 0 1 2 3
[Link] Job sequencing with deadlines using Greedy strategy.
#include <stdio.h>
#include <stdlib.h>
struct Job {
char id;
int deadline;
int profit;
};
int main() {
int n, i, j, max = 0;
struct Job job[10];
int slot[10];
printf("Enter number of jobs: ");
scanf("%d", &n);
for (i = 0; i < n; i++) {
printf("Job id, deadline, profit: ");
scanf(" %c %d %d", &job[i].id, &job[i].deadline, &job[i].profit);
if (job[i].deadline > max)
max = job[i].deadline;
}
// Sort by profit (descending)
for (i = 0; i < n - 1; i++)
for (j = i + 1; j < n; j++)
if (job[i].profit < job[j].profit) {
struct Job temp = job[i];
job[i] = job[j];
job[j] = temp;
}
for (i = 0; i < max; i++) slot[i] = -1;
// Schedule jobs
for (i = 0; i < n; i++) {
for (j = job[i].deadline - 1; j >= 0; j--) {
if (slot[j] == -1) {
slot[j] = i;
break;
}
}
}
printf("\nJob sequence: ");
for (i = 0; i < max; i++)
if (slot[i] != -1)
printf("%c ", job[slot[i]].id);
return 0;
}
[Link] a program to solve 0/1 Knapsack problem Using Dynamic Programming.
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int main() {
int n, W, i, w;
int wt[20], val[20], K[20][20];
printf("Enter number of items: ");
scanf("%d", &n);
printf("Enter knapsack capacity: ");
scanf("%d", &W);
printf("Enter weight and value of each item:\n");
for (i = 1; i <= n; i++)
scanf("%d %d", &wt[i], &val[i]);
// Build table K[][] using Dynamic Programming
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i] <= w)
K[i][w] = max(val[i] + K[i-1][w - wt[i]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}
printf("\nMaximum value in knapsack = %d\n", K[n][W]);
return 0;
}
[Link] N-Queens Problem Using Backtracking.
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
int board[MAX], n;
int place(int row, int col) {
for (int i = 1; i < row; i++)
if (board[i] == col || abs(board[i] - col) == abs(i - row))
return 0;
return 1;
}
void print() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
printf("%c ", board[i] == j ? 'Q' : '.');
printf("\n");
}
printf("\n");
}
void NQueen(int row) {
for (int col = 1; col <= n; col++) {
if (place(row, col)) {
board[row] = col;
if (row == n)
print();
else
NQueen(row + 1);
}
}
}
int main() {
printf("Enter number of queens: ");
scanf("%d", &n);
NQueen(1);
return 0;
}.
10. Use Backtracking strategy to solve 0/1 Knapsack problem.
#include <stdio.h>
#include <stdlib.h>
int n, W, wt[10], val[10];
int maxProfit = 0;
void knapsack(int i, int weight, int profit) {
if (weight > W)
return; // invalid state
if (profit > maxProfit)
maxProfit = profit;
if (i == n)
return;
// Include current item
knapsack(i + 1, weight + wt[i], profit + val[i]);
// Exclude current item
knapsack(i + 1, weight, profit);
}
int main() {
printf("Enter number of items: ");
scanf("%d", &n);
printf("Enter knapsack capacity: ");
scanf("%d", &W);
printf("Enter weight and value of each item:\n");
for (int i = 0; i < n; i++)
scanf("%d %d", &wt[i], &val[i]);
knapsack(0, 0, 0);
printf("Maximum profit = %d\n", maxProfit);
return 0;
}
11. Implement Travelling Sales Person problem using Branch and Bound approach.
#include <stdio.h>
#include <stdlib.h>
#define INF 999
#define MAX 10
int n, cost[MAX][MAX], visited[MAX];
int min_cost = INF;
void tsp(int city, int count, int cost_so_far) {
if (count == n && cost[city][0]) {
int total_cost = cost_so_far + cost[city][0];
if (total_cost < min_cost)
min_cost = total_cost;
return;
}
for (int i = 0; i < n; i++) {
if (!visited[i] && cost[city][i]) {
visited[i] = 1;
tsp(i, count + 1, cost_so_far + cost[city][i]);
visited[i] = 0;
}
}
}
int main() {
printf("Enter number of cities: ");
scanf("%d", &n);
printf("Enter cost matrix:\n");
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &cost[i][j]);
for (int i = 0; i < n; i++)
visited[i] = 0;
visited[0] = 1; // start from city 0
tsp(0, 1, 0);
printf("\nMinimum cost of travelling = %d\n", min_cost);
return 0;
}