MySQL遍历图形数据并获得非循环路径

Question

This one is a hard one for me to solve, basically I have data in a table looking like this:

id  a   b
1   2   4
2   4   2
3   5   2
4   2   5
5   6   2
6   2   6
7   8   6
8   6   8
9   5   6
...

You can see how complex the structure gets if you try to establish what parent has what children:

[2->[4->[2->RECURSIVE], 5->[2->RECURSIVE], 6->[2->RECURSIVE, 8->[6->[8->RECURSIVE]]]], ...]

I fear MySQL alone can't manage to efficiently find a path, but considering I write this in PHP maybe I could write some way for it to maybe first query the 800 lines of code then program an efficient way to parse the data.

The idea is that this function that I am trying to make, let's call it makePath() takes two parameters and returns an array with sub-arrays and the id's referring to a line in the data table.

For example makePath(2,8) would return:

array(array(2,6,8), array(2,5,6,8))

Since these are the only paths going from 2 to 8 without backtracking (i.e. going [2,5,2,6,8] and infinite other combinations of paths.)

I am stuck on how to start all this, hopefully someone brighter than me on the graph and cyclic theory could explain how I should start my code -thanks for your time!

Answer 1

You should be able to do this with a depth-first search on a directed graph structure. A basic outline would look like:

1. Create the graph. You'll need at a minimum a list of children and a visiting flag per node.
2. Call visit with the initial node. For your visit function, you'll need to know the destination node, have a reference to the result array, and keep track of the nodes visited along the current path in a stack.
3. If the current node is the final node, then add the path traveled (by going through the stack) to the result array.
4. If the node is being visited, then return.
5. If the node is not being visited, then
   1. mark the node as being visited
   2. call visit(recursion) with each child
   3. unmark the node as being visited

If you need help with any of the steps, then please ask.