Algorithm for a graph problem
algorithm, c#, graph
Solution
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.
- If graph has no nodes, it is acyclic.
- If graph has no leaf, it is cyclic.
- 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.
Problem
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 --> ```