Глубина первого поиска в MySQL - программирование

Я пытаюсь написать MySQL PROCEDURE, который берет ребро e и набор ребер eset в качестве входов и выводит логическое значение iscyclic, чтобы определить, приводит ли дополнительное ребро к циклическому графу. Будет ли более простой способ сделать это иначе, чем создать таблицу всех вершин со столбцом для чего-то вроде "visit count", а затем проверить, будет ли какая-либо вершина посещать более одного раза при запуске через набор ребер?

Ответ 1

Как показывают комментарии Биллиски, вам нужно следить за отдельными деревьями вашего леса, т.е. подключенными наборами.

Простейшая реализация непересекающейся структуры данных набора будет состоять из одной временной таблицы, которая отображает ID каждой вершины в ID родителя. Вы можете следовать этим родительским ссылкам от одной вершины к следующей, пока не закончите с корнем этого дерева, которое является вершиной, указывающей на себя. Этот корень служит уникальным представителем, который идентифицирует весь подключенный набор.

Итак, чтобы проверить, связаны ли два набора, вы вычисляете их корни и просто сравниваете их.

Изначально каждая вершина является ее собственным родителем.
Подключение двух узлов моделируется путем вычисления их корней и создания один из которых является родителем другого.

Существуют дополнительные инструменты, позволяющие сохранить глубину дерева ниже:

вы всегда должны сделать более глубокое дерево родителем менее глубокого, и вы можете выполнить сжатие пути, чтобы уменьшить глубину найденного узлы.

Все это может быть смоделировано и в MySQL, но поведение производительности может отличаться от реализации в памяти.

Поэтому я предлагаю отложить это до тех пор, пока вы не узнаете, что вам нужна более высокая производительность, и у вас есть некоторые данные для тестирования и сравнения различных реализаций.