import org.openjdk.jmh.annotations.*;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.concurrent.TimeUnit;

@State(Scope.Thread)
@Fork(1)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class Graph {
    private int[][] g;
    private static final int SIZE = 10;

    @Setup
    public void setup() {
        g = new int[][] {
                {0, 1, 0, 0, 0, 0, 0, 1, 1, 0},
                {1, 0, 1, 1, 0, 0, 1, 0, 1, 0},
                {0, 1, 0, 0, 0, 0, 0, 0, 0, 1},
                {0, 1, 0, 0, 1, 0, 1, 0, 0, 0},
                {0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
                {0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
                {1, 0, 0, 0, 0, 0, 1, 0, 1, 0},
                {1, 1, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0, 0, 1, 0, 0, 0}
        };


    }

    private class DfsRunner {
        boolean[] visited;

        public DfsRunner() {
            visited = new boolean[SIZE];
        }

        public void run(int v) {
            visited[v] = true;
            for (int u = 0; u < SIZE; u++) {
                if (g[v][u] == 1 && !visited[u]) {
                    run(u);
                }
            }
        }
    }

    @GenerateMicroBenchmark
    public boolean dfs() {
        DfsRunner dfsRunner = new DfsRunner();
        dfsRunner.run(0);
        for (int i = 0; i < SIZE; i++) {
            if (!dfsRunner.visited[i]) return false;
        }
        return true;
    }

    @GenerateMicroBenchmark
    public boolean bfs() {
        boolean[] visited = new boolean[SIZE];

        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(0);

        while (!queue.isEmpty()) {
            int v = queue.poll();
            visited[v] = true;
            for (int u = 0; u < SIZE; u++) {
                if (g[v][u] == 1 && !visited[u]) {
                    queue.add(u);
                }
            }
        }

        for (int i = 0; i < SIZE; i++) {
            if (!visited[i]) return false;
        }
        return true;
    }
}


-----------------------------------------------------------------------------
Benchmark           Mode Thr     Count  Sec         Mean   Mean error    Units
c.d.b.Graph.bfs     avgt   1        10    1      727.719        6.730    ns/op
c.d.b.Graph.dfs     avgt   1        10    1      339.698       14.303    ns/op