Алгоритъмът на Крускал за обхващане на дървета с внедряване на Java

1. Общ преглед

В предишна статия въведохме алгоритъма на Prim за намиране на минималните обхващащи дървета. В тази статия ще използваме друг подход, алгоритъм на Крускал, за да разрешим минималните и максималните проблеми с обхващащото дърво.

2. Обхващащо дърво

Обхващащо дърво на неориентирана графика е свързан подграф, който покрива всички възли на графиката с минимално възможния брой ръбове. По принцип графиката може да има повече от едно обхващащо дърво. Следващата фигура показва графика с обхващащо дърво (ръбовете на обхващащото дърво са в червено):

Ако графиката е претеглена с ръбове, можем да определим теглото на обхващащото дърво като сбор от тежестите на всички негови ръбове. Минималното обхващащо дърво е обхващащо дърво, чието тегло е най-малкото от всички възможни обхващащи дървета. Следващата фигура показва минимално обхващащо дърво на графика, претеглена с ръб:

По същия начин дървото с максимално обхващане има най-голямото тегло сред всички обхващащи дървета. Следващата фигура показва дърво с максимален обхват на графика, претеглена с ръб:

3. Алгоритъмът на Крускал

Като дадем графика, можем да използваме алгоритъма на Крускал, за да намерим нейното минимално обхващащо дърво. Ако броят на възлите в графика е V , тогава всяко от нейните обхващащи дървета трябва да има (V-1) ръбове и да не съдържа цикли. Можем да опишем алгоритъма на Крускал в следния псевдокод:

Initialize an empty edge set T. Sort all graph edges by the ascending order of their weight values. foreach edge in the sorted edge list Check whether it will create a cycle with the edges inside T. If the edge doesn't introduce any cycles, add it into T. If T has (V-1) edges, exit the loop. return T

Нека стартираме алгоритъма на Крускал за минимално обхващащо дърво на нашата примерна графика стъпка по стъпка:

Първо, избираме ръба (0, 2), защото той има най-малкото тегло. След това можем да добавим ръбове (3, 4) и (0, 1), тъй като те не създават никакви цикли. Сега следващият кандидат е ръб (1, 2) с тегло 9. Ако обаче включим този ръб, ще създадем цикъл (0, 1, 2). Следователно ние отхвърляме този ръб и продължаваме да избираме следващия най-малък. И накрая, алгоритъмът завършва чрез добавяне на ръба (2, 4) на тежест 10.

За да изчислим максималното обхващащо дърво, можем да променим реда за сортиране на низходящ ред. Останалите стъпки остават същите. Следващата фигура показва поетапната конструкция на максимално обхващащо дърво на нашата примерна графика.

4. Откриване на цикъл с недисконтен комплект

В алгоритъма на Kruskal, решаващата част е да се провери дали ръбът ще създаде цикъл, ако го добавим към съществуващия набор от ръбове. Има няколко алгоритми за откриване на графичен цикъл, които можем да използваме. Например, можем да използваме алгоритъм за първоначално търсене (DFS), за да прекосим графиката и да открием дали има цикъл.

Трябва обаче да правим откриване на цикъл на съществуващите ръбове всеки път, когато тестваме нов ръб. По-бързо решение е да се използва алгоритъмът Union-Find със структурата на несвързаните данни, тъй като той също така използва подход за добавяне на инкрементални ръбове за откриване на цикли. Можем да го впишем в нашия процес на изграждане на обхващащо дърво.

4.1. Конструкция на неразделим комплект и обхващащо дърво

Първо, ние третираме всеки възел на графиката като индивидуален набор, който съдържа само един възел. След това всеки път, когато въвеждаме ръб, проверяваме дали двата му възела са в един и същ набор. Ако отговорът е да, тогава той ще създаде цикъл. В противен случай обединяваме двата несвързани множества в един комплект и включваме ръба на обхващащото дърво.

Можем да повторим горните стъпки, докато изградим цялото обхващащо дърво.

Например в горната минимална конструкция на обхващащо дърво първо имаме 5 комплекта възли: {0}, {1}, {2}, {3}, {4}. Когато проверяваме първия ръб (0, 2), двата му възла са в различни набори от възли. Следователно можем да включим този ръб и да обединим {0} и {2} в един набор {0, 2}.

Можем да правим подобни операции за ръбовете (3, 4) и (0, 1). След това наборите от възли стават {0, 1, 2} и {3, 4}. Когато проверяваме следващия ръб (1, 2), можем да видим, че и двата възела на този ръб са в един и същ набор. Следователно ние отхвърляме този ръб и продължаваме да проверяваме следващия. И накрая, ръбът (2, 4) удовлетворява нашето условие и можем да го включим за минималното обхващащо дърво.

4.2. Внедряване на несъгласен набор

Можем да използваме дървесна структура, за да представим несъединяващ се набор. Всеки възел има родителски указател за препратка към неговия родителски възел. Във всеки набор има уникален корен възел, който представлява този набор. Коренният възел има самоотправен родителски указател.

Нека използваме клас Java, за да дефинираме информацията за несвързания набор:

public class DisjointSetInfo { private Integer parentNode; DisjointSetInfo(Integer parent) { setParentNode(parent); } //standard setters and getters }

Нека обозначим всеки възел на графика с цяло число, започвайки от 0. Можем да използваме структура на данните от списъка, Списъчни възли , за да съхраняваме информацията за несвязан набор от графика. В началото всеки възел е представителен член на собствения си набор:

void initDisjointSets(int totalNodes) { nodes = new ArrayList(totalNodes); for (int i = 0; i < totalNodes; i++) { nodes.add(new DisjointSetInfo(i)); } } 

4.3. Намерете операция

За да намерим набора, към който принадлежи възел, можем да следваме родителската верига на възела нагоре, докато стигнем до основния възел:

Integer find(Integer node) { Integer parent = nodes.get(node).getParentNode(); if (parent.equals(node)) { return node; } else { return find(parent); } }

Възможно е да има силно небалансирана дървесна структура за неразделим набор. Ние можем да се подобри находка операцията с помощта на стр Атина компресия техника.

Since each node we visit on the way to the root node is part of the same set, we can attach the root node to its parent reference directly. The next time when we visit this node, we need one lookup path to get the root node:

Integer pathCompressionFind(Integer node) { DisjointSetInfo setInfo = nodes.get(node); Integer parent = setInfo.getParentNode(); if (parent.equals(node)) { return node; } else { Integer parentNode = find(parent); setInfo.setParentNode(parentNode); return parentNode; } }

4.4. Union Operation

If the two nodes of an edge are in different sets, we'll combine these two sets into one. We can achieve this union operation by setting the root of one representative node to the other representative node:

void union(Integer rootU, Integer rootV) { DisjointSetInfo setInfoU = nodes.get(rootU); setInfoU.setParentNode(rootV); }

This simple union operation could produce a highly unbalanced tree as we chose a random root node for the merged set. We can improve the performance using a union by rank technique.

Since it is tree depth that affects the running time of the find operation, we attach the set with the shorter tree to the set with the longer tree. This technique only increases the depth of the merged tree if the original two trees have the same depth.

To achieve this, we first add a rank property to the DisjointSetInfo class:

public class DisjointSetInfo { private Integer parentNode; private int rank; DisjointSetInfo(Integer parent) { setParentNode(parent); setRank(0); } //standard setters and getters }

In the beginning, a single node disjoint has a rank of 0. During the union of two sets, the root node with a higher rank becomes the root node of the merged set. We increase the new root node's rank by one only if the original two ranks are the same:

void unionByRank(int rootU, int rootV) { DisjointSetInfo setInfoU = nodes.get(rootU); DisjointSetInfo setInfoV = nodes.get(rootV); int rankU = setInfoU.getRank(); int rankV = setInfoV.getRank(); if (rankU < rankV) { setInfoU.setParentNode(rootV); } else { setInfoV.setParentNode(rootU); if (rankU == rankV) { setInfoU.setRank(rankU + 1); } } }

4.5. Cycle Detection

We can determine whether two nodes are in the same disjoint set by comparing the results of two find operations. If they have the same representive root node, then we've detected a cycle. Otherwise, we merge the two disjoint sets by using a union operation:

boolean detectCycle(Integer u, Integer v) { Integer rootU = pathCompressionFind(u); Integer rootV = pathCompressionFind(v); if (rootU.equals(rootV)) { return true; } unionByRank(rootU, rootV); return false; } 

The cycle detection, with the union by rank technique alone, has a running time of O(logV). We can achieve better performance with both path compression and union by rank techniques. The running time is O(α(V)), where α(V) is the inverse Ackermann function of the total number of nodes. It is a small constant that is less than 5 in our real-world computations.

5. Java Implementation of Kruskal’s Algorithm

We can use the ValueGraph data structure in Google Guava to represent an edge-weighted graph.

To use ValueGraph, we first need to add the Guava dependency to our project's pom.xml file:

     com.google.guava     guava     28.1-jre 

We can wrap the above cycle detection methods into a CycleDetector class and use it in Kruskal's algorithm. Since the minimum and maximum spanning tree construction algorithms only have a slight difference, we can use one general function to achieve both constructions:

ValueGraph spanningTree(ValueGraph graph, boolean minSpanningTree) { Set edges = graph.edges(); List edgeList = new ArrayList(edges); if (minSpanningTree) { edgeList.sort(Comparator.comparing(e -> graph.edgeValue(e).get())); } else { edgeList.sort(Collections.reverseOrder(Comparator.comparing(e -> graph.edgeValue(e).get()))); } int totalNodes = graph.nodes().size(); CycleDetector cycleDetector = new CycleDetector(totalNodes); int edgeCount = 0; MutableValueGraph spanningTree = ValueGraphBuilder.undirected().build(); for (EndpointPair edge : edgeList) { if (cycleDetector.detectCycle(edge.nodeU(), edge.nodeV())) { continue; } spanningTree.putEdgeValue(edge.nodeU(), edge.nodeV(), graph.edgeValue(edge).get()); edgeCount++; if (edgeCount == totalNodes - 1) { break; } } return spanningTree; }

In Kruskal's algorithm, we first sort all graph edges by their weights. This operation takes O(ElogE) time, where E is the total number of edges.

След това използваме цикъл, за да преминем през сортирания списък с ръбове. Във всяка итерация проверяваме дали ще се формира цикъл чрез добавяне на ръба към текущия набор от обхващащи дървета ръбове. Този цикъл с откриване на цикъл отнема най-много O (ElogV) време.

Следователно, общото време на работа е O (ELogE + ELogV) . Тъй като стойността на E е в скалата на O (V2) , сложността във времето на алгоритъма на Kruskal е O (ElogE) или O (ElogV) .

6. Заключение

В тази статия научихме как да използваме алгоритъма на Крускал, за да намерим минимално или максимално обхващащо дърво на графика. Както винаги, изходният код на статията е достъпен в GitHub.