Green University of Bangladesh
Department of Computer Science and Engineering (CSE)
Faculty of Sciences and Engineering
Semester: (Spring, Year:2022), B.Sc. in CSE (Day)
LAB REPORT NO: 02
Course Title: Algorithms Lab
Course Code: CSE 206 Section: 203DB
Lab Experiment Name: Implement Breadth-First Search Traversal
Student Details
Name ID
1. Md. Al Imran Suvo 203002044
Lab Date : 07/ 03/ 2022
Submission Date : 14/ 03/ 2022
Course Teacher’s Name : Md. Gulzar Hussain
[For Teachers use only: Don’t Write Anything inside this box]
Lab Report Status
Marks: ………………………………… Signature:.....................
Comments:.............................................. Date:..............................
1. TITLE OF THE LAB EXPERIMENT
Implement Implement Breadth-First Search Traversal in Java
2. OBJECTIVES
• To understand how to represent a graph using an adjacency matrix.
• To understand how Breadth-First Search (BFS) works.
3. PROBLEM ANALYSIS
Every graph is a set of points referred to as vertices or nodes which are connected using lines called
edges. The vertices represent entities in a graph. Edges, on the other hand, express relationships between
entities. Hence, while nodes model entities, edges model relationships in a network graph. A graph G with
a set of V vertices together with a set of E edges is represented as G= (V, E). Both vertices and edges can
have additional attributes that are used to describe the entities and relationships. Figure 1 depicts a simple
graph with five nodes and seven edges.
Figure 1: A simple graph
Adjacency Matrix:
Vertices are labeled (or re-labelled) with integers from 0 to V (G) - 1. A two-dimensional array “matrix”
with dimensions V (G) * V (G) contains a 1 at matrix [j] [k] if there is an edge from the vertex labeled j to the
vertex labeled k, and a 0 otherwise.Table:1 represents the graph of figure:1;
4. ALGORITHM
Step 1. Set i=0, e = Number of edges.
Step 2. e (number of edge) < i (Decision). • if no - continue with the step 7.
Step 3. Take the values of edge by giving the adjacency nodes [j], [k] (A, B, C, D,
E=0,1,2,3,4). Step 4. matrix[j][k] =matrix[k][j] =1.
Step 5. Increment i (i++).
Step 6. continue with the step 2.
Step 7. Stop.
5. IMPLEMENT IN JAVA
package graph;
import java.util.*;
import java.io.*;
class Graph
{
private int V;
private LinkedList<Integer> adj[];
Graph(int v){
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v,int w)
{
adj[v].add(w);
}
void BFS(int s)
{
boolean visited[] = new boolean[V];
LinkedList<Integer> queue = new LinkedList<Integer>();
visited[s]=true;
queue.add(s);
while (queue.size() != 0)
{
s = queue.poll();
System.out.print(s+" ");
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext())
{
int n = i.next();
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("Breadth First Traversal is: "+
"(starting from vertex 1)");
g.BFS(1);
}
}
5. OUTPUT
6. DISCUSSION & CONCLUSION
Based on the focused objective(s) to understand about this algorithm, the additional lab exercise made me
more confident towards the fulfillment of the objectives(s).
