Как обнаружить цикл в неориентированном графе с помощью непересекающихся множеств?

Алгоритм:

For each edge (u, v) in the Adjacency list:
If u and v do not belong to the same set:
   Union(u, v)
else:
  return true // cycle detected
return false

График:

(1)-------(2)

Список смежности:

[1] -> [2]

[2] -> [1]

Непересекающиеся наборы:

{{1}, {2}}

Итерация 1:

Ребро e = (1, 2)

Союз(1, 2)

Непересекающиеся множества = {{1, 2}}

Итерация 2:

Ребро e = (2, 1)

И 2, и 1 принадлежат одному и тому же множеству, поэтому алгоритм обнаруживает цикл. Очевидно, что граф не содержит циклов.

Алгоритм безупречно работает для ориентированных графов. Помогите пожалуйста с этим анализом.


graph algorithm cycle disjoint-sets disjoint-union
person Abhishek    schedule 16.04.2017    source источник
comment
В вашем примере нет двух ребер, только одно ребро.   -  person Ante    schedule 16.04.2017
comment
@Ante это неориентированный граф, поэтому adj[1] имеет ребро (1, 2), а adj[2] имеет (2, 1)   -  person Abhishek    schedule 16.04.2017
comment
Да, это неориентированный граф, (1, 2) такой же, как (2, 1).   -  person Ante    schedule 16.04.2017
comment
@Ante семантически да, но в реальной реализации вы обычно перебираете список смежности каждой вершины, поэтому в конечном итоге вы дважды попадаете в край. Я знаю, что алгоритм работает, если я извлекаю уникальные наборы ребер, но это не кажется правильным и увеличивает сложность.   -  person Abhishek    schedule 16.04.2017
comment
Что вы имеете в виду под «семантически»?! Если вы работаете с неориентированным графом, то ребра не имеют направления.   -  person Ante    schedule 16.04.2017
comment
@ Анте, пожалуйста, посмотрите на список смежности, упомянутый в вопросе. В любой реализации вы перебираете списки смежности. Я понимаю, что ребра не имеют направления, и это никак не меняет прил. Поправьте меня, если я ошибаюсь.   -  person Abhishek    schedule 16.04.2017
comment
В алгоритме вы перебираете края! Списки смежности — это только один из способов реализации структуры данных графа. Итак, если вы реализуете неориентированный граф со списками смежности, позаботьтесь о том, чтобы не использовать одно и то же ребро дважды. Есть несколько способов сделать это. Возможно, проще всего взять элементы списка с большим значением, чем у узла. Например. узел 1 имеет элементы [2], а так как 2›1 можно использовать ребро (1,2). Узел 2 имеет элемент [1], и, поскольку 1‹2, не используйте ребро (2,1).   -  person Ante    schedule 16.04.2017

Ответы (1)


arrow_upward
1
arrow_downward

Цикл должен иметь четкие ребра! В алгоритме поиска объединения вы перебираете все ребра. Вам нужно будет отфильтровать повторяющиеся ребра из списка смежности. В вашем случае есть только одна итерация, поэтому она вернет false.

person 夢のの夢    schedule 16.04.2017
comment
Таким образом, алгоритм становится зависимым от типа графа (направленный/ненаправленный)? Тот факт, что мне нужно запускать алгоритм по-разному для ненаправленных, кажется странным, или я ошибаюсь? - person Abhishek; 16.04.2017
comment
непересекающиеся множества используются для неориентированного графа, да. - person 夢のの夢; 16.04.2017
comment
Этот алгоритм непересекающихся множеств отлично работает для ориентированных графов. - person Abhishek; 16.04.2017