AIM: Implement BFT and DFT for given graph, when graph is represented by
(i) Adjacency Matrix (ii) Adjacency Lists
(i) Breadth-First Traversal (BFT) using Adjacency Matrix
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void BFT_Matrix(vector<vector<int> > &adjMatrix, int startVertex) {
int numVertices = [Link]();
vector<bool> visited(numVertices, false);
queue<int> q;
visited[startVertex] = true;
[Link](startVertex);
while (![Link]()) {
int vertex = [Link]();
[Link]();
cout << vertex << " ";
for (int i = 0; i < numVertices; ++i) {
if (adjMatrix[vertex][i] == 1 && !visited[i]) {
visited[i] = true;
[Link](i);
}
}
}
}
int main() {
int numVertices = 4;
vector<vector<int> > adjMatrix(numVertices, vector<int>(numVertices, 0));
// Manually setting up the adjacency matrix
adjMatrix[0][1] = 1; adjMatrix[0][2] = 1;
adjMatrix[1][0] = 1; adjMatrix[1][2] = 1; adjMatrix[1][3] = 1;
adjMatrix[2][0] = 1; adjMatrix[2][1] = 1; adjMatrix[2][3] = 1;
adjMatrix[3][1] = 1; adjMatrix[3][2] = 1;
cout << "BFT using Adjacency Matrix: ";
BFT_Matrix(adjMatrix, 0); // Start from vertex 0
return 0;
}
Output:
BFT using Adjacency Matrix: 0 1 2 3
Explanation:
HEADER FILES
#include <iostream>
● Includes the input/output stream library. Needed for cout.
#include <queue>
● Includes the queue container for Breadth-First Traversal (BFS).
#include <vector>
● Includes the vector container for dynamic arrays.
NAMESPACE
using namespace std;
● This allows us to use names like vector, queue, and cout without prefixing them
with std::.
BREADTH-FIRST TRAVERSAL FUNCTION
void BFT_Matrix(vector<vector<int> > &adjMatrix, int startVertex)
{
● Defines a function named BFT_Matrix.
● Takes:
○ a reference to a 2D vector adjMatrix (the adjacency matrix),
○ an integer startVertex (starting node for traversal).
int numVertices = [Link]();
● Gets the number of vertices from the size of the matrix.
vector<bool> visited(numVertices, false);
● Creates a boolean vector to keep track of visited vertices. Initially, all set to false.
queue<int> q;
● Declares a queue for BFS traversal.
visited[startVertex] = true;
[Link](startVertex);
● Marks the starting vertex as visited and pushes it into the queue.
BFS LOOP
while (![Link]()) {
● Continue until the queue becomes empty.
int vertex = [Link]();
[Link]();
cout << vertex << " ";
● Gets the front element (current vertex), removes it from the queue, and prints it.
for (int i = 0; i < numVertices; ++i) {
● Loop through all vertices to find neighbors of the current vertex.
if (adjMatrix[vertex][i] == 1 && !visited[i]) {
● Checks if i is a neighbor of vertex (i.e., adjMatrix[vertex][i] == 1) and
hasn't been visited.
visited[i] = true;
[Link](i);
● Marks neighbor as visited and enqueues it.
MAIN FUNCTION
int main() {
● Entry point of the program.
int numVertices = 4;
● Declares number of vertices (4 nodes).
vector<vector<int> > adjMatrix(numVertices,
vector<int>(numVertices, 0));
● Initializes a 4x4 adjacency matrix with all elements 0.
SETUP ADJACENCY MATRIX (UNDIRECTED GRAPH)
adjMatrix[0][1] = 1; adjMatrix[0][2] = 1;
adjMatrix[1][0] = 1; adjMatrix[1][2] = 1; adjMatrix[1][3] =
1;
adjMatrix[2][0] = 1; adjMatrix[2][1] = 1; adjMatrix[2][3] =
1;
adjMatrix[3][1] = 1; adjMatrix[3][2] = 1;
● Sets the connections between nodes:
○ 0 is connected to 1 and 2
○ 1 is connected to 0, 2, 3
○ 2 is connected to 0, 1, 3
○ 3 is connected to 1, 2
Since it’s an undirected graph, connections are symmetric: if a is connected to b,
then b is connected to a.
CALL THE BFT FUNCTION
cout << "BFT using Adjacency Matrix: ";
● Print heading for output.
BFT_Matrix(adjMatrix, 0); // Start from vertex 0
● Calls the function to perform BFT starting from vertex 0.
return 0;
}
● Ends the program.
SAMPLE OUTPUT
Given the adjacency matrix, BFT starting from vertex 0 would visit:
0 1 2 3
(Visited in breadth-first order: start at 0 neighbors 1 & 2 neighbor of 1 is 3)
(ii) Depth-First Traversal (DFT) using Adjacency Matrix
#include <iostream>
#include <vector>
using namespace std;
void DFT_Matrix(vector<vector<int> > &adjMatrix, vector<bool> &visited, int vertex) {
visited[vertex] = true;
cout << vertex << " ";
for (int i = 0; i < [Link](); ++i) {
if (adjMatrix[vertex][i] == 1 && !visited[i]) {
DFT_Matrix(adjMatrix, visited, i);
}
}
}
int main() {
int numVertices = 4;
vector<vector<int> > adjMatrix(numVertices, vector<int>(numVertices, 0));
// Manually setting up the adjacency matrix
adjMatrix[0][1] = 1; adjMatrix[0][2] = 1;
adjMatrix[1][0] = 1; adjMatrix[1][2] = 1; adjMatrix[1][3] = 1;
adjMatrix[2][0] = 1; adjMatrix[2][1] = 1; adjMatrix[2][3] = 1;
adjMatrix[3][1] = 1; adjMatrix[3][2] = 1;
vector<bool> visited(numVertices, false);
cout << "DFT using Adjacency Matrix: ";
DFT_Matrix(adjMatrix, visited, 0); // Start from vertex 0
return 0;
}
Output:
DFT using Adjacency Matrix: 0 1 2 3
Explanation:
HEADER FILES
#include <iostream>
● Includes input/output stream functionality for cout.
#include <vector>
● Includes the vector container, used to store the adjacency matrix and visited list.
NAMESPACE
using namespace std;
● Avoids needing to write std:: before cout, vector, etc.
DEPTH-FIRST TRAVERSAL FUNCTION
void DFT_Matrix(vector<vector<int> > &adjMatrix, vector<bool>
&visited, int vertex) {
● A recursive function for Depth-First Traversal (DFT).
● Takes:
○ adjMatrix: the graph as a 2D vector (adjacency matrix).
○ visited: a boolean vector to track visited nodes.
○ vertex: the current node to process.
visited[vertex] = true;
cout << vertex << " ";
● Marks the current vertex as visited and prints it.
for (int i = 0; i < [Link](); ++i) {
● Iterates through all possible vertices (0 to N-1).
if (adjMatrix[vertex][i] == 1 && !visited[i]) {
DFT_Matrix(adjMatrix, visited, i);
}
● If there is an edge from vertex to i and i is not visited, recursively call DFT_Matrix
for vertex i.
MAIN FUNCTION
int main() {
● Starting point of the program.
int numVertices = 4;
● Declares a graph with 4 vertices (0, 1, 2, 3).
vector<vector<int> > adjMatrix(numVertices,
vector<int>(numVertices, 0));
● Initializes a 4x4 adjacency matrix with all entries as 0.
SETUP ADJACENCY MATRIX (UNDIRECTED GRAPH)
adjMatrix[0][1] = 1; adjMatrix[0][2] = 1;
adjMatrix[1][0] = 1; adjMatrix[1][2] = 1; adjMatrix[1][3] =
1;
adjMatrix[2][0] = 1; adjMatrix[2][1] = 1; adjMatrix[2][3] =
1;
adjMatrix[3][1] = 1; adjMatrix[3][2] = 1;
● Manually connects the vertices as follows:
○ 0 is connected to 1 and 2
○ 1 is connected to 0, 2, 3
○ 2 is connected to 0, 1, 3
○ 3 is connected to 1 and 2
Since the graph is undirected, every edge is symmetric (i.e., adjMatrix[i][j]
= 1 means adjMatrix[j][i] = 1).
INITIALIZE VISITED VECTOR
vector<bool> visited(numVertices, false);
● A vector to keep track of which vertices have been visited. All initialized to false.
CALL THE DFT FUNCTION
cout << "DFT using Adjacency Matrix: ";
● Displays a message before printing the traversal result.
DFT_Matrix(adjMatrix, visited, 0); // Start from vertex 0
● Starts Depth-First Traversal from vertex 0.
return 0;
}
● Ends the program.
SAMPLE OUTPUT
The output would be:
DFT using Adjacency Matrix: 0 1 2 3
Depending on how the graph is connected and how neighbors are ordered, the exact
order can vary, but it reflects Depth-First behavior: go deep into one path before
backtracking.
KEY DIFFERENCE FROM BFT:
● DFT uses recursion and a call stack (depth first).
● BFT uses a queue (breadth first).
(iii) Breadth-First Traversal (BFT) using Adjacency List
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void BFT_List(vector<vector<int> > &adjList, int startVertex) {
int numVertices = [Link]();
vector<bool> visited(numVertices, false);
queue<int> q;
visited[startVertex] = true;
[Link](startVertex);
while (![Link]()) {
int vertex = [Link]();
[Link]();
cout << vertex << " ";
// Using traditional for loop instead of range-based for loop
for (int i = 0; i < adjList[vertex].size(); ++i) {
int adjVertex = adjList[vertex][i];
if (!visited[adjVertex]) {
visited[adjVertex] = true;
[Link](adjVertex);
}
}
}
}
int main() {
int numVertices = 4;
vector<vector<int> > adjList(numVertices);
// Manually setting up the adjacency list
adjList[0].push_back(1); adjList[0].push_back(2);
adjList[1].push_back(0); adjList[1].push_back(2); adjList[1].push_back(3);
adjList[2].push_back(0); adjList[2].push_back(1); adjList[2].push_back(3);
adjList[3].push_back(1); adjList[3].push_back(2);
cout << "BFT using Adjacency List: ";
BFT_List(adjList, 0); // Start from vertex 0
return 0;
}
Output:
BFT using Adjacency List: 0 1 2 3
Explanation:
HEADER FILES
#include <iostream>
● For standard input/output like cout.
#include <queue>
● For queue container used in BFS.
#include <vector>
● For vector, used to represent the adjacency list.
NAMESPACE
using namespace std;
● So you don’t need to prefix std:: everywhere.
BREADTH-FIRST TRAVERSAL FUNCTION
void BFT_List(vector<vector<int> > &adjList, int startVertex) {
● Function to perform BFT on a graph using adjacency list.
● Parameters:
○ adjList: the graph.
○ startVertex: starting point for traversal.
int numVertices = [Link]();
● Finds total number of vertices in the graph.
vector<bool> visited(numVertices, false);
● Boolean vector to track visited vertices.
queue<int> q;
● Queue for BFS traversal.
visited[startVertex] = true;
[Link](startVertex);
● Start from the startVertex, mark it visited and enqueue it.
BFS LOOP
while (![Link]()) {
● Continue until the queue is empty.
int vertex = [Link]();
[Link]();
cout << vertex << " ";
● Remove the front vertex and print it.
for (int i = 0; i < adjList[vertex].size(); ++i) {
● Traverse all neighbors of the current vertex using a for-loop.
int adjVertex = adjList[vertex][i];
if (!visited[adjVertex]) {
visited[adjVertex] = true;
[Link](adjVertex);
}
● For each neighbor:
○ If it’s not visited, mark as visited and enqueue it.
MAIN FUNCTION
int main() {
● Program starts here.
int numVertices = 4;
vector<vector<int> > adjList(numVertices);
● Creates an adjacency list with 4 vertices.
GRAPH STRUCTURE (Manual Setup)
adjList[0].push_back(1); adjList[0].push_back(2);
adjList[1].push_back(0); adjList[1].push_back(2);
adjList[1].push_back(3);
adjList[2].push_back(0); adjList[2].push_back(1);
adjList[2].push_back(3);
adjList[3].push_back(1); adjList[3].push_back(2);
Adjacency List (Undirected Graph):
0 1, 2
1 0, 2, 3
2 0, 1, 3
3 1, 2
This graph structure looks like:
0
/ \
1---2
\ /
3
CALL TO BFT FUNCTION
cout << "BFT using Adjacency List: ";
BFT_List(adjList, 0); // Start from vertex 0
● Displays the output message and starts BFS from vertex 0.
return 0;
}
● End of program.
Dry Run of BFT from Vertex 0
Initial state:
● visited: [true, false, false, false]
● queue: [0]
Step-by-Step:
1. Pop 0
○ Print: 0
○ Neighbors of 0: [1, 2]
○ Enqueue: 1 and 2
○ visited: [true, true, true, false]
○ queue: [1, 2]
2. Pop 1
○ Print: 1
○ Neighbors: [0, 2, 3]
○ 0 and 2 already visited
○ Enqueue 3
○ visited: [true, true, true, true]
○ queue: [2, 3]
3. Pop 2
○ Print: 2
○
Neighbors: [0, 1, 3] all visited
○ queue: [3]
4. Pop 3
○ Print: 3
○
Neighbors: [1, 2] already visited
○ queue: []
Final Output:
BFT using Adjacency List: 0 1 2 3
(iv) Depth-First Traversal (DFT) using Adjacency List
#include <iostream>
#include <vector>
using namespace std;
void DFT_List(vector<vector<int> > &adjList, vector<bool> &visited, int vertex) {
visited[vertex] = true;
cout << vertex << " ";
// Using traditional for loop instead of range-based for loop
for (int i = 0; i < adjList[vertex].size(); ++i) {
int adjVertex = adjList[vertex][i];
if (!visited[adjVertex]) {
DFT_List(adjList, visited, adjVertex);
}
}
}
int main() {
int numVertices = 4;
vector<vector<int> > adjList(numVertices);
// Manually setting up the adjacency list
adjList[0].push_back(1); adjList[0].push_back(2);
adjList[1].push_back(0); adjList[1].push_back(2); adjList[1].push_back(3);
adjList[2].push_back(0); adjList[2].push_back(1); adjList[2].push_back(3);
adjList[3].push_back(1); adjList[3].push_back(2);
vector<bool> visited(numVertices, false);
cout << "DFT using Adjacency List: ";
DFT_List(adjList, visited, 0); // Start from vertex 0
return 0;
}
Output:
DFT using Adjacency List: 0 1 2 3
Explanation:
HEADER FILES
#include <iostream>
● For input/output like cout.
#include <vector>
● For using vector, which implements the adjacency list and visited array.
NAMESPACE
using namespace std;
● So you don’t need to write std:: for every standard object.
DEPTH-FIRST TRAVERSAL FUNCTION
void DFT_List(vector<vector<int> > &adjList, vector<bool>
&visited, int vertex)
● Recursive function for DFT using an adjacency list.
● Takes:
○ adjList: the graph in list form,
○ visited: boolean list to track visited nodes,
○ vertex: the current node being visited.
visited[vertex] = true;
cout << vertex << " ";
● Mark current node as visited and print it.
for (int i = 0; i < adjList[vertex].size(); ++i) {
● Loop through all neighbors of the current node.
int adjVertex = adjList[vertex][i];
if (!visited[adjVertex]) {
DFT_List(adjList, visited, adjVertex);
}
● If neighbor is not visited, recursively call DFT_List on it.
MAIN FUNCTION
int main() {
● Program execution starts here.
int numVertices = 4;
vector<vector<int> > adjList(numVertices);
● Declares a graph with 4 vertices and initializes the adjacency list.
GRAPH STRUCTURE (MANUAL SETUP)
adjList[0].push_back(1); adjList[0].push_back(2);
adjList[1].push_back(0); adjList[1].push_back(2);
adjList[1].push_back(3);
adjList[2].push_back(0); adjList[2].push_back(1);
adjList[2].push_back(3);
adjList[3].push_back(1); adjList[3].push_back(2);
This creates the same graph structure as before:
Adjacency List:
0 1, 2
1 0, 2, 3
2 0, 1, 3
3 1, 2
Undirected Graph:
0
/ \
1---2
\ /
3
SETUP AND FUNCTION CALL
vector<bool> visited(numVertices, false);
● Initializes visited list with false for all nodes.
cout << "DFT using Adjacency List: ";
DFT_List(adjList, visited, 0); // Start from vertex 0
● Print header and start DFT from node 0.
return 0;
}
● Program ends.
Dry Run of DFT from Vertex 0
Initial State:
● visited = [false, false, false, false]
● Starting vertex: 0
Step-by-Step Trace:
1. DFT(0)
○ Visit 0 Print 0, mark visited[0] = true
○ Neighbors: [1, 2]
○ Call DFT(1)
2. DFT(1)
○ Visit 1 Print 1, mark visited[1] = true
○ Neighbors: [0 (visited), 2, 3]
○ Call DFT(2)
3. DFT(2)
○ Visit 2 Print 2, mark visited[2] = true
○ Neighbors: [0, 1 (visited), 3]
○ Call DFT(3)
4. DFT(3)
○ Visit 3 Print 3, mark visited[3] = true
○ Neighbors: [1, 2] (already visited)
○
Return to DFT(2) done
○
Return to DFT(1) done
○
Return to DFT(0) done
Output:
DFT using Adjacency List: 0 1 2 3
Diagram: Traversal Path
Traversal: 0 1 2 3
0
/ \
v \
1 --> 2
\ |
\ v
3