Labsheet 7
Pirajesh M R – AM.EN.U4CSE22042
1.
#include <iostream>
#include <vector>
using namespace std;
class Graph {
int V;
vector<vector<int>> adjMatrix;
public:
Graph(int vertices) {
V = vertices;
adjMatrix.resize(V, vector<int>(V, 0));
void addEdge(int u, int v) {
adjMatrix[u][v] = 1;
void printAdjMatrix() {
cout << "Adjacency Matrix:" << endl;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
cout << adjMatrix[i][j] << " ";
cout << endl;
}
void printAdjacencies() {
for (int i = 0; i < V; i++) {
cout << "Adjacencies of vertex " << i << ": ";
for (int j = 0; j < V; j++) {
if (adjMatrix[i][j] == 1) {
cout << j << " ";
cout << endl;
};
int main() {
int vertices = 5;
Graph g(vertices);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.printAdjMatrix();
g.printAdjacencies();
return 0;
}
2.
#include <iostream>
#include <vector>
using namespace std;
class Graph {
int V;
vector<vector<int>> adjMatrix;
public:
Graph(int vertices) {
V = vertices;
adjMatrix.resize(V, vector<int>(V, 0));
void addEdge(int u, int v) {
adjMatrix[u][v] = 1;
adjMatrix[v][u] = 1;
void printAdjMatrix() {
cout << "Adjacency Matrix:" << endl;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
cout << adjMatrix[i][j] << " ";
cout << endl;
void printAdjacencies() {
for (int i = 0; i < V; i++) {
cout << "Adjacencies of vertex " << i << ": ";
for (int j = 0; j < V; j++) {
if (adjMatrix[i][j] == 1) {
cout << j << " ";
cout << endl;
};
int main() {
int vertices = 5;
Graph g(vertices);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.printAdjMatrix();
g.printAdjacencies();
return 0;
3.
#include <iostream>
#include <vector>
#include <list>
using namespace std;
class Graph {
int V;
vector<list<int>> adjList;
public:
Graph(int vertices) {
V = vertices;
adjList.resize(V);
void addEdge(int u, int v) {
adjList[u].push_back(v);
void printAdjList() {
cout << "Adjacency List:" << endl;
for (int i = 0; i < V; i++) {
cout << i << ": ";
for (int neighbor : adjList[i]) {
cout << neighbor << " ";
cout << endl;
void printAdjacencies() {
for (int i = 0; i < V; i++) {
cout << "Adjacencies of vertex " << i << ": ";
for (int neighbor : adjList[i]) {
cout << neighbor << " ";
cout << endl;
};
int main() {
int vertices = 5;
Graph g(vertices);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.printAdjList();
g.printAdjacencies();
return 0;
Adjacency Matrix (Program 1 and 2)
Best-case time complexity: O(1) for checking the presence of an edge.
Worst-case time complexity: O(V^2) for storing the graph, where V is the number of vertices.
Adjacency List (Program 3)
Best-case time complexity: O(1) for adding an edge.Worst-case time complexity: O(V + E) for storing
the graph, where V is the number of vertices and E is the number of edges.
4.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
int V;
vector<vector<int>> adjList;
public:
Graph(int vertices) {
V = vertices;
adjList.resize(V);
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u);
void findDistances(int s) {
vector<int> distance(V, -1);
queue<int> q;
distance[s] = 0;
q.push(s);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : adjList[node]) {
if (distance[neighbor] == -1) {
distance[neighbor] = distance[node] + 1;
q.push(neighbor);
for (int i = 0; i < V; i++) {
if (distance[i] == -1) {
cout << "Vertex " << i << " is unreachable from vertex " << s << endl;
} else {
cout << "Distance from vertex " << s << " to vertex " << i << " is " << distance[i] << endl;
};
int main() {
int vertices, edges, u, v, s;
cout << "Enter the number of vertices: ";
cin >> vertices;
Graph g(vertices);
cout << "Enter the number of edges: ";
cin >> edges;
cout << "Enter the edges (u v):" << endl;
for (int i = 0; i < edges; i++) {
cin >> u >> v;
g.addEdge(u, v);
}
cout << "Enter the source vertex: ";
cin >> s;
g.findDistances(s);
return 0;
The time complexity of the BFS algorithm used in this code is O(V + E), where V is the number of
vertices and E is the number of edges. This is because each vertex and each edge is processed once.
5.
class Solution {
public:
void DFS(int node, vector<int> &vec, vector<vector<int>>& isConnected) {
for(int i = 0; i < isConnected[0].size(); i++) {
if(isConnected[node][i] && vec[i]==0) {
vec[i] = 1;
DFS(i, vec, isConnected);
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected[0].size();
vector<int> vec(n,0);
int count = 0;
for(int i = 0; i < n; i++) {
if(!vec[i]) {
DFS(i, vec, isConnected);
count++;
return count;
};
6.
#include <vector>
using namespace std;
class Solution {
public:
void dfs(vector<vector<char>>& grid, int i, int j) {
int m = grid.size();
int n = grid[0].size();
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
return;
grid[i][j] = '0';
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
int numIslands(vector<vector<char>>& grid) {
if (grid.empty()) {
return 0;
int m = grid.size();
int n = grid[0].size();
int num_islands = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
++num_islands;
dfs(grid, i, j);
}
return num_islands;
};
7.
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
queue<pair<int, int>> q;
int freshCount = 0;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (grid[i][j] == 2) {
q.push({i, j});
} else if (grid[i][j] == 1) {
++freshCount;
if (freshCount == 0) return 0;
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int minutes = 0;
while (!q.empty()) {
int size = q.size();
bool hasRotten = false;
for (int i = 0; i < size; ++i) {
auto [row, col] = q.front();
q.pop();
for (auto [dr, dc] : directions) {
int newRow = row + dr;
int newCol = col + dc;
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow]
[newCol] == 1) {
grid[newRow][newCol] = 2;
q.push({newRow, newCol});
--freshCount;
hasRotten = true;
if (hasRotten) ++minutes;
return freshCount == 0 ? minutes : -1;
};
8.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Graph {
int V;
vector<vector<int>> adj;
public:
Graph(int vertices) {
V = vertices;
adj.resize(V);
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
void DFSUtil(int node, vector<bool> &visited, vector<int> &component) {
visited[node] = true;
component.push_back(node);
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
DFSUtil(neighbor, visited, component);
void connectedComponents() {
vector<bool> visited(V, false);
for (int i = 0; i < V; ++i) {
if (!visited[i]) {
vector<int> component;
DFSUtil(i, visited, component);
for (int node : component) {
cout << node << " ";
cout << endl;
};
int main() {
int vertices = 7;
Graph g(vertices);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(5, 6);
g.connectedComponents();
return 0;
9.
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
void bfs(vector<vector<char>>& grid, int i, int j) {
int m = grid.size();
int n = grid[0].size();
queue<pair<int, int>> q;
q.push({i, j});
grid[i][j] = '0';
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (auto [dx, dy] : directions) {
int newX = x + dx;
int newY = y + dy;
if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == '1') {
grid[newX][newY] = '0';
q.push({newX, newY});
int numIslands(vector<vector<char>>& grid) {
if (grid.empty()) {
return 0;
int m = grid.size();
int n = grid[0].size();
int num_islands = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
++num_islands;
bfs(grid, i, j);
return num_islands;
};
10.
class Solution {
public:
bool dfs(vector<vector<char>>& board, string& word, int i, int j, int index) {
if (index == word.size()) return true;
int m = board.size();
int n = board[0].size();
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[index]) {
return false;
char temp = board[i][j];
board[i][j] = '#';
bool found = dfs(board, word, i - 1, j, index + 1) ||
dfs(board, word, i + 1, j, index + 1) ||
dfs(board, word, i, j - 1, index + 1) ||
dfs(board, word, i, j + 1, index + 1);
board[i][j] = temp;
return found;
bool exist(vector<vector<char>>& board, string word) {
int m = board.size();
int n = board[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == word[0] && dfs(board, word, i, j, 0)) {
return true;
return false;
};
