K V S J JASWANTH VU22CSEN0500128
INTERMEDIATE CODING
ASSIGNMENT-04
1) Graph Traversals:Given a graph, traverse it in BFS and DFS orders.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_NODES 100
typedef struct Graph {
int num_nodes;
int adj_list[MAX_NODES][MAX_NODES];
} Graph;
void bfs(Graph* graph, int start_node) {
bool visited[MAX_NODES] = {false};
int queue[MAX_NODES], front = 0, rear = -1;
visited[start_node] = true;
queue[++rear] = start_node;
while (front <= rear) {
int current_node = queue[front++];
printf("%d ", current_node);
for (int i = 0; i < graph->num_nodes; i++) {
if (graph->adj_list[current_node][i] &&
!visited[i]) {
visited[i] = true;
queue[++rear] = i;
}
}
}
printf("\n");
}
void dfs(Graph* graph, int current_node, bool
visited[]) {
visited[current_node] = true;
printf("%d ", current_node);
for (int i = 0; i < graph->num_nodes; i++) {
if (graph->adj_list[current_node][i] &&
!visited[i]) {
dfs(graph, i, visited);
}
}
}
K V S J JASWANTH VU22CSEN0500128
int main() {
Graph graph;
graph.num_nodes = 5;
int adj_matrix[5][5] = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 0},
{1, 0, 0, 1, 1},
{0, 1, 1, 0, 1},
{0, 0, 1, 1, 0}
};
for(int i=0; i < graph.num_nodes; ++i) {
for(int j=0; j < graph.num_nodes; ++j) {
graph.adj_list[i][j] = adj_matrix[i][j];
}
}
printf("BFS traversal starting from node 0: ");
bfs(&graph, 0);
bool visited_dfs[MAX_NODES] = {false};
printf("DFS traversal starting from node 0: ");
dfs(&graph, 0, visited_dfs);
printf("\n");
return 0;
}
K V S J JASWANTH VU22CSEN0500128
2) Number of districts: A map with cities is represented as a graph, where each node
represents a city and each edge represents a (two-way) road from the city. A district is a
group of directly or indirectly connected cities. Given the graph of a country, count the
number of districts in it.
#include <stdio.h>
#include <stdbool.h>
#define MAX_NODES 100
typedef struct Graph {
int num_nodes;
int adj_list[MAX_NODES][MAX_NODES];
} Graph;
void dfs(Graph* graph, int current_node, bool
visited[]) {
visited[current_node] = true;
for (int i = 0; i < graph->num_nodes; i++) {
if (graph->adj_list[current_node][i] &&
!visited[i]) {
dfs(graph, i, visited);
}
}
}
int count_districts(Graph* graph) {
bool visited[MAX_NODES] = {false};
int num_districts = 0;
for (int i = 0; i < graph->num_nodes; i++) {
if (!visited[i]) {
dfs(graph, i, visited);
num_districts++;
}
}
return num_districts;
}
int main() {
Graph graph;
graph.num_nodes = 7;
int adj_matrix[7][7] = {
{0, 1, 1, 0, 0, 0, 0},
{1, 0, 0, 1, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 1},
{0, 0, 0, 0, 1, 0, 1},
{0, 0, 0, 0, 1, 1, 0}
};
K V S J JASWANTH VU22CSEN0500128
for (int i = 0; i < graph.num_nodes; ++i) {
for (int j = 0; j < graph.num_nodes; ++j) {
graph.adj_list[i][j] = adj_matrix[i][j];
}
}
int districts = count_districts(&graph);
printf("Number of districts: %d\n", districts);
return 0;
}
K V S J JASWANTH VU22CSEN0500128
3) You are given an m x n array where each cell can have 0 (represents an empty cell), 1
(represents a good apple) or 2 (represents a bad apple). Starting from day1, all the four
apples adjacent (top, bottom or diagnol) to each rotten apple also become rotten. What is
the minimum number of days before which all the apples are rotten? If they never get
rotten, return -1.
#include <stdio.h>
#include <stdbool.h>
#define MAX_ROWS 50
#define MAX_COLS 50
int min_days_rotten(int grid[MAX_ROWS][MAX_COLS], int
m, int n) {
int days = 0;
bool changed = true;
while (changed) {
changed = false;
int temp_grid[MAX_ROWS][MAX_COLS];
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
temp_grid[i][j] = grid[i][j];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
for (int k = 0; k < 4; k++) {
int ni = i + dx[k];
int nj = j + dy[k];
if (ni >= 0 && ni < m && nj >=
0 && nj < n && temp_grid[ni][nj] == 1) {
temp_grid[ni][nj] = 2;
changed = true;
}
}
}
}
}
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
grid[i][j] = temp_grid[i][j];
}
}
K V S J JASWANTH VU22CSEN0500128
if (changed) {
days++;
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
return -1;
}
}
}
return days;
}
int main(){
int m = 3, n = 3;
int grid[MAX_ROWS][MAX_COLS] = {
{2, 1, 1},
{1, 1, 0},
{0, 1, 1}
};
int days = min_days_rotten(grid, m, n);
printf("Minimum days to rot: %d\n", days);
return 0;
}
