Алгоритм Крускала: что такое алгоритм, чтобы проверить, образуют ли ребра графа петлю или нет?
Может ли кто-нибудь предоставить мне информацию о том, как проверить, образуют ли ребра графа петлю или нет? Любая информация будет очень полезна. Спасибо заранее.
3 ответа
Алгоритм Крускала (которым вы пометили вопрос) использует структуру данных непересекающихся множеств, инициализированную непересекающимися наборами для каждой вершины. Затем для каждого ребра объединяются два набора, которым принадлежат вершины ребра. Если две вершины уже находятся в одном наборе, вы нашли петлю. Если вы удаляете край каждый раз, когда это происходит, вы получите остовное дерево. Если вы сортируете ребра в порядке возрастания веса, это будет минимальное остовное дерево.
Если вам нужно только узнать, содержит ли граф циклы или нет, используйте что-то более простое в качестве DFS - если у какого-либо узла есть соседний узел (кроме родительского), который уже был посещен - вы нашли цикл.
Сделайте полную DFS на графике. Поддерживайте две логические переменные, "посещенные" и "завершенные" для каждого узла в графе. "посещен", чтобы указать, была ли посещена вершина или нет, и "завершен", чтобы указать, завершена ли DFS, начиная с этого конкретного узла, или нет. Если при выполнении DFS вы попадаете на узел, который уже был посещен, но его DFS еще не завершен, то на графике существует цикл.
Это использование структуры данных быстрого поиска объединения, которая проверяет, находится ли соединяемое ребро между вершинами одного и того же кластера.