Since in_array() is O(N), this makes the algorithm O(N^2).

Use keys in $completed -- like $completed[$node] = true -- and isset($completed[$node]) instead, which is O(1).

Or, remove nodes from the list of remaining nodes after they're added to the results.

This seems like an odd return value.

Instead, suppose we choose one node at random/arbitrarily and mark it completed, so we always produce an ordering on all of the items (a "best effort" ordering)?

Then we could return a list of something like this:

array(
  'node' => $node,
  'depth' => /* the minimum distance from the root to the node */,
  'cycle' => /* true if we had to force our way through a cycle before we could complete this node */
)

That should be everything you need to render the data in Harbormaster.