Нахождение всех несвязных подграфов в графе

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

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

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

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

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

import networkx as nx
g = nx.Graph()
# add nodes/edges to graph

d = list(nx.connected_components(g)) 
# d contains disconnected subgraphs
# d[0] contains the biggest subgraph

Дополнительная информация здесь.

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

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

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

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

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

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

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

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

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

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