Найти несколько колец в диаграмме

Question

У меня возникла проблема, которую я, похоже, не могу решить, У меня есть digram узлов, этот узел формирует форму в соответствии с изображением.

Диаграмма содержит 15 узлов. Диаграмма также имеет 2 кольца. Мне нужно найти решение, на котором я могу найти элементы, которые образуют кольцо на диаграмме. Итак, из этой диаграммы я бы получил 2 списка элементов {A, Z, B, O, F}, {T, H, R, M, P, F}, каждый узел будет считаться кольцом, игнорируя остальные элементы, которые не входят в кольца {Q, N, C, V}. Имейте в виду, что для моих целей диаграмма всегда будет содержать несколько колец.

У меня есть список узлов, каждый узел имеет свойство ConnectedNodes, которое представляет собой список, содержащий связанные с ним узлы, не упорядоченные или что-то еще. Узлы-соединители {F, P} соединены с тремя узлами. Они являются общими, они соединяются с кольцевыми узлами и не кольцевыми узлами, а остальные узлы соединены жестко с двумя узлами. Может кто-то, пожалуйста, дайте мне идеи или, возможно, предложите алограммы, которые могут быть применены к этой проблеме.

Обновление: - Это допустимо, если вы можете иметь более одного кольцевого элемента в качестве узла соединителя {V, P, D}. Для обновленной диаграммы теперь у меня есть 4 кольца вместо 2 и 4 узлов.

Answer 1

Непонятно, что именно вы хотели бы сделать. Насколько я понимаю, вы хотите один из них:

1. Вы хотите найти какое-либо конкретное кольцо (например: {A, Z, B, O, F}).

Вы можете сделать это с помощью DFS - просто запустить его из любой вершины v , продолжить до тех пор пока вы достигнете вершин у, которые уже посетили. Кольцо создано с вершинами, которые вы посетили с тех пор, как вы покинули u.

2. Вы хотите найти каждое кольцо на диаграмме ({A, Z, B, O, F}, {T, H, R, M, P, F} в первый тест)

Это также может быть сделано с помощью DFS - начать с любой вершины v и искать для каждого моно-вершинного-путь (путь, в котором каждая вершина встречается не более одного раза), начиная с об , Всякий раз, когда есть край (u, w) от конца пути до любой вершины внутри пути, у вас есть кольцо.

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

Пессимистическая временная сложность этого алгоритма O (n!). Но, пожалуйста, обратите внимание, что в общем случае невозможно найти лучшее решение, потому что число колец в общем случае равно n! (например, на полном графике).

3. Вы хотите найти каждую вершину на диаграмме, которая является частью некоторого кольца ({A, Z, B, O, F, T, H, R, M, P } в первом тестовом случае)

Вы можете сделать это, посмотрев каждый мост в графе. https://en.wikipedia.org/wiki/Bridge_(graph_theory)

Вершина у не является частью любого кольца, если и только если каждое ребро, которое происходит от у является мостом.

Вы можете сделать это в линейном времени.