Determining connectivity is essentially what you are doing in the example. You can't know that A has no direct path to D, E, F without checking somehow. Once this is done, finding a valid path is a fairly simple matter. Such a graph could be expanded upon to include nodes with various data and priorities. This could influence the actual path taken without needing to change the pathfinding algorithm. More weight could be given to a well traveled path or animals could attempt to avoid a path for some reason.

A navgraph created at worldgen should take away a lot of strain that pathfinding can put on the system.