Перебирая соединенные компоненты

Я хочу перебрать каждый связанный компонент неориентированного графа, содержащего ~ 107 вершин. т.е. я хочу вызвать некоторую функцию f (Vi) для каждого вектора V1... Vk, где Vi - вектор, содержащий данные, прикрепленные к каждому узлу в i-м связанном компоненте графа.

Каковы самые быстрые алгоритмы для этого?

Мои первые мысли были:

  1. Сохраните все не посещенные вершины в куче, затем повторно извлекайте вершину из кучи, используйте DFS, чтобы найти связанный с ней компонент Vi, вызывайте f (Vi) и удаляйте все вершины в компоненте из кучи.
  2. Найти вариант объединения-поиска непересекающихся множеств, который не только поддерживает эффективное объединение множеств, но и делает возможным итерацию по множествам и поиск их членов. (Это возможно?)
Источник

3 ответа

Решение

  1. Запустите классический алгоритм подключения компонентов. Как правило, это манипулирует структурой данных дизъюнктных множеств.

  2. Создать хеш-таблицу, отображающую узлы в связанные списки узлов.

  3. Итерировать по каждому узлу

    а. Найти репрезентативный узел в структуре данных дизъюнктных множеств

    б. При необходимости создайте связанный список для репрезентативного узла в хеш-таблице.

    с. Добавить узел в связанный список, связанный с репрезентативным узлом

Для этого требуется эффективное линейное время (т. Е. Ожидаемое Θ(|E| + |V|) (при общепринятом понимании, что непересекающиеся множества фактически являются линейным временем).

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

Источник

Да, DFS - хороший вариант для этого. Но имейте в виду, что с заданным диапазоном 10^7 узлов, если вы запускаете рекурсивную DFS, вы можете столкнуться с проблемами с памятью. Потому что в случае использования worts все узлы будут образовывать цепочку, и вам потребуется большой размер в стеке, вызывая STACKOVERFLOW(:D)

Попробуйте сделать:

  1. DFS, используя стек (не рекурсивный DFS) с порядком O(V+E) или,
  2. Используйте просто BFS (лучший выбор, учитывая простоту и количество узлов здесь) порядок (V + E)

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

Источник

Если вы храните график в виде списка смежности, а вершины обозначаются целыми числами из 1 в n-1тогда нет необходимости в объединении-поиске или хеш-таблицах.

Давайте предположим, что g[v] список (вектор) вершин, смежных с v, Более того, пусть cc быть списком списков (вектором векторов), где cc[i] обозначает вершины в i-th подключенный компонент. В целях реализации, пусть visited[v] = true если и только если мы исследовали v в DFS рутина, которую мы собираемся использовать. Тогда псевдокод выглядит так:

dfs(v, current_cc):
   visited[v] = true
   current_cc.append(v)
   for u in g[v]:
      if not visited[u]:
         dfs(u, current_cc)

for v = 0 to n-1:
   visited[i] = false

for v = 0 to n-1:
   if not visited[v]:
      current_cc = []
      dfs(v, current_cc)
      cc.append(current_cc)

//From now, cc[i] is a list of vertices in the i-th connected component, 
//so we can easily iterate and call whatever we want on them.
Источник
Другие вопросы по тегам