Implementation (Part 1)

Lektion 5 von 9 im Kurs Kruskals Algorithmus - Graph-Algorithmen von Coddy.

Wir beginnen mit Union-Find, der Engine zur Zyklenerkennung.

Aufgabe

Mittel

Kruskals Zyklustest basiert auf Union-Find. Lassen Sie uns dies zuerst aufbauen und verwenden, um die Anzahl der zusammenhängenden Komponenten zu zählen.

Schreiben Sie eine Funktion namens countSets, die n und das flache edges Array (Tripel [u, v, w, ...], ungerichtet; ignorieren Sie hier die Gewichte) entgegennimmt und die Anzahl der zusammenhängenden Komponenten zurückgibt, die mit Union-Find berechnet wurden.

Zum Beispiel gibt es bei 4 Vertices und Kanten [0,1,5, 2,3,5] 2 Komponenten: {0,1} und {2,3}.

Probier es selbst

#include <stdlib.h>

int countSets(int n, int* edges, int edges_size) {
    // Hier Code schreiben
    return 0;
}

Teste dich selbst

Diese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.

Alle Lektionen in Kruskals Algorithmus - Graph-Algorithmen

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2