7 ответов:
Я думаю, что то, что вы ищете, обычно называется заливкой потоком. От вас зависит, будете ли вы пересекать график через BFS или DFS.
В основном вы берете немеченый (он же неокрашенный) узел и присваиваете ему новую метку. Вы назначаете одну и ту же метку всем узлам, расположенным рядом с этим узлом, и так далее для всех узлов, доступных из этого узла.
Когда больше недоступные узлы не могут быть помечены, вы начинаете с выбора другого немаркированного узла. Заметьте, что факт то, что этот новый узел не помечен, означает, что он недоступен из нашего предыдущего узла и, таким образом, находится в другом отключенном компоненте.
Когда больше нет немеченых узлов, число различных меток, которые вы должны были использовать, равно числу компонентов графа. Метка для каждого узла указывает, какой узел является частью какого компонента.
Не реализация 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Подробнеездесь .
Есть много аспектов этого вопроса, которые не полностью объяснены, поэтому я собираюсь дать несколько исчерпывающий ответ. Несмотря на мою склонность размещать стены текста. Заметьте также, что я предполагаю, что это вопрос домашнего задания или вопрос самообразования, поэтому я не собираюсь давать прямой ответ.
Два основных алгоритма обнаружения связности графа - этоПервый поиск по глубине ипервый поиск по ширине . Это действительно 2 отправные точки, которые вы хочу посмотреть. Оба приведут вас к решению, но по-разному, и трудно спорить, что "лучше", не рассматривая некоторые довольно глубокие аспекты проблемы. Но давайте двигаться дальше. Как я уже упоминал ранее, вы упустили некоторые важные детали, и я коснусь здесь некоторых возможностей.Является ли ваш граф направленным или неориентированным? и рассматриваете ли вы связность в "сильном" смысле (в этом случае смотрите ответ Огги) или связность в "слабом" смысле? В зависимости от вашего ответа, вам придется подойти к вашему алгоритму немного по-другому. Обратите внимание, что для неориентированного графа слабая и сильная связность эквивалентны, так что это хорошо. Но вам все равно придется иметь в виду структуру графа, реализуя или находя алгоритм.
Кроме того, возникает вопрос о том, что вы подразумеваете под "нахождением подграфов" (парафраза). Обычно связность графа является проблемой решения - просто "есть один связанный граф " или "есть два или более подграфов (он же отключен)". Наличие алгоритма для этого требует наименьшего количества книжной работы, что приятно. :) Следующим шагом вверх будет подсчет графиков, буквально их количество, и эта книжная работа тоже не так уж плоха. В предпоследнем случае вам может понадобиться список узлов в каждом подграфе. Наконец, вы можете буквально скопировать подграфы, ребра и все (таким образом, возвращаемый тип будет списком графов, я полагаю, с подразумеваемым инвариантно, что каждый граф связан). Ни один из этих различных типов результатов не потребует другого алгоритма, но , безусловно, потребует другого подхода к книжной работе.Все это может показаться смешным количеством излишеств для того, что является довольно базовым вопросом, но я подумал, что просто выделю все аспекты, связанные даже с таким простым графическим вопросом. В качестве своего рода клиффхангера, обратите внимание, что ничто из этого даже пока не касается времени выполнения или использования памяти! :) - Агор
JGraphT - это хорошая графическая библиотека с открытым исходным кодом, лицензированная по лицензии LGPL. Я использовал его в прошлом, чтобы иметь дело с графиками и обнаруживать циклы внутри графиков. Он также довольно прост в использовании, и вы можете использовать JGraph для визуализации графиков.
Как насчет широтного первого поиска, чтобы найти все связанные узлы? Получив список подключенных узлов, вы вычтете этот список из списка всех узлов. В итоге вы получаете список отключенных узлов
Comments