CodinGame_2023_09_13__16_42_56__TestDFS.java

import java.util.*;

public class TestDFS {
    public static void main(String args[]) {

        Graph graph = new Graph(7);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);
        graph.addEdge(2, 6);

        List<Integer> result = graph.dfs(0);
        System.out.println(result); // Expected output: [0, 1, 3, 4, 2, 5, 6]
    }

    private static class Graph {
        private int V; // Number of nodes (vertices) in the graph
        private LinkedList<Integer>[] adjacency; // Adjacency list

        @SuppressWarnings("unchecked")
        public Graph(int v) {
            V = v;
            adjacency = new LinkedList[v];
            for (int i = 0; i < v; ++i) {
                adjacency[i] = new LinkedList<>();
            }
        }

        // Add an edge between nodes u and v
        public void addEdge(int u, int v) {
            adjacency[u].add(v);
            adjacency[v].add(u); // The graph is undirected
        }

        // Recursive function to perform DFS from a given node
        private void dfsRecursive(int n, boolean[] visited, List<Integer> result) {
            visited[n] = true;
            result.add(n);

            // Traverse all unvisited adjacent nodes
            for (Integer neighbor : adjacency[n]) {
                if (!visited[neighbor]) {
                    dfsRecursive(neighbor, visited, result);
                }
            }
        }

        // Perform Depth-First Search (DFS) from the given node and return the order of visit
        public List<Integer> dfs(int n) {
            boolean[] visited = new boolean[V]; // Array to track visited nodes
            List<Integer> result = new ArrayList<>(); // List to store the order of visit

            dfsRecursive(n, visited, result); // Call the recursive DFS function

            return result;
        }
    }
}