Как эффективно найти связанные компоненты в графе без матрицы смежности?

Question

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

Я знаю, что мог бы просто рассчитать всю матрицу смежности и использовать поиск в глубину, чтобы найти все компоненты.Но это было бы не очень эффективно, так как мне нужно было бы проверить каждую пару вершин.

В настоящее время я делаю следующую процедуру:

1. Выберите любую неназначенную вершину, котораятеперь является его собственным компонентом
2. Найдите всех соседей этой вершины и добавьте их к компоненту
3. Найдите всех соседей только что добавленных вершин (среди тех вершин, которые еще не назначены ни одному компоненту) и добавьтеони тоже
4. Повторяйте предыдущий шаг, пока не будут найдены новые соседи
5. Компонент завершен, повторите с первого шага, чтобы найти другие компоненты, пока все вершины не будут назначены

Это псевдокод:

connected_components(vertices):
  // vertices belonging to the current component and whose neighbors have not yet been added
  vertices_to_check= [vertices.pop()]
  // vertices belonging to the current component
  current_component = []
  components = []
  while (vertices.notEmpty() or vertices_to_check.notEmpty()):
    if (vertices_to_check.isEmpty()): // All vertices in the current component have been found
      components.add(current_component)
      current_component = []
      vertices_to_check= [vertices.pop()]
    next_vertex = vertices_to_check.pop()
    current_component.add(next_vertex)
    for vertex in vertices: // Find all neighbors of next_vertex
      if (vertices_adjacent(vertex, next_vertex)):
        vertices.remove(vertex)
        vertices_to_check.add(vertex)
  components.add(current_component)
  return components

Я понимаю, что этот метод быстрее, чем вычисление матрицы смежности в большинстве случаев, так как мне не нужно проверять, являются ли две вершины смежными, если этоУже известно, что они принадлежат к одному и тому же компоненту.Но есть ли способ улучшить этот алгоритм?

Answer 1

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

Теперь, если большинство вершин принадлежат одному компоненту, таких пар может быть не слишком много;но если вы не ожидаете , то большинство вершин принадлежат одному компоненту, нет особого смысла оптимизировать именно для этого случая.Итак, отбрасывая этот случай, самый лучший сценарий выглядит так:

• Оказывается, что это ровно два компонента, каждый с одинаковым количеством вершин (½ | V |каждый).Таким образом, существует ¼ | V | ² пар вершин, которые принадлежат отдельным компонентам, и вам необходимо вызвать vertices_adjacent для каждой из этих пар.
• Этидва компонента оказываются законченными, или вам чрезвычайно повезло в выборе ребер для проверки в первую очередь, так что вы можете обнаружить подключенные детали, проверив просто | V |- 2 пары.

.,,который все еще включает создание making | V | ² + | V |- 2 звонка на vertices_adjacent.Для сравнения, подход списка построения смежности составляет ½ | V | ² - ½ | V |вызовов - это больше, чем в лучшем случае, но с коэффициентом меньше 2. (И сценарий худший случай просто эквивалентен подходу со списком сборки-смежности.происходит, если ни один из компонентов не содержит более двух вершин, или если граф является ациклическим, и вы вряд ли выберете ребра для проверки в первую очередь. Большинство графов будет где-то посередине.)

Так что это, вероятно, не стоитпытаясь оптимизировать слишком близко для точного минимального количества вызовов до vertices_adjacent.

Тем не менее, ваш подход кажется мне довольно разумным;он не делает никаких вызовов на vertices_adjacent, которые явно не нужны, поэтому единственное улучшение было бы вероятностным, если бы он мог лучше угадать, какие вызовы окажутся полезными для устранения более поздних вызовов.

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