Search code examples
language-agnosticgraph-theoryprojectionreachability

Best way to test for total reachability

I have a set of nodes, each of which is connected to at least one other node. I would like to know if the connections are such that each node is reachable from every other. For example:

1--2
   |
3--4

Versus:

1--2

3--4

I am convinced this kind of reachability testing can be projected in terms of an exact cover problem, however I can't seem to get my brain wrapped around how to do so. Does anyone have any pointers, documentation, web sites, etc., on how to do this? Examples would be extremely valuable.

Update: My ignorance has betrayed me, as it would seem there are far more efficient algorithms for this kind of test. If you have one, please point me to it.

Solution
    • start from any node and do a depth/breadth first traversal
    • count number of visited node (of course, dont visit any node twice!)
    • compare counted number with total number