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

Ответ 1

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

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

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

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

Ответ 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

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

Ответ 3

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

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

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

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

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

Ответ 7

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