Java Coding Test Course, Breadth-First Search

Understanding various algorithms and data structures is important in coding tests. One of them is Breadth-First Search (BFS). In this article, we will explain the basic concepts of BFS, provide example problems, and outline a step-by-step approach to solving those problems.

1. Overview of Breadth-First Search (BFS)

Breadth-First Search is an algorithm used to explore graph or tree structures, starting from the root node and visiting adjacent nodes in priority order. It is primarily implemented using a queue data structure. BFS is useful for finding the shortest path to a specific node and is suitable for problems involving shortest distances.

1.1 Characteristics of BFS

  • Searches all nodes at the same depth
  • Guarantees the shortest path
  • May use a lot of memory

1.2 Time Complexity of BFS

The time complexity of BFS is O(V + E), where V is the number of nodes and E is the number of edges. This is because each node and edge is visited once.

2. Example Problem

Problem Description

This problem involves calculating the shortest distances from a starting node in a given graph. The graph is provided in the form of an adjacency list, and you are required to write a function that returns the shortest distance to all nodes reachable from the starting node.

Input

  • n (1 ≤ n ≤ 1000): Number of nodes in the graph
  • edges: An array of edge lists, where each edge is of the form [a, b]
  • start: The starting node (an integer from 1 to n)

Output

Returns an array containing the shortest distances from the starting node to each node. If a node is unreachable, denote it by -1.

2.1 Example

    Input: 
    n = 5
    edges = [[1, 2], [1, 3], [2, 4], [3, 5]]
    start = 1

    Output: 
    [0, 1, 1, 2, -1]

3. Problem Solving Process

To solve this problem, we will proceed through the following steps.

3.1 Convert Input Data to Graph Form

First, we will convert the edge list into an adjacency list representation of the graph. This allows us to easily find adjacent nodes for each node.

3.2 Implement BFS Algorithm

We will perform BFS starting from the starting node using a queue. The current node is added to the queue, allowing us to explore adjacent nodes. We will record the shortest distance for visited nodes in an array for later use.

3.2.1 Progress of BFS Exploration

  1. Add the starting node to the queue and set the initial value (0) in the distance array.
  2. Poll a node from the queue and check all adjacent nodes to that node.
  3. If an adjacent node has not been visited, update the distance and add it to the queue.
  4. Repeat this process until all nodes have been visited.

3.3 Generate Final Results

After exploring all nodes, we return the distance array to display the shortest paths. Nodes that are unreachable are indicated by -1.

4. Java Code Example


import java.util.*;

public class BFSDistance {
    public static int[] bfsDistance(int n, int[][] edges, int start) {
        List> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // Create the graph adjacency list
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]); // Undirected graph
        }

        int[] distances = new int[n + 1];
        Arrays.fill(distances, -1); // Set initial distance to -1
        distances[start] = 0; // Distance to the starting point is 0
        
        Queue queue = new LinkedList<>();
        queue.add(start);
        
        while (!queue.isEmpty()) {
            int currentNode = queue.poll();
            for (int neighbor : graph.get(currentNode)) {
                if (distances[neighbor] == -1) { // If not visited
                    distances[neighbor] = distances[currentNode] + 1;
                    queue.add(neighbor);
                }
            }
        }
        
        return Arrays.copyOfRange(distances, 1, distances.length); // Return from 1 to n
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{1, 2}, {1, 3}, {2, 4}, {3, 5}};
        int start = 1;

        int[] result = bfsDistance(n, edges, start);
        System.out.println(Arrays.toString(result)); // [0, 1, 1, 2, -1]
    }
}

5. Conclusion

In this lecture, we demonstrated the concept and application of Breadth-First Search (BFS). BFS is a highly effective algorithm for finding the shortest path and a powerful tool for exploring graphs and trees. We encourage you to practice and apply this technique in coding tests. In the next lecture, we will cover Depth-First Search (DFS)!

6. Additional Practice Problems

We provide additional problems for practicing Breadth-First Search. Try solving the problems below.

Problem: Finding Shortest Path

Given an unweighted graph, determine the shortest paths from the starting node to all other nodes. Additionally, learn how to use Dijkstra’s algorithm to find the shortest path in weighted graphs.

Reference Materials