Implementation (Part 2)

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

Fügen Sie nun die günstigste sichere Kante hinzu, bis der MST vollständig ist.

Aufgabe

Mittel

Erstellen Sie nun den MST.

Schreiben Sie eine Funktion namens kruskal, die n und das flache edges-Array (Tripel, ungerichtet) eines zusammenhängenden Graphen entgegennimmt und das Gesamtgewicht seines minimalen Spannbaums (Minimum Spanning Tree) zurückgibt.

Wählen Sie wiederholt die günstigste ungenutzte Kante aus; wenn sich ihre Endpunkte in verschiedenen Mengen befinden, vereinigen Sie diese und addieren Sie das Gewicht der Kante; andernfalls überspringen Sie diese.

Verwenden Sie die Union-Find-Idee aus der vorherigen Lektion wieder.

Probier es selbst

#include <stdlib.h>

int kruskal(int n, int* edges, int edges_size) {
    // Schreibe hier den Code
    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 Code Implementation (Part 1)Implementation (Part 2) Projekt-Lektion

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2