Нахождение всех отключенных подграфов в графе

Question

У меня есть график, который содержит неизвестное количество отключенных подграфов. Какой хороший алгоритм (или библиотека Java), чтобы найти их все?

Answer 1

Я думаю, что то, что вы ищете, обычно называется Flood Fill . От вас зависит, пройдете ли вы по графику через BFS или DFS.

В основном вы берете немаркированный (AKA uncoloured) узел и назначаете ему новый ярлык. Вы назначаете одну и ту же метку всем узлам, смежным с этим, и так далее всем узлам, которые доступны из этого узла.

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

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

Answer 2

Не реализация Java, но, возможно, это будет кому-то полезно, вот как это сделать в Python:

import networkx as nx
g = nx.Graph()
# add nodes/edges to graph
d = list(nx.connected_component_subgraphs(g))
# d contains disconnected subgraphs
# d[0] contains the biggest subgraph

Подробнее здесь .

Answer 3

Есть много аспектов этого вопроса, которые не полностью объяснены, поэтому я собираюсь дать несколько исчерпывающий ответ. Несмотря на мою склонность публиковать текстовые стены. : / Обратите внимание, что я предполагаю, что это домашнее задание или вопрос самообразования, поэтому я не собираюсь давать прямой ответ.

Два основных алгоритма обнаружения связности графа: Поиск в глубину и Поиск в ширину . Это действительно две отправные точки, которые вы хотите посмотреть. Оба приведут вас к решению, но по-разному, и трудно поспорить, что «лучше», не рассматривая некоторые довольно глубокие аспекты проблемы. Но давайте двигаться дальше.

Как я упоминал ранее, вы пропустили некоторые важные детали, и я коснусь некоторых возможностей здесь.

Ваш график направлен или ненаправлен? и рассматриваете ли вы связность в «сильном» смысле (в этом случае см. ответ Огги) или связность в «слабом» смысле? В зависимости от вашего ответа, вам придется немного приблизиться к вашему алгоритму. Обратите внимание, что для неориентированного графа слабая и сильная связность эквивалентны, так что это хорошо. Но вы должны будете помнить структуру графа независимо от того, реализуете ли он алгоритм или находите его.

Кроме того, возникает вопрос о том, что вы подразумеваете под «нахождением подграфов» (перефразируя). Обычно связность графа является проблемой решения - просто «есть один связный граф» или «есть два или более подграфа (иначе он отключен)». Наличие алгоритма для этого требует наименьшего количества книг, что приятно. :) Следующим шагом будет граф графов, буквально их число, и эта книжная работа также не так уж и плоха. Предположительно, вам может потребоваться список узлов в каждом подграфе. Наконец, вы можете буквально скопировать подграфы, ребра и все (поэтому возвращаемый тип будет списком графов, я полагаю, с подразумеваемым инвариантом, что каждый граф связан). Ни один из этих разных типов результатов не потребует другого алгоритма, но , безусловно, потребует другого подхода к работе с книгами.

Все это может показаться нелепым излишним из-за довольно простого вопроса, но я подумал, что просто выделю все аспекты, связанные даже с таким простым графическим вопросом. Обратите внимание на то, как ничего из этого не затрагивает время выполнения или использование памяти! :) - Агор

Answer 4

JGraphT - это симпатичная графическая библиотека с открытым исходным кодом, лицензированная по лицензии LGPL. Я использовал его в прошлом для работы с графиками и выявления циклов внутри графиков. Он также довольно прост в использовании, и вы можете использовать JGraph для визуализации графиков.

Answer 5

Я предполагаю, что вы хотите найти все (сильно) связанные компоненты? Для этого вы можете использовать алгоритм Тарьяна (вариант DFS)

Answer 6

Я столкнулся с аналогичной проблемой, когда хотел получить все слабо связанные подграфы ориентированного графа. Я писал об этом здесь . Я использовал JUNG API и сравнил два подхода. Мой первый подход можно использовать в качестве шаблона для решения вашей проблемы.

Answer 7

Как насчет поиска в ширину для поиска всех подключенных узлов? Получив список подключенных узлов, вычтите этот список из списка всех узлов. Вы получите список отключенных узлов