import java.util.LinkedList;
import java.util.Queue;
public class Graph {
private int[][] adjacencyMatrix; // 2D array to represent the graph's adjacency matrix
private int numVertices; // number of vertices in the graph
public Graph(int numVertices) {
this.numVertices = numVertices;
adjacencyMatrix = new int[numVertices][numVertices]; // initialize the adjacency matrix with 0 values
}
public void addEdge(int src, int dest) {
adjacencyMatrix[src][dest] = 1; // add directed edge from src to dest by setting the corresponding value to 1
}
public void BFS(int startVertex) {
boolean[] visited = new boolean[numVertices]; // array to keep track of visited vertices
Queue<Integer> queue = new LinkedList<Integer>(); // queue to store vertices to be visited
visited[startVertex] = true; // mark the starting vertex as visited
queue.add(startVertex); // add the starting vertex to the queue
while (!queue.isEmpty()) { // loop until all vertices have been visited
int node = queue.poll(); // get the next vertex from the queue
System.out.print(node + " -> "); // output the vertex being visited
for (int i = 0; i < numVertices; i++) { // loop through all vertices
if (adjacencyMatrix[node][i] == 1 && !visited[i]) { // if there is a directed edge from node to i and i has not been visited
visited[i] = true; // mark i as visited
queue.add(i); // add i to the queue to be visited later
}
}
}
System.out.println("Done"); // output message indicating that the BFS is complete
}
public void printMatrix() {
System.out.println("Adjacency matrix representation:");
for (int i = 0; i < numVertices; i++) { // loop through rows of the matrix
for (int j = 0; j < numVertices; j++) { // loop through columns of the matrix
System.out.print(adjacencyMatrix[i][j] + " "); // output the value at the current position of the matrix
}
System.out.println(); // move to the next row
}
}
public static void main(String[] args) {
Graph graph = new Graph(6); // create a graph with 6 vertices
graph.addEdge(0, 1); // add directed edges
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 3);
graph.addEdge(4, 5);
graph.printMatrix(); // output the adjacency matrix
System.out.print("BFS starting from vertex 2: ");
graph.BFS(2); // run BFS starting from vertex 2
}
}