Implementation (Part 2)

Lektion 6 von 9 im Kurs Prims Algorithmus - Graphenalgorithmen von Coddy.

Lassen Sie den Baum nun wachsen und fügen Sie immer die günstigste Kante hinzu, die den Schnitt überquert.

Aufgabe

Mittel

Lassen Sie nun den gesamten Baum wachsen.

Schreiben Sie eine Funktion namens prim, die n und das flache edges Array (Tripel, ungerichtet) eines zusammenhängenden Graphen entgegennimmt und das Gesamtgewicht des minimalen Spannbaums (Minimum Spanning Tree) zurückgibt, wobei der Baum bei Knoten 0 beginnt.

Führen Sie ein inTree Flag pro Knoten. Suchen Sie in jeder Runde die günstigste Kante, bei der genau ein Endpunkt im Baum liegt, addieren Sie deren Gewicht und nehmen Sie den außerhalb liegenden Endpunkt in den Baum auf.

Probier es selbst

#include <stdlib.h>

int prim(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 Prims Algorithmus - Graphenalgorithmen

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