Как вы рассчитываете количество связанных графиков?

Question

Учитывая массив узлов и массив ребер, как рассчитать количество связанных графов?

Answer 1

Чтобы уточнить ответ квазеленого, вот короткий псевдокод для него:

make_set (v) создает новый набор, единственным членом которого является v.

объединение union (x, y)два набора х и у.Представительский элемент для нового набора выбран из одного из двух наборов

get_representatve (v) возвращает представителя набора, членом которого является данный узел.

Поиск связанных компонентов вgraph G = (V, E):

foreach vertex v in V:
    make_set(v)

foreach edge (u, v) in E:
    if get_representatve(u) != get_representatve:
         union(u, v)

Реализация необходимых функций - это упражнение для читателя ;-) В любом случае, оно будет работать нормально для неориентированных графов, но если вам нужны сильно связанные компоненты, вам следуетпосмотрите на алгоритм Тарьяна.

Для параллельных реализаций на самом деле не существует детерминистского алгоритма, эффективного с точки зрения работы, но есть некоторые интересные случайные.

Answer 2

Вы можете использовать объединение найти (вы можете найти его вверх). Начните со всех узлов как отдельных наборов, затем для каждого ребра объедините два узла, которые ребро соединяет в одном наборе. Затем проверьте, сколько существует различных наборов, пройдя по всем узлам и выяснив, сколько существует различных представителей.

Answer 3

• Начиная с одного из узлов, выполните BFS или DFS, чтобы получить все узлы, подключенные с этого узла.
• Теперь итерируйте список узлов, чтобы найти любой узел, который уже не включен,
• выполните ту же процедуру на узле.Повторяйте, пока все узлы не будут посещены.
• К настоящему времени у вас будут все графики в ваших данных.

Answer 4

Для неориентированных графов это можно сделать за O (n) раз с помощью простой DFS.Вот как:

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

Чтобы найти ответ, запустите DFS на любом узле и запустите процедуру explore на этом узле.Сохраните целое число (скажем, cc) и передайте его процедуре explore каждый раз, когда она вызывается.Кроме того, сохраните хэш-карту / словарь или такой, который отображает cc на соответствующий узел.На каждом уровне процедуры explore сопоставьте текущий узел с cc на данный момент.Каждый раз, когда процедура исследования вызывается рекурсивно, передайте ей одно и то же значение cc.

Каждый раз, когда explore возвращается в цикл DFS, увеличивайте cc и передайте это значение в следующий раз.Как только вы закончите со всей DFS, у вас будет словарь, который сопоставляет каждый узел с соответствующим номером подключенного компонента.Значение cc в конце этой процедуры может дать вам количество подключенных компонентов, которые есть на графике.

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

function explore(node, graph, cc, map){
    map(currentNode) = cc
    //find all children of current node, and push onto stack. 
    //mark current node as visited
    for i in stack:
        explore(i, graph, cc, map)
}

function DFS{
     int cc = -1
     for node in keysOfGraph:
          if not visited:
              cc++
              explore(node, graph, cc, map)

return cc
}

Из Алгоритмы Дасгупты (раздел 3.2.3)

Answer 5

Да, есть алгоритм, который является линейным по размеру графика, O (| V | + | E |).

visited := the empty set
count := 0
for each vertex v in vertices:
    if v not in visited:
        count++
        add v and all nodes reachable from v to visited
return count