Итерация по связанным компонентам

Question

Я хочу перебирать каждую связанную компоненту неориентированного графа, содержащую ~ 10 вершины. т.е. я хочу вызвать некоторую функцию F (V _я) на каждом вектор V ... V _к где У _я представляет собой вектор, содержащий данные, прикрепленный к каждому узлу в г-й компоненте связности граф.

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

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

1. Хранить все посещенные вершины в кучу, а затем повторно взять вершину из кучи, используйте DFS, чтобы найти его компонента связности V _я, вызов F (V _я) и удалите все вершины компонента из кучи.
2. Найти вариант непересекающихся множеств union-find, который не только поддерживает эффективное объединение соединений, но также позволяет эффективно перебирать множества и находить их элементы. (Возможно ли это?)

Answer 1

1. Run классический connected components algorithm. Как правило, это управляет disjoint-sets data structure.

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

3. итерацию по каждому узлу

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

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

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

Это эффективно занимает линейное время (то есть, Θ (| E | + | V |), как ожидается (по широко распространенному пониманию, что непересекающиеся множества является фактически линейным временем).

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

Answer 2

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

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

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

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

Answer 3

Если вы храните график как список смежности, а вершины обозначаются целыми числами от 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.