I would like to verify whether this implementation of BFS and a method, which returns a boolean whether a graph is connected runs in O(n^2) or some better time:
public static Map<Vertex, Boolean> bfs(Vertex start) { Map<Vertex, Boolean> visited = g.createVertexMap(false); Queue<Vertex> q = new LinkedList<Vertex>(); visited.put(start, true); q.offer(start); while (!q.isEmpty()) { Vertex v = q.poll(); for (Vertex neighbour : v.getOutNeighbours()) { counter++; if (!visited.get(neighbour)) { visited.put(neighbour, true); q.offer(neighbour); } } } return navstiveny; } public static boolean isConnected() { Vertex someVertex = g.getVertices().iterator().next(); Map<Vertex, Boolean> availability = bfs(someVertex); return !availability.values().contains(false); } Thanks!
