Graph theory question

[Pezzoni]

Sorry for yet another question, but this is drivng me utterly insane. I've spent the last four hours or so attempting to discover an algorithm to decide if there is a vertex in a directed graph from which every other vertex can be reached.

The question itself is seems simple to solve - run a depth first search starting at every vertex, and if you 'find' every other vertex from any of the start points, then you're sorted. The problem is attempting to find a way to do it that works in O(V+E) time. If anyone could give me a hint or two it would be very much appreciated - any algorithms or similar I should be looking at?

Thanks very much,

[Starglider]

I can't recall a standard algorithm offhand, but here's how I'd do it. Check for source nodes (i.e. nodes with no inbound edges). If there is more than one, fail. If there is exactly one, check for strong connectivity to the rest of the graph, if yes success, if no fail. If there are no source nodes, the graph must be cyclic. Find the cycles and progressively merge them until you have an acyclic graph, then apply the above approach. Optionally do a weak connectedness check before you go looking for cycles, because it's cheap and if the graph isn't weakly connected then there's clearly no universal source.

For small graphs (<1024 nodes) it might be faster to implement a parallelised breadth first search using bitfields and propagation masks (I once implemented a reasonable Go-playing AI almost exclusively using this approach). You could do it with a big fixed stream of SSE instructions with a check for success every few instructions (unless you want constant runtime, in which you just check at the end).

[Kuroneko]

What you're asking for is a plain mathematical impossibility: an algorithm with O(V²) worst case cannot exist. The simple way to do this would be to loop something like the following, with graph adjacency matrix A:

Code: Select all

if ( I + A contains a positive row ) success;
for ( Z = A, k = 1; k < V; k++ ) {
  Z = A*(I+Z);
  if ( I+Z contains a positive row ) success;
} fail;

(You can also simply modify A to have each vertex be self-adjacent and remove the addition of the identity matrix from the conditionals.) But this is not terribly efficient; the worse case is O(V^4), or with an exponent a fraction under 4 if you're clever. If you have some reason to believe that A is diagonalizable, it can be done in O(V^3) instead. If you want to improve the general case, look up Warshall's algorithm for calculating transitive closure, which does something similar in O(V^3) worst case. You may be able to somewhat to improve its efficiency, since you're not asking for complete connectedness.