minimális feszítőfa

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank =  * n

    def find(self, u):
        if self.parent != u:
            self.parent = self.find(self.parent)  # Path compression
        return self.parent

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            if self.rank > self.rank:
                self.parent = root_u
            elif self.rank < self.rank:
                self.parent = root_v
            else:
                self.parent = root_u
                self.rank += 1

def kruskal(edges, n):
    edges.sort(key=lambda x: x)  # Rendezés súly szerint
    ds = DisjointSet(n)
    mst = 
    total_weight = 0

    for u, v, weight in edges:
        if ds.find(u) != ds.find(v):  # Ha nem keletkezik kör
            ds.union(u, v)
            mst.append((u, v, weight))
            total_weight += weight

    return mst, total_weight

# Példa gráf
edges = [
    (0, 1, 1),  # A-B
    (0, 2, 4),  # A-C
    (1, 2, 2),  # B-C
    (1, 3, 6),  # B-D
    (2, 3, 3),  # C-D
    (2, 4, 5),  # C-E
    (3, 4, 2),  # D-E
]
n = 5  # Csúcsok száma

mst, total_weight = kruskal(edges, n)
print("Minimális feszítőfa élei:", mst)
print("Összköltség:", total_weight)

import heapq

def prim(graph, start):
    visited = set()
    min_heap =   # (súly, csúcs)
    total_weight = 0
    mst = 

    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if u in visited:
            continue
        visited.add(u)
        total_weight += weight
        mst.append(u)

        for v, edge_weight in graph:
            if v not in visited:
                heapq.heappush(min_heap, (edge_weight, v))

    return total_weight

# Példa gráf mátrixként ábrázolva
graph = {
    0: ,  # A: 
    1: ,  # B
    2: ,  # C
    3: ,  # D
    4:   # E
}

total_weight = prim(graph, 0)
print("Minimális feszítőfa összköltsége:", total_weight)