Удаление циклов из графа в SQL

Рейтинг: 0Ответов: 0Опубликовано: 22.08.2023

Предположим, у вас есть таблица рёбер со столбцами A и B, в которых указаны номера вершин, соединенных ребром. Как выбрать из неё ребра так, чтобы в выборке не оказалось ни одного ребра, создающего цикл? Пример:

| A | B |
| 1 | 2 |
| 1 | 3 |
| 2 | 3 |
| 3 | 4 |
| 4 | 1 |

Результат запроса:

| A | B |
| 1 | 2 |
| 1 | 3 |
| 4 | 1 |

Или

| A | B |
| 1 | 2 |
| 2 | 3 |
| 4 | 1 |

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

Небольшая визуализация визуализация

Ответы

Ответов пока нет.