MySQL пересекает данные графа и получает нециклический путь - PullRequest
Новая
       22

MySQL пересекает данные графа и получает нециклический путь

2 голосов
/ 16 ноября 2011

Этот вопрос мне сложно решить, в основном у меня есть данные в таблице, выглядящей так: 

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
...

Вы можете увидеть, насколько сложной становится структура, если попытаетесь установить, у какого родителя есть какие дети: 

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

Боюсь, что одному MySQL не удастся эффективно найти путь, но, учитывая, что я пишу это на PHP, возможно, я мог бы написать какой-то способ для него, возможно, сначала запросить 800 строк кода, а затем запрограммировать эффективный способ анализа данных. .

Идея состоит в том, что эта функция, которую я пытаюсь создать, назовем ее makePath (), принимает два параметра и возвращает массив с подмассивами, а идентификатор ссылается на строку в таблице данных.

Например, makePath (2,8) вернет: 

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

Поскольку это единственные пути, идущие от 2 до 8 без возврата назад (т. Е. Идущие [2,5,2,6,8] и бесконечные другие комбинации путей.)

Я застрял на том, как начать все это, надеюсь, кто-то более яркий, чем я, на графике и теории циклов может объяснить, как я должен начать свой код - спасибо за ваше время!

1 Ответ

0 голосов
/ 17 ноября 2011

Вы должны быть в состоянии сделать это с помощью поиска в глубину в структуре ориентированного графа. Основная схема будет выглядеть так:

  1. Создать график. Вам потребуется как минимум список дочерних элементов и флаг visiting на узел.
  2. Вызовите визит с начального узла. Для функции посещения вам необходимо знать узел назначения, иметь ссылку на массив результатов и отслеживать узлы, посещенные по текущему пути в стеке.
  3. Если текущий узел является последним узлом, добавьте пройденный путь (проходя через стек) в массив результатов.
  4. Если узел посещается, вернитесь.
  5. Если узел не посещается, то
    1. пометить узел как посещенный
    2. вызов визит (рекурсия) с каждым ребенком
    3. снять отметку с узла как посещенного

Если вам нужна помощь по любому из шагов, пожалуйста, спросите.

...