Algorithm for a graph problem

Question

I need to check the connectedness of directional nodes in a list. It is basically questions with 2 to 7 answers each. The answer picked dictates the next question. Since these pairs will be manually captured, I need to check each possible path for looping back (not allowed) and dead ends (all routes must stop at the END node) Any pointers?

start --> n1 --- n2 --- n3 --- n4 --- end

            \  /   \      \   /       /

             n5     \      n6------ n7

              \      \     /       /

               n8----n9---n10----n11

          DIRECTION -->

Answer 1

Use a breadth first search algorithm, keeping track of all of the nodes you have already visited. If, when searching for the next node to traverse, one of the nodes already visited is a possibility, then the graph is wrong. Additionally, if you reach a node that has no other possible node to traverse to next, and you have not reached the end, then the graph is also not connected properly.

Answer 2

Please see this question about cycles and the reachability problem.

Answer 3

This may be what you are looking for:

Testing whether a graph is acyclic

Your END node is what the leaf node is in that page's terminology.

1. If graph has no nodes, it is acyclic.
2. If graph has no leaf, it is cyclic.
3. Choose any leaf, remove leaf and all transitions to it, goto step 1.

To check that there are no dead ends: Simply make sure there is only a single leaf node before using the above algorithm.