Kruskal’s και Prim’s Algorithm

Ας μάθουμε για δύο ενδιαφέροντες αλγορίθμους που χρησιμοποιούμε όταν έχουμε ένα γράφο και θέλουμε να βρούμε κάτι συγκεκριμένο. Ειδικά, θα δούμε πώς μπορούμε να βρούμε το Minimum Spanning Tree (MST), που είναι σαν να ψάχνουμε για το πιο οικονομικό τρόπο να συνδέσουμε όλα τα σημεία ενός γράφου χωρίς να δημιουργήσουμε κύκλους.

Τι Είναι το Minimum Spanning Tree (MST);

Σκέψου ότι έχεις μια ομάδα φίλων και θέλεις να συνδέσεις όλους τους φίλους με καλώδια, αλλά θέλεις να ξοδέψεις όσο το δυνατόν λιγότερα χρήματα για τα καλώδια. Κάθε καλώδιο έχει και μια τιμή. Το MST σου λέει ποια καλώδια να χρησιμοποιήσεις για να συνδέσεις όλους τους φίλους με το μικρότερο κόστος, χωρίς να δημιουργήσεις κύκλους με τα καλώδια.

Kruskal’s Algorithm (Αλγόριθμος του Kruskal)

Ο Αλγόριθμος του Kruskal είναι σαν να παίρνεις όλα τα καλώδια που έχεις και να τα βάζεις σε μια σειρά από το φθηνότερο στο πιο ακριβό. Στη συνέχεια, ξεκινάς με το φθηνότερο καλώδιο και το προσθέτεις στη σύνδεση των φίλων, αν δεν δημιουργεί κύκλους. Συνεχίζεις με το επόμενο φθηνότερο καλώδιο και έτσι μέχρι να συνδέσεις όλους τους φίλους.

Ας δούμε πώς μπορούμε να το υλοποιήσουμε στην C#:

using System;
using System.Collections.Generic;
using System.Linq;

public class KruskalAlgorithm
{
public class Edge
{
public int Start { get; }
public int End { get; }
public int Weight { get; }

public Edge(int start, int end, int weight)
{
Start = start;
End = end;
Weight = weight;
}
}

public class DisjointSet
{
private readonly Dictionary<int, int> parent = new();
private readonly Dictionary<int, int> rank = new();

public void MakeSet(int x)
{
parent[x] = x;
rank[x] = 0;
}

public int Find(int x)
{
if (parent[x] != x)
parent[x] = Find(parent[x]);
return parent[x];
}

public void Union(int x, int y)
{
int rootX = Find(x);
int rootY = Find(y);

if (rootX != rootY)
{
if (rank[rootX] > rank[rootY])
parent[rootY] = rootX;
else if (rank[rootX] < rank[rootY])
parent[rootX] = rootY;
else
{
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
}

public static List<Edge> Kruskal(int numberOfNodes, List<Edge> edges)
{
var result = new List<Edge>();
var disjointSet = new DisjointSet();

// Initialize disjoint sets
for (int i = 1; i <= numberOfNodes; i++)
{
disjointSet.MakeSet(i);
}

// Sort edges by weight
edges = edges.OrderBy(edge => edge.Weight).ToList();

foreach (var edge in edges)
{
int rootStart = disjointSet.Find(edge.Start);
int rootEnd = disjointSet.Find(edge.End);

// If the edge does not form a cycle
if (rootStart != rootEnd)
{
result.Add(edge);
disjointSet.Union(rootStart, rootEnd);
}
}

return result;
}

public static void Main()
{
var edges = new List<Edge>
{
new Edge(1, 2, 4),
new Edge(1, 3, 1),
new Edge(2, 3, 2),
new Edge(2, 4, 5),
new Edge(3, 4, 8)
};

var result = Kruskal(4, edges);

Console.WriteLine(“Edges in the Minimum Spanning Tree:”);
foreach (var edge in result)
{
Console.WriteLine($”{edge.Start} – {edge.End}: {edge.Weight}”);
}
}

}

Prim’s Algorithm (Αλγόριθμος του Prim)

Ο Αλγόριθμος του Prim είναι σαν να ξεκινάς από έναν φίλο και να προσθέτεις το πιο φθηνό καλώδιο που συνδέει τον φίλο αυτό με κάποιον άλλο φίλο που δεν έχει συνδεθεί ακόμα. Συνεχίζεις με αυτόν τον τρόπο μέχρι να συνδέσεις όλους τους φίλους.

Ας δούμε πώς μπορούμε να το υλοποιήσουμε στην C#:

using System;
using System.Collections.Generic;
using System.Linq;

public class PrimAlgorithm
{
    public class Edge
    {
        public int Start { get; }
        public int End { get; }
        public int Weight { get; }

        public Edge(int start, int end, int weight)
        {
            Start = start;
            End = end;
            Weight = weight;
        }
    }

    public static List<Edge> Prim(int numberOfNodes, List<Edge> edges, int startNode)
    {
        var result = new List<Edge>();
        var minHeap = new SortedSet<Edge>(Comparer<Edge>.Create((a, b) => a.Weight.CompareTo(b.Weight)));
        var visited = new HashSet<int>();

        // Function to add edges to the heap
        void AddEdges(int node)
        {
            visited.Add(node);
            foreach (var edge in edges.Where(e => e.Start == node || e.End == node))
            {
                if (!visited.Contains(edge.Start) || !visited.Contains(edge.End))
                {
                    minHeap.Add(edge);
                }
            }
        }

        AddEdges(startNode);

        while (minHeap.Count > 0)
        {
            var edge = minHeap.Min;
            minHeap.Remove(edge);

            if (visited.Contains(edge.Start) && visited.Contains(edge.End))
            {
                continue;
            }

            result.Add(edge);
            AddEdges(edge.Start);
            AddEdges(edge.End);
        }

        return result;
    }

    public static void Main()
    {
        var edges = new List<Edge>
        {
            new Edge(1, 2, 4),
            new Edge(1, 3, 1),
            new Edge(2, 3, 2),
            new Edge(2, 4, 5),
            new Edge(3, 4, 8)
        };

        var result = Prim(4, edges, 1);

        Console.WriteLine("Edges in the Minimum Spanning Tree:");
        foreach (var edge in result)
        {
            Console.WriteLine($"{edge.Start} - {edge.End}: {edge.Weight}");
        }
    }
}

Τι Κάνουν Αυτοί οι Αλγόριθμοι;

Αλγόριθμος του Kruskal: Σου δίνει τη δυνατότητα να συνδέσεις όλους τους κόμβους του γράφου με το μικρότερο συνολικό κόστος, επιλέγοντας τις πιο φθηνές ακμές πρώτα και αποφεύγοντας τους κύκλους.
Αλγόριθμος του Prim: Ξεκινά από έναν κόμβο και επεκτείνεται συνεχώς με τις πιο φθηνές ακμές για να συνδέσει όλους τους κόμβους.

Γιατί Χρησιμοποιούμε Αυτούς τους Αλγόριθμους;

Κερδίζουμε Χρόνο και Χρήμα: Ειδικά όταν έχουμε έναν μεγάλο γράφο, οι αλγόριθμοι αυτοί μας βοηθούν να βρούμε την πιο οικονομική λύση.

Σύνδεση Δικτύων: Όταν συνδέουμε δίκτυα, όπως υπολογιστές ή δρόμους, θέλουμε να το κάνουμε με τον πιο οικονομικό τρόπο.

Αυτοί οι αλγόριθμοι είναι πολύ χρήσιμοι για να καταλάβουμε πώς μπορούμε να συνδέσουμε στοιχεία με το λιγότερο κόστος. Αν έχεις απορίες ή θέλεις να μάθεις περισσότερα, μην διστάσεις να ρωτήσεις!

Kruskal Download