Greedy Algorithms - Kruskal

def kruskal(edges):
    sorted_edges = sorted(edges, key=lambda edge: edge[2])

    # Αντιστοιχίζω κάθε κορυφή σε κενό σετ/σύνολο
    # Και μετά, θα προσθέσω στο σετ την ίδια κορυφή
    # {A: A, B: B, C: C, ....}
    subgraph_node = dict()
    for u, v, weight in sorted_edges:
        subgraph_node[u] = set()
        subgraph_node[v] = set()
    for u in subgraph_node:
        subgraph_node[u].add(u)

    is_included_in_mst = list()

    for u, v, weight in sorted_edges:
        if subgraph_node[u] == subgraph_node[v]:
            is_included_in_mst.append(False)
        else:
            is_included_in_mst.append(True)
            # Ενώνω
            combined_subgraph = set.union(subgraph_node[u], subgraph_node[v])
            # Κάθε κορυφή του λεξικού πλέον αντιστοιχίζεται σε ένα σετ/σύνολο,
            # το οποίο περιέχει το υπόλοιπο δένδρο/γράφο στον οποίο ανήκει η κορυφή αυτή
            for k in combined_subgraph:
                subgraph_node[k] = combined_subgraph

    return is_included_in_mst, sorted_edges


def visualize(edges, colors):
    from pyvis.network import Network
    net = Network()
    edges = [(edges[i][0], edges[i][1], edges[i][2], colors[i]) for i in range(len(edges))]
    for u, v, weight, color in edges:
        net.add_node(u)
        net.add_node(v)
        net.add_edge(u, v, label=str(weight), color=color)

    net.show('network.html')


edges = [('A', 'B', 1), ('B', 'C', 4), ('B', 'D', 2), ('C', 'D', 6), ('A', 'D', 3)]

# visualize(edges,colors)
is_included_in_mst, sorted_edges = kruskal(edges)
colors = ['red' if is_included else 'blue' for is_included in is_included_in_mst]
visualize(sorted_edges, colors)