BFS

Only read the BFS part if in hurry.

• BFS explores the graph level by level, starting from the source node and progressively moving to nodes at increasing distances.
• It processes all the neighbors of the current node before moving on to the next level of nodes. In other words, it visits all the nodes at a distance of 1 from the source, then all the nodes at a distance of 2, and so on.
• This level-by-level exploration ensures that BFS reaches each node in the shortest possible number of steps (edges) from the source.
• The queue follows the FIFO order, meaning that the nodes are processed in the order they are discovered.
• This FIFO order guarantees that the nodes closer to the source are processed before the nodes farther away. Algorithm: r m* w a* (remove, mark*, work, add*)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
 
public class Main {
    static class Edge {
        int src;
        int nbr;
 
        Edge(int src, int nbr) {
            this.nbr = nbr;
            this.src = src;
        }
    }
 
    static class Pair {
        int v;
        String psf;
 
        Pair(int v, String psf) {
            this.v = v;
            this.psf = psf;
        }
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int vtces = Integer.parseInt(br.readLine());
        ArrayList<Edge>[] graph = createGraph(br, vtces);
 
        int src = Integer.parseInt(br.readLine());
        bfs(graph, src);
    }
 
    private static ArrayList<Edge>[] createGraph(BufferedReader br, int vtces) throws Exception {
        ArrayList<Edge>[] graph = new ArrayList[vtces];
        for (int i = 0; i < vtces; i++) {
            graph[i] = new ArrayList<>();
        }
 
        int edges = Integer.parseInt(br.readLine());
        for (int i = 0; i < edges; i++) {
            String[] parts = br.readLine().split(" ");
            int v1 = Integer.parseInt(parts[0]);
            int v2 = Integer.parseInt(parts[1]);
            graph[v1].add(new Edge(v1, v2));
            graph[v2].add(new Edge(v2, v1));
        }
 
        return graph;
    }
 
    private static void bfs(ArrayList<Edge>[] graph, int src) {
        ArrayDeque<Pair> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[graph.length];
        queue.add(new Pair(src, src + ""));
 
        while (queue.size() > 0) {
            Pair rem = queue.removeFirst();
            if (visited[rem.v]) {
                continue;
            }
            visited[rem.v] = true;
            System.out.println(rem.v + "@" + rem.psf);
 
            for (Edge edge : graph[rem.v]) {
                if (!visited[edge.nbr]) {
                    queue.add(new Pair(edge.nbr, rem.psf + edge.nbr));
                }
            }
        }
    }
}