Java Coding Test Course, DFS and BFS Programs

Developing algorithm problem-solving skills is very important for software developers. Especially when preparing for employment, it is necessary to understand and utilize various algorithms and data structures. In this course, we will understand the concepts of Depth First Search (DFS) and Breadth First Search (BFS), and we will solve actual algorithm problems. In this process, we will examine problem definition, approaches, Java code implementation, and time complexity together.

Problem Definition

The given problem is as follows:

Problem: Given an undirected graph consisting of vertices from 0 to N, write a program to check if it is possible to reach all vertices starting from a specific starting vertex. Let’s solve this problem using two methods: DFS and BFS.

Problem Approach

Graph search algorithms have two main methods: Depth First Search and Breadth First Search. These two methods have different characteristics and applications. Therefore, we will prepare implementations of both methods to solve the problem.

1. DFS (Depth First Search)

DFS explores by going deep first and returns when there are no more vertices to visit. This method can easily be implemented using a stack or through recursion.

DFS Implementation

Here is the Java code that explores the graph using DFS:

import java.util.*;

public class Graph {
    private int vertices;
    private LinkedList[] adjacencyList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int source, int destination) {
        adjacencyList[source].add(destination);
        adjacencyList[destination].add(source); // Undirected graph
    }

    public void dfs(int start) {
        boolean[] visited = new boolean[vertices];
        dfsUtil(start, visited);
    }

    private void dfsUtil(int vertex, boolean[] visited) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        for (Integer neighbor : adjacencyList[vertex]) {
            if (!visited[neighbor]) {
                dfsUtil(neighbor, visited);
            }
        }
    }
}

2. BFS (Breadth First Search)

BFS explores by prioritizing width, first exploring the neighbors of the current vertex and then the neighbors of those neighbors. It is primarily implemented using a queue.

BFS Implementation

Here is the Java code that explores the graph using BFS:

import java.util.*;

public class Graph {
    private int vertices;
    private LinkedList<Integer>[] adjacencyList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int source, int destination) {
        adjacencyList[source].add(destination);
        adjacencyList[destination].add(source); // Undirected graph
    }

    public void bfs(int start) {
        boolean[] visited = new boolean[vertices];
        Queue<Integer> queue = new LinkedList<>();

        visited[start] = true;
        queue.add(start);

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");

            for (Integer neighbor : adjacencyList[vertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
}

Code Execution Example

Now let’s run an example of exploring a graph using DFS and BFS. The code below creates a graph and performs a traversal using both methods:

public class GraphTraversalExample {
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);

        System.out.println("DFS Traversal:");
        graph.dfs(0);

        System.out.println("\nBFS Traversal:");
        graph.bfs(0);
    }
}

Time Complexity Analysis

The time complexities of DFS and BFS are as follows:

• DFS: O(V + E) where V is the number of vertices and E is the number of edges.
• BFS: O(V + E) as it visits each vertex and edge in the graph once.

Conclusion

DFS and BFS are fundamental algorithms for graph traversal. By understanding and utilizing these algorithms, various problems can be solved. If you have learned the basic concepts and implementation methods of graphs through this course, you are ready to tackle more complex problems. Subsequently, it is advisable to connect theory with practice by solving various problems often encountered in actual coding tests.

In the future, I hope you will learn more diverse data structures and algorithms to elevate your programming skills to the next level.