Kruskals Algorithmus ist ein Greedy-Algorithmus, der zur Lösung des Minimum-Spanning-Tree-Problems verwendet wird. Ein minimaler Spannbaum ist ein Spannbaum mit der kleinsten Summe von Kantengewichten in einem verbundenen ungerichteten Graphen. Der Kruskal-Algorithmus wählt Kanten in der Reihenfolge von kleinen bis großen Kantengewichten aus. Wenn die ausgewählten Kanten keinen Zyklus bilden, werden sie dem Spannbaum hinzugefügt. Der spezifische Implementierungsprozess ist wie folgt:
Sortieren Sie alle Kanten von klein nach groß entsprechend ihrer Kantengewichtung.
Wählen Sie nacheinander Kanten aus. Wenn sich die beiden Endpunkte der ausgewählten Kante nicht in derselben verbundenen Komponente befinden, fügen Sie diese Kante zum minimalen Spannbaum hinzu und führen Sie die beiden Endpunkte in derselben verbundenen Komponente zusammen.
Bis der minimale Spannbaum alle Eckpunkte im Diagramm enthält. Der Vorteil des
-Algorithmus besteht darin, dass er nur auf das Gewicht der Kante achten muss und nichts mit dem Grad des Scheitelpunkts zu tun hat, sodass er auch in dichten Diagrammen eine bessere Leistung zeigen kann. Gleichzeitig weist der Kruskal-Algorithmus auch eine gute Skalierbarkeit auf und kann das Problem der minimalen aufspannenden Gesamtstruktur in gewichteten Diagrammen problemlos lösen.
Sortieren Sie alle Kanten nach Gewicht von klein nach groß.
Befinden sich die beiden durch diese Kante verbundenen Knoten nicht in derselben verbundenen Komponente, wird die Kante hinzugefügt zum Spannbaum und führen Sie die beiden Knoten zu einer verbundenen Komponente zusammen.
Wiederholen Sie Schritt 2, bis sich alle Knoten in derselben verbundenen Komponente befinden und der zu diesem Zeitpunkt generierte Baum der minimale Spannbaum ist.
Während des Implementierungsprozesses wird Union-Lookup normalerweise verwendet, um die Konnektivität aufrechtzuerhalten und die Effizienz zu verbessern.
import java.util.*;
public class KruskalAlgorithm {
// 定义边的数据结构
class Edge implements Comparable<Edge> {
int src, dest, weight;
public int compareTo(Edge edge) {
return this.weight - edge.weight;
}
}
// 并查集数据结构
class Subset {
int parent, rank;
}
int V, E; // V是顶点数，E是边数
Edge edge[]; // 存储边的数组
// 构造函数，初始化边和顶点数
KruskalAlgorithm(int v, int e) {
V = v;
E = e;
edge = new Edge[E];
for (int i = 0; i < e; ++i)
edge[i] = new Edge();
}
// 查找父节点
int find(Subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// 合并两个子集
void union(Subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// 执行克鲁斯卡尔算法
void kruskal() {
Edge result[] = new Edge[V]; // 存储结果的数组
int e = 0; // 表示result数组中的下标
// 将边按照权重从小到大排序
Arrays.sort(edge);
// 创建V个子集
Subset subsets[] = new Subset[V];
for (int i = 0; i < V; ++i)
subsets[i] = new Subset();
// 初始化每个子集的父节点和秩
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
// 取E-1条边
int i = 0;
while (e < V - 1) {
Edge next_edge = new Edge();
next_edge = edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
// 如果两个节点不在同一个集合中，合并它们
if (x != y) {
result[e++] = next_edge;
union(subsets, x, y);
}
}
// 打印结果
System.out.println("Following are the edges in the constructed MST");
for (i = 0; i < e; ++i){
System.out.println(result[i].src + " - " + result[i" - " + result[i].weight);
return;
}
// 定义一个辅助函数，用于查找结点所在的集合
private int find(int parent[], int i) {
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
// 定义一个辅助函数，用于合并两个集合
private void union(int parent[], int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
}
}Die Funktion verwendet die Sortiermethode der Arrays-Klasse, um die Kanten nach ihrem Gewicht von klein nach groß zu sortieren. Anschließend durchläuft die Funktion die sortierten Kanten nacheinander und verwendet für jede Kante die Suchfunktion, um den Wurzelknoten der Menge zu finden, in dem sich src und dest befinden. Wenn die Wurzelknoten unterschiedlich sind, bedeutet dies, dass die beiden Mengen nicht verbunden sind und zusammengeführt werden können und die Kanten zum Ergebnisarray des minimalen Spannbaums hinzugefügt werden. Schließlich durchläuft die Funktion das Ergebnisarray des minimalen Spannbaums und gibt den Startpunkt, den Endpunkt und das Gewicht jeder Kante aus.
In dieser Implementierung wird eine Methode zur schnellen Suche nach Mengen verwendet, d. h. die Union-Suche wird verwendet, um dies zu erreichen. Jeder Knoten hat ein übergeordnetes Array, wobei parent[i] den übergeordneten Knoten von Knoten i darstellt. Wenn parent[i] == -1 ist, ist Knoten i der Wurzelknoten. Wenn bei der Suche nach der Menge, in der sich der Knoten befindet, der übergeordnete Knoten des aktuellen Knotens -1 ist, bedeutet dies, dass der Knoten der Wurzelknoten ist und direkt zurückgegeben wird. Andernfalls wird die Menge, in der sich der übergeordnete Knoten befindet, rekursiv durchsucht . Wenn Sie zwei Sammlungen zusammenführen, suchen Sie die Wurzelknoten der beiden zusammenzuführenden Sammlungen und setzen Sie den übergeordneten Knoten eines Wurzelknotens auf den Index des anderen Wurzelknotens, dh führen Sie den Wurzelknoten einer Sammlung unter dem Wurzelknoten von zusammen die andere Sammlung.
Die zeitliche Komplexität des auf diese Weise implementierten Kruskal-Algorithmus beträgt O(ElogE), wobei E die Anzahl der Kanten im Diagramm darstellt. Der Hauptzeitaufwand liegt im Prozess der Kantensortierung. Die Raumkomplexität beträgt O(V+E), wobei V die Anzahl der Eckpunkte im Diagramm darstellt. Der Hauptraumaufwand besteht darin, die Kanten und übergeordneten Arrays zu speichern.
Das obige ist der detaillierte Inhalt vonJava-Code zur Implementierung des Kruskal-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
