I certainly would not use XML for that. XML is useful for things like communications between different systems or storing some configuration into a file on disk, it is really unpractical as an internal data structure.
You probably want to build a graph, which could be possibly a hash of arrays, in which the array contains all possible successor nodes to the hash key node. Or you could build a list of possible complete paths from a given node.
is not completely sufficient to figure out the paths that are allowed. Suppose that I am on node B: does that mean that we can go to node C irrespective of what happened before (in which case paths 1 and 3 seem to be redundant), or that I am allowed to go to C only if I was on A before getting to B (so that I can't go anywhere if I am on node B but not coming from A)? Determining the best modeling for your application behavior depends on an answer to such questions.