Name- Prajwal Tilekar
Roll no- 75
Problem Statement- Create a graph and implement DFS using adjacency matrix. assignment
1. Objective
To create a graph using an adjacency matrix representation and implement Depth-First Search (DFS)
for graph traversal.
2. Definition
Graph: A collection of vertices (nodes) connected by edges. It can be directed or undirected.
Adjacency Matrix: A 2D array used to represent a graph. If there's an edge between vertex
uuu and vvv, adj[u][v]=1adj[u][v] = 1adj[u][v]=1, otherwise adj[u][v]=0adj[u][v] = 0adj[u]
[v]=0.
Depth-First Search (DFS): A graph traversal technique where the algorithm starts at a node,
explores as far as possible along each branch, and backtracks when necessary.
3. Theory
1. Graph Representation:
o An adjacency matrix is a square matrix of size n×nn \times nn×n, where nnn is the
number of vertices.
o For undirected graphs, the matrix is symmetric.
o For directed graphs, the matrix may not be symmetric.
2. Depth-First Search:
o DFS starts from a specified vertex and visits nodes as deep as possible before
backtracking.
o It is implemented using recursion or a stack.
o The time complexity is O(V2)O(V^2)O(V2) for adjacency matrix representation,
where VVV is the number of vertices.
4. Diagram
0
/\
1 2
/\
3 4
5. Code
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
int vertices; // Number of vertices
vector<vector<int>> adjMatrix; // Adjacency matrix
public:
// Constructor to initialize the graph
Graph(int v) {
vertices = v;
adjMatrix.resize(v, vector<int>(v, 0));
}
// Function to add an edge between two vertices
void addEdge(int u, int v) {
adjMatrix[u][v] = 1;
adjMatrix[v][u] = 1; // For undirected graph
}
// Depth-First Search (DFS) function
void dfs(int start, vector<bool>& visited) {
visited[start] = true; // Mark the current node as visited
cout << "Visited " << start << endl;
// Traverse all adjacent vertices
for (int i = 0; i < vertices; i++) {
if (adjMatrix[start][i] == 1 && !visited[i]) {
dfs(i, visited);
}
}
}
// Helper function to start DFS from a specific node
void startDFS(int start) {
vector<bool> visited(vertices, false); // Initialize visited array
cout << "Depth-First Search Traversal:" << endl;
dfs(start, visited);
}
// Function to print the adjacency matrix
void printAdjMatrix() {
cout << "Adjacency Matrix:" << endl;
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}
};
int main() {
// Create a graph with 5 vertices
Graph g(5);
// Add edges
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
// Print the adjacency matrix
g.printAdjMatrix();
// Perform DFS starting from vertex 0
g.startDFS(0);
return 0;
}
6. Output
