BFS in graph (code in JAVA)
import java.util.*;
public class graph {
// Function to return Breadth First Traversal of given graph.
public static ArrayList<Integer> bfsOfGraph(int numNodes, ArrayList<ArrayList<Integer>> adj) {
ArrayList < Integer > bfs = new ArrayList < > (); // stores ans
boolean vis[] = new boolean[numNodes + 1];
Queue < Integer > q = new LinkedList < > ();
// keep any node from where you want to start your bfs
q.add(1); // keep value of node here, if your node has 0 then you should keep it
vis[1] = true;
while (!q.isEmpty()) {
int levelSize = q.size(); // Number of nodes at the current level
for (int i = 0; i < levelSize; i++) {
Integer node = q.poll();
bfs.add(node);
for (Integer it : adj.get(node)) {
if (!vis[it]) {
vis[it] = true;
q.add(it);
}
}
}
bfs.add(-1); // Add a marker (-1) to separate levels
}
return bfs;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Input the number of nodes.
System.out.print("Enter the number of nodes: ");
int numNodes = scanner.nextInt();
// Create an adjacency list.
ArrayList<ArrayList<Integer>> adjList = new ArrayList<>(numNodes);
for (int i = 0; i < numNodes + 1; i++) { // numNodes + 2 only if remove empty zero index
adjList.add(new ArrayList<>());
}
// Input the number of edges.
System.out.print("Enter the number of edges: ");
int numEdges = scanner.nextInt();
// Input the edges (connections between nodes).
System.out.println("Enter the edges (startNode endNode):");
for (int i = 0; i < numEdges; i++) {
int startNode = scanner.nextInt();
int endNode = scanner.nextInt();
// Add an edge from startNode to endNode (for directed graph).
adjList.get(startNode).add(endNode);
// For undirected graph, add the reverse edge as well.
adjList.get(endNode).add(startNode); // Uncomment this line for an undirected graph.
}
// Print the adjacency list.
System.out.println("Adjacency List:");
for (int i = 1; i < numNodes + 1; i++) {
System.out.print(i + " -> ");
for (int neighbor : adjList.get(i)) {
System.out.print(neighbor + " ");
}
System.out.println();
}
// BFS of graph
System.out.println("The bfs of the given graph is:");
ArrayList<Integer> bfsResult = bfsOfGraph(numNodes, adjList);
for (Integer node : bfsResult) {
if (node == -1) {
System.out.println(); // Print a newline for each level
} else {
System.out.print(node + " ");
}
}
scanner.close();
}
}
No comments:
Post a Comment