Нахождение всех отключенных подграфов в графе
У меня есть график, который содержит неизвестное количество отключенных подграфов. Какой хороший алгоритм (или библиотека Java), чтобы найти их все?
8 ответов
Я думаю, что то, что вы ищете, обычно называется Flood Fill. От вас зависит, пройдете ли вы по графику через BFS или DFS.
В основном вы берете немаркированный (AKA uncoloured) узел и назначаете ему новый ярлык. Вы назначаете одну и ту же метку всем узлам, смежным с этим, и так далее всем узлам, которые доступны из этого узла.
Когда больше недоступных узлов нельзя пометить, вы начинаете заново, выбирая другой немеченый узел. Обратите внимание, что тот факт, что этот новый узел является немаркированным, подразумевает, что он недоступен из нашего более раннего узла и, таким образом, находится в другом отключенном компоненте.
Когда больше нет немеченых узлов, количество различных меток, которые вы должны были использовать, равно количеству компонентов графа. Метка для каждого узла говорит вам, какой узел является частью какого компонента.
Не реализация 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
Больше информации здесь.
Есть много аспектов этого вопроса, которые не полностью объяснены, поэтому я собираюсь дать несколько исчерпывающий ответ. Несмотря на мою склонность публиковать текстовые стены.:/ Обратите внимание, что я предполагаю, что это домашнее задание или вопрос самообразования, поэтому я не собираюсь давать прямой ответ.
Два основных алгоритма обнаружения связности графа - это поиск в глубину и поиск в ширину. Это действительно две отправные точки, которые вы хотите посмотреть. Оба приведут вас к решению, но по-разному, и трудно поспорить, что "лучше", не рассматривая некоторые довольно глубокие аспекты проблемы. Но давайте двигаться дальше.
Как я упоминал ранее, вы пропустили некоторые важные детали, и я коснусь некоторых возможностей здесь.
Ваш график направлен или ненаправлен? и рассматриваете ли вы связность в "сильном" смысле (в этом случае см. ответ Огги) или связность в "слабом" смысле? В зависимости от вашего ответа, вам придется немного приблизиться к вашему алгоритму. Обратите внимание, что для неориентированного графа слабая и сильная связность эквивалентны, так что это хорошо. Но вы должны будете помнить структуру графа независимо от того, реализуете ли он алгоритм или находите его.
Кроме того, возникает вопрос о том, что вы подразумеваете под "нахождением подграфов" (перефразируя). Обычно связность графа является проблемой решения - просто "есть один связный граф" или "есть два или более подграфа (иначе он отключен)". Наличие алгоритма для этого требует наименьшего количества книг, что приятно.:) Следующим шагом будет подсчет графиков, буквально их количество, и эта книжная работа тоже не так уж плоха. Предположительно, вам может потребоваться список узлов в каждом подграфе. Наконец, вы можете буквально скопировать подграфы, ребра и все (поэтому возвращаемый тип будет списком графов, я полагаю, с подразумеваемым инвариантом, что каждый граф связан). Ни один из этих разных типов результатов не потребует другого алгоритма, но , безусловно, потребует другого подхода к работе с книгами.
Все это может показаться нелепым излишним из-за довольно простого вопроса, но я подумал, что просто выделю все аспекты, связанные даже с таким простым графическим вопросом. Обратите внимание на то, что ничего подобного не затрагивает время выполнения или использование памяти!:) - Агор
JGraphT - это хорошая графическая библиотека с открытым исходным кодом, лицензированная по лицензии LGPL. Я использовал его в прошлом для работы с графиками и определения циклов внутри графиков. Он также довольно прост в использовании, и вы можете использовать JGraph для визуализации графиков.
Вероятно, мне следовало бы найти стандартный алгоритм ( в Википедии есть несколько предложений), но я придумал его самостоятельно, и он хорошо работал для моих целей. Моей реализации на C# требуется пара секунд, чтобы обработать граф с 40 000 узлов и 44 000 ребер, чтобы найти 160 подграфов и 20 000 несвязанных узлов. Я использовал HashSet для хранения каждой группы подграфов, поэтому членство в группе тестирования составляет примерно O(1), а общий алгоритм становится O(E*C), где E — количество ребер, а C — количество связанных компонентов в графе. . В Википедии упоминается алгоритм O(N), линейный по количеству узлов, поэтому я уверен, что мой алгоритм не максимально эффективен, но для моего приложения он был достаточно быстрым. (Редактировать: я также умалчиваю о стоимости слияния групп, поэтому не придавайте слишком большого значения моему анализу сложности.)
Логика:
For each edge A->B
If A is in a group and B is not, add B to group A
If A is not in a group and B is, add A to group B
If A and B are in different groups, merge the groups
If neither A or B is in a group, create new group containing A and B
Псевдокод:
graph = {nodes, edges}
groups = {}
foreach edge A->B in graph.edges:
groupA = findgroup(A)
groupB = findgroup(B)
if (groupA && !groupB)
groupA.add(B)
elif (!groupA && groupB)
groupB.add(A)
elif (groupA && groupB)
if (groupA != groupB)
groupA.union(groupB)
groups.delete(groupB)
else
groups.add({A,B})
findgroup(node):
for group in groups:
if group.contains(node):
return group
return null
Обратите внимание, что это не захватит никакие узлы, которые не участвуют в ребрах. Для моих конкретных целей это было хорошо. Если вы хотите получить все группы с одним узлом, вы можете выполнить последний проход:
foreach node in graph.nodes:
group = findgroup(node)
if !group:
groups.add({node})
Как насчет поиска в ширину, чтобы найти все подключенные узлы? Когда у вас есть список подключенных узлов, вы вычитаете этот список из списка всех узлов. Вы получите список отключенных узлов
Я предполагаю, что вы хотите найти все (сильно) связанные компоненты? Для этого вы можете использовать алгоритм Тарьяна (вариант DFS)