Kotlin coding test course, DFS and BFS programs

Introduction

Learning various algorithms while preparing for coding tests is very important. Among them,
DFS (Depth-First Search) and BFS (Breadth-First Search) algorithms are effective for solving many problems.
In this article, we will understand the concepts of DFS and BFS and learn how to prepare for actual coding tests through examples using these algorithms.

Concepts of DFS and BFS

DFS and BFS are algorithms for graph traversal, and the approaches of the two algorithms are different from each other.

DFS (Depth-First Search)

DFS is a depth-first search that explores as deeply as possible from one node before returning to the previous node
to explore other nodes when no further exploration is possible. It is generally implemented using a stack structure.

BFS (Breadth-First Search)

BFS is a breadth-first search that explores all neighboring nodes of one node before moving on to explore nodes at the next depth.
It is typically implemented using a queue structure.

Problem Description

Here is an example problem that can be solved using DFS and BFS.
Problem: Determine whether two nodes in a given graph are connected.

Input

• Number of nodes N (1 ≤ N ≤ 1000)
• Number of edges E (1 ≤ E ≤ 10000)
• Pairs of two nodes representing each edge (A, B)
• Query Q (number of queries to check if two nodes are connected)
• For each query, two nodes X, Y to check for connectivity

Output

For each query, print “YES” if X and Y are connected, otherwise print “NO”.

Problem Solving Process

1. Graph Representation

The graph can be represented in the form of an adjacency list. Connected nodes are added to the list to determine the existence or lack thereof.

2. Implementing DFS

We will implement DFS through recursive calls. A boolean array is used to check visited nodes, and we will explore
starting from the given node until we reach the target node.

fun dfs(graph: List>, visited: BooleanArray, current: Int, target: Int): Boolean {
    if (current == target) return true
    visited[current] = true

    for (neighbor in graph[current]) {
        if (!visited[neighbor]) {
            if (dfs(graph, visited, neighbor, target)) return true
        }
    }
    return false
}
    

3. Implementing BFS

BFS is implemented using a queue. We add the starting node to the queue, and for each node, we take it out of the queue one by one
to visit all neighboring nodes and check if we reach the target node.

fun bfs(graph: List>, start: Int, target: Int): Boolean {
    val queue: Queue = LinkedList()
    val visited = BooleanArray(graph.size)
    
    queue.offer(start)
    visited[start] = true

    while (queue.isNotEmpty()) {
        val current = queue.poll()
        if (current == target) return true

        for (neighbor in graph[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true
                queue.offer(neighbor)
            }
        }
    }
    return false
}
    

4. Complete Code

Now we will write the complete code that takes the input of the graph and determines connectivity using DFS and BFS.

import java.util.*

fun main() {
    val scanner = Scanner(System.`in`)
    val n = scanner.nextInt()
    val e = scanner.nextInt()

    val graph = List(n) { mutableListOf() }

    for (i in 0 until e) {
        val a = scanner.nextInt() - 1
        val b = scanner.nextInt() - 1
        graph[a].add(b)
        graph[b].add(a)  // Undirected graph
    }

    val q = scanner.nextInt()
    for (i in 0 until q) {
        val x = scanner.nextInt() - 1
        val y = scanner.nextInt() - 1

        val visitedDFS = BooleanArray(n)
        val visitedBFS = BooleanArray(n)

        // DFS Check
        val isConnectedDFS = dfs(graph, visitedDFS, x, y)
        // BFS Check
        val isConnectedBFS = bfs(graph, x, y)

        println("Connected in DFS: ${if (isConnectedDFS) "YES" else "NO"}")
        println("Connected in BFS: ${if (isConnectedBFS) "YES" else "NO"}")
    }
}
    

Conclusion

DFS and BFS each have their strengths and weaknesses, and it is important to choose the right algorithm depending on the specific problem.
I hope this tutorial helped you understand the two algorithms and will aid you in preparing for actual coding tests.