Algoritmo di Kruskal per Spanning Tree con implementazione Java

1. Panoramica

In un articolo precedente, abbiamo introdotto l'algoritmo di Prim per trovare gli spanning tree minimi. In questo articolo, utilizzeremo un altro approccio, l'algoritmo di Kruskal, per risolvere i problemi di spanning tree minimo e massimo.

2. Spanning Tree

Uno spanning tree di un grafo non orientato è un sottografo connesso che copre tutti i nodi del grafo con il minimo numero possibile di bordi. In generale, un grafico può avere più di uno spanning tree. La figura seguente mostra un grafico con uno spanning tree (i bordi dello spanning tree sono in rosso):

Se il grafico è ponderato per i bordi, possiamo definire il peso di uno spanning tree come la somma dei pesi di tutti i suoi bordi. Un albero di copertura minimo è un albero di copertura il cui peso è il più piccolo tra tutti gli alberi di copertura possibili. La figura seguente mostra uno spanning tree minimo su un grafico ponderato sul bordo:

Allo stesso modo, uno spanning tree massimo ha il peso maggiore tra tutti gli spanning tree. La figura seguente mostra un albero di copertura massimo su un grafico ponderato sul bordo:

3. Algoritmo di Kruskal

Dato un grafico, possiamo usare l'algoritmo di Kruskal per trovare il suo albero di copertura minimo. Se il numero di nodi in un grafo è V , allora ciascuno dei suoi spanning tree dovrebbe avere bordi (V-1) e non contenere cicli. Possiamo descrivere l'algoritmo di Kruskal nel seguente pseudo-codice:

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

Eseguiamo passo dopo passo l'algoritmo di Kruskal per uno spanning tree minimo sul nostro grafico di esempio:

In primo luogo, scegliamo il bordo (0, 2) perché ha il peso più piccolo. Quindi, possiamo aggiungere i bordi (3, 4) e (0, 1) poiché non creano alcun ciclo. Ora il candidato successivo è bordo (1, 2) con peso 9. Tuttavia, se includiamo questo bordo, produrremo un ciclo (0, 1, 2). Pertanto, scartiamo questo bordo e continuiamo a scegliere il successivo più piccolo. Infine, l'algoritmo termina aggiungendo il bordo (2, 4) del peso 10.

Per calcolare il massimo spanning tree, possiamo modificare l'ordinamento in ordine decrescente. Gli altri passaggi rimangono gli stessi. La figura seguente mostra la costruzione passo passo di un albero di copertura massimo sul nostro grafico di esempio.

4. Rilevamento del ciclo con un insieme disgiunto

Nell'algoritmo di Kruskal, la parte cruciale è controllare se un bordo creerà un ciclo se lo aggiungiamo all'insieme di bordi esistente. Esistono diversi algoritmi di rilevamento del ciclo del grafico che possiamo utilizzare. Ad esempio, possiamo utilizzare un algoritmo di ricerca in profondità (DFS) per attraversare il grafico e rilevare se è presente un ciclo.

Tuttavia, è necessario eseguire un rilevamento del ciclo sui bordi esistenti ogni volta che testiamo un nuovo bordo. Una soluzione più rapida consiste nell'utilizzare l'algoritmo Union-Find con la struttura dati disgiunta perché utilizza anche un approccio di aggiunta incrementale del bordo per rilevare i cicli. Possiamo adattarlo al nostro processo di costruzione dello spanning tree.

4.1. Set disgiunto e costruzione di alberi spanning

In primo luogo, trattiamo ogni nodo del grafico come un insieme individuale che contiene un solo nodo. Quindi, ogni volta che introduciamo un bordo, controlliamo se i suoi due nodi sono nello stesso insieme. Se la risposta è sì, creerà un ciclo. Altrimenti, uniamo i due insiemi disgiunti in un insieme e includiamo il bordo per lo spanning tree.

Possiamo ripetere i passaggi precedenti fino a quando non costruiamo l'intero albero spanning.

Ad esempio, nella costruzione dello spanning tree minimo sopra, abbiamo prima 5 set di nodi: {0}, {1}, {2}, {3}, {4}. Quando controlliamo il primo bordo (0, 2), i suoi due nodi si trovano in insiemi di nodi diversi. Pertanto, possiamo includere questo margine e unire {0} e {2} in un insieme {0, 2}.

Possiamo fare operazioni simili per i bordi (3, 4) e (0, 1). Gli insiemi di nodi diventano quindi {0, 1, 2} e {3, 4}. Quando controlliamo il bordo successivo (1, 2), possiamo vedere che entrambi i nodi di questo bordo si trovano nello stesso insieme. Pertanto, scartiamo questo bordo e continuiamo a controllare quello successivo. Infine, il bordo (2, 4) soddisfa la nostra condizione e possiamo includerlo per l'albero di copertura minimo.

4.2. Implementazione di set disgiunti

Possiamo usare una struttura ad albero per rappresentare un insieme disgiunto. Ogni nodo ha un puntatore padre per fare riferimento al proprio nodo padre. In ogni set, c'è un nodo radice univoco che rappresenta questo set. Il nodo radice ha un puntatore genitore autoreferenziale .

Usiamo una classe Java per definire le informazioni sull'insieme disgiunto:

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

Etichettiamo ogni nodo del grafico con un numero intero, a partire da 0. Possiamo usare una struttura dati di lista, List nodes , per memorizzare le informazioni sugli insiemi disgiunti di un grafico. All'inizio, ogni nodo è il membro rappresentativo del proprio insieme:

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

4.3. Trova operazione

Per trovare l'insieme a cui appartiene un nodo, possiamo seguire la catena padre del nodo verso l'alto fino a raggiungere il nodo radice:

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

È possibile avere una struttura ad albero altamente sbilanciata per un insieme disgiunto. Siamo in grado di migliorare la scoperta operazione utilizzando il p compressione ath tecnica.

Poiché ogni nodo che visitiamo sulla strada per il nodo radice fa parte dello stesso insieme, possiamo collegare il nodo radice direttamente al suo riferimento padre . La prossima volta che visiteremo questo nodo, abbiamo bisogno di un percorso di ricerca per ottenere il nodo radice:

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. Operazione dell'Unione

Se i due nodi di un arco sono in insiemi differenti, combineremo questi due insiemi in uno solo. Possiamo ottenere questa operazione di unione impostando la radice di un nodo rappresentativo sull'altro nodo rappresentativo:

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

Questa semplice operazione di unione potrebbe produrre un albero altamente sbilanciato poiché abbiamo scelto un nodo radice casuale per l'insieme unito. Possiamo migliorare le prestazioni usando un'unione per tecnica di rango .

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.

Quindi usiamo un ciclo per scorrere l'elenco dei bordi ordinati. In ogni iterazione, controlliamo se verrà formato un ciclo aggiungendo il bordo al set di bordi dello spanning tree corrente. Questo ciclo con il rilevamento del ciclo richiede al massimo il tempo O (ElogV) .

Pertanto, il tempo di esecuzione complessivo è O (ELogE + ELogV) . Poiché il valore di E è nella scala di O (V2) , la complessità temporale dell'algoritmo di Kruskal è O (ElogE) o O (ElogV) .

6. Conclusione

In questo articolo, abbiamo imparato come utilizzare l'algoritmo di Kruskal per trovare uno spanning tree minimo o massimo di un grafico. Come sempre, il codice sorgente dell'articolo è disponibile su GitHub.