Обнаружение цикла на графике с использованием алгоритма Крускала

Question

Обнаружение цикла на графике с использованием алгоритма Крускала

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

KRUSKAL(G):
1 A = ∅
2 foreach v ∈ G.V:
3    MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5    if FIND-SET(u) ≠ FIND-SET(v):
6       A = A ∪ {(u, v)}
7       UNION(u, v)
8 return A

Мне трудно понять FIND-SET() а также MAKE-SET() функции или их реализация с помощью структуры данных с несвязным множеством.

Мой текущий код выглядит так:

class edge {
public:      //for quick access (temp)
char leftV;
char rightV;
int weight;
};

std::vector<edge> kruskalMST(std::vector<edge> edgeList){
std::vector<char> set;
std::vector<edge> result;
sortList(edgeList);    //sorts according to weight ( passed by reference)
do{
if(set.empty()){
set.push_pack(edgeList[i].leftV);    //also only push them when
set.push_pack(edgeList[i].rightV);    //they aren't there , will fix
result.push_back(edgeList[i]);
++i;
}
else {
if((setContains(set , edgeList[i].leftV)) && (setContains(set , edgeList[i].rightV)))
++i; //skip node
else {
set.push_pack(edgeList[i].leftV);    //also only push them when
set.push_pack(edgeList[i].rightV);    //they aren't there , will fix
result.push_back(edgeList[i]);
++i;
}
} while(i<edgeList.size());
return result;
}

Мой код обнаруживает цикл в графе, когда две вершины, которые уже присутствуют в set vector появиться снова. В большинстве случаев это работало, пока я не столкнулся с такой ситуацией:

  [a]              [c]
|                |
|                |
|                |
[b]              [d]

Когда эти ребра появляются в порядке сортировки, это происходит потому, что a, b, c, d уже втолкнули в set vector, присоединение [a] в [c] не создает цикл внутри графика, но определяется как цикл из-за текущей реализации.

Есть ли жизнеспособная альтернатива для обнаружения циклов в моем случае? Или если бы кто-то мог объяснить, как MAKE-SET, FIND-SET, а также UNION работать в алгоритме Крускала, это очень поможет.

2

algorithm c++disjoint-sets graph-algorithm union-find

Решение

Другие решения

Я не буду повторять теоретико-множественное описание алгоритма объединения / поиска (Kruskal — всего лишь частный случай этого), но использую более простой подход (при котором вы можете применять объединение по рангу и сжатию пути).

Для простоты я предположил, что у нас есть уникальный целочисленный идентификатор для каждой вершины в диапазоне от 0 до порядка — 1 (скажем, идентификатор вершины можно использовать как индекс для массива.)

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

int find(int v, int cc[]) {
while (cc[v] >= 0)
v = cc[v];
return v;
}

bool edge_union(int v0, int v1, int cc[]) {
int r0 = find(v0, cc);
int r1 = find(v1, cc);
if (r0 != r1) {
cc[r1] = r0;
return true;
}
return false;
}

Массив cc везде инициализируется -1 (и, конечно, его размер отражает порядок графа).

Сжатие пути может затем быть выполнено путем размещения встреченных вершин в цикле while функции find и затем для всех них установлен один и тот же представитель.

int find2(int v, int cc[]) {
std::deque<int> stack;
while (cc[v] >= 0) {
stack.push_back(v);
v = cc[v];
}
for (auto i : stack) {
cc[i] = v;
}
return v;
}

Для объединения по рангу мы просто используем отрицательные значения массива: чем меньше значение, тем больше ранг. Вот код:

bool edge_union2(int v0, int v1, int cc[]) {
int r0 = find(v0, cc);
int r1 = find(v1, cc);
if (r0 == r1)
return false;
if (cc[r0] < cc[r1])
cc[r1] = r0;
else {
if (cc[r1] < cc[r0])
cc[r0] = r1;
else {
cc[r1] = r0;
cc[r0] -= 1;
}
}
return true;
}

2

Источник

Accepted Answer

MAKE-SET(v) означает, что вы инициализируете набор, состоящий только из вершины v, Первоначально каждая вершина находится в наборе самостоятельно.

FIND-SET(u) это функция, которая говорит вам, к какому набору принадлежит вершина. Он должен возвращать указатель или идентификационный номер, который однозначно идентифицирует набор.

UNION(u, v) означает, что вы объединяете набор, содержащий u с набором, содержащим v, Другими словами, если u а также v в разных наборах, UNION операция сформирует новый набор, содержащий все члены наборов FIND-SET(u) а также FIND-SET(v),

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

Реализовать FIND-SET(u)Вы следуете указателям, начиная с u пока вы не достигнете лидера набора, который является единственной вершиной в наборе, которая указывает на себя.

Реализовать UNION(u, v)Вы ставите лидера одного набора в лидера другого набора.

Эти операции могут быть оптимизированы с идеями объединения по рангу и сжатию пути.

Объединение по рангу означает, что вы отслеживаете максимальное количество указателей из любой вершины в наборе на лидера. Это то же самое, что высота дерева, образованного указателями. Вы можете обновить рейтинг, выполнив постоянное количество шагов для каждого UNION операция, которая является единственным временем, когда ранг набора может измениться. Предположим, что мы объединяем множества A и B так, что A имеет больший ранг, чем B. Мы делаем так, чтобы лидер B указывал на лидера A. Результирующий набор имеет тот же ранг, что и A. Если A имеет ранг меньший, чем B мы ставим лидер A на лидера B, и результирующий набор имеет тот же ранг, что и B. Если A и B имеют одинаковый ранг, не имеет значения, какой лидер мы выберем. Делаем ли мы указание лидера A на лидера B или наоборот, результирующий набор будет иметь ранг, который на один больше, чем ранг A.

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

Если вы реализуете объединение по рангу и сжатию пути, у вас будет невероятно быстрая реализация union-find. Сложность времени для N операции это O (n α (n)), где α является обратной функцией Аккермана. Эта функция растет так медленно, что если N это число атомов во вселенной, α (п) равно 5. Таким образом, это практически константа, а оптимизированная структура данных с непересекающимися множествами является практически линейной реализацией union-find.

5