Lesson 4

The cut property guarantees the correctness of Kruskal's algorithm. Indeed, in each iteration, Kruskal's algorithm adds an edge that connects two different components. As \(S\) we can take all vertices of one of these components.

As you expected, an implementation of Kruskal's algorithm exists in the \(\texttt{networkx}\) library. The code below finds the answer to the previous problem.

from networkx import Graph, minimum_spanning_edges

graph = Graph()
for u, v, w in [
    ('A', 'B', 3), ('A', 'F', 4), ('B', 'G', 1), ('F', 'G', 3),
    ('B', 'C', 3), ('C', 'G', 2), ('F', 'E', 4), ('G', 'E', 7),
    ('C', 'D', 5), ('E', 'D', 4), ('C', 'E', 5)
]:
    graph.add_edge(u, v, weight=w)

print(sum(e[2]['weight'] for e in minimum_spanning_edges(graph)))

17