daring mica
Does anyome know how to work out the time complexity? I am trying to get a worst-case time complexity no worse than O(v + e), where v is the number of vertices, and e is the number of edges.
public boolean isConnectedWithChargingStations(Vertex startVertex, Vertex endVertex) {
// Sanity check
if (startVertex.getIndex() == endVertex.getIndex()) {
return true;
}
Stack<Vertex> searchStack = new Stack<Vertex>();
Set<Vertex> visited = new HashSet<>();
searchStack.push(startVertex);
while(!searchStack.isEmpty()){
Vertex vertex = searchStack.pop();
if (!visited.contains(vertex)) {
visited.add(vertex);
if (vertex == endVertex){
return true;
}
if (vertex.hasChargingStation() || vertex == startVertex){
for (Edge e : vertex.getIncidentRoads()) {
//System.out.println(e.toString());
Vertex neighbour = e.getFirstVertex();
if (!visited.contains(neighbour)) {
searchStack.push(neighbour);
}
neighbour = e.getSecondVertex();
if (!visited.contains(neighbour)) {
searchStack.push(neighbour);
}
}
}
}
}
return false;
}
ocean fog