# Can this graph search be optimized?

I have the following which searches my graph to see if a vertex is reachable from the first vertex, which everything should be connected to. I do this to ensure there are no disconnected parts.

Unfortunately it is very slow.

Is there something I could do or store to optimize this?

I want to learn about graphs and generated cities so Im not using a real graph library.

``````private void removeDisconnectedSquares()
{
for(int i = 0; i < getNumXNodes(); ++i)
{
for(int j = 0; j < getNumYNodes(); ++j)
{
//removeDisconnectedSquare(i, j);
visitedNodes.clear();
if(!isNodeReachableFrom(getNodeAt(i, j), getNodeAt(0, 0)))
{
removeVertex(i, j);
}
}
}
}

private boolean isNodeReachableFrom(GraphNode node, GraphNode target)
{
if(node == null)
{
return false;
}

if(visitedNodes.contains(node))
{
return false;
}
else
{
}

if(node == target)
{
return true;
}

if(node.contains(target))
{
return true;
}

for(int i = 0; i < node.getSize(); ++i)
{
if(isNodeReachableFrom(node.at(i), target))
{
return true;
}
}

return false;
}
``````
-

Rather than using recursion (which is pretty slow), you can for this using a Set of all reachable nodes, and a Queue of nodes you still haven't searched. This is a basic implementation of Breadth-First Search.

``````private boolean isNodeReachableFrom(GraphNode start, GraphNode target) {

// These are GraphNodes who's connected GraphNodes we haven't looked at yet.
// Maybe the target is connected to one of these!

// These are GraphsNodes which we have proved are reachable from the given node.
// If we are ever about to add the given target to this list, we return true.
Set reachableNodes = new HashSet<GraphNode>();

// As long as there are still nodesToSearch, we could still find our target.
while (nodesToSearch.peek() != null) {
GraphNode node = nodesToSearch.remove();

// If we have already seen this node, we don't want to look at its connected
// nodes again, because we could get stuck in a cycle.

// If this is a new node, see if the target is connected.  If it is, we are
// done successfully.  Otherwise, add all of the connected nodes to our
// list of nodesToSearch.
if (isNewNode) {
for (GraphNode connectedNode : getConnectedNodes(node)) {
if (connetedNode.equals(target)) {
return true;
}
}
}
}

// There are no nodes we haven't searched, so the target is not reachable.
return false;
}
``````

Note: I made up `getConnectedNodes(node)` because your code didn't show me how to do this with the GraphNode object.

Note that this is an implementation of `isNodeReachableFrom`. However, you seem to want to figure out the list of nodes which aren't reachable from a starting node. Notice that we build up the list of all `reachableNodes` in the call above, which is probably what you really want. You could write a function to return that reachableNodes structure, which would reuse the above logic without the `target` sections. Something like this:

``````public Set<GraphNode> getReachableNodes(GraphNode start) { ... }
``````
-