Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

Kruskal's algorithm (Minimum spanning tree)

Introduction

Kruskal's algorithm - efficient algorithm for constructing the minimum spanning tree of a weighted connected undirected graph. The algorithm is also used to find some approximations for the Steiner problem.

Task

The algorithm solves the problem of finding the minimum spanning tree (MST).

Example problem

The problem of finding the minimum spanning tree is often encountered in a similar setting: for example, there are n cities that need to be connected by roads so that one can get from any city to any other (directly or through other cities). It is allowed to build roads between given pairs of cities and the cost of building each such road is known. It is required to decide which roads should be built in order to minimize the total cost of construction.

Algorithm

At the beginning, the current set of edges is set to empty. Then, while it is possible, the following operation is carried out: from all edges, the addition of which to the already existing set does not cause the appearance of a cycle in it, the edge of the minimum weight is selected and added to the already existing set. When there are no more such edges, the algorithm is complete. The subgraph of a given graph, containing all its vertices and the found set of edges, is its minimum weight spanning tree.

Implementation

First, let's sort the incoming list of edges by weight. Thus, taking the elements sequentially from the list, each time we will receive the edge with the minimum weight among the remaining ones.

Next, in the loop, we look for the index of the set that contains the beginning of the edge and the set that contains the end of the edge. If the set is not found, we get None.

  • If both sets are found and their indices are equal, we skip an edge, it will make a cycle.
  • If one of the edge points was found in some set, add the opposite point to this set and add the edge to the result.
  • If both sets are not found, add an edge to the result and add to the list of sets a set with two points of this edge
  • If both sets are found, but the indices are not equal, add an edge to the result and join the sets by indices using the union operation.
def kruskal(edges: list) -> list:
    # Sorting input edges by weight
    edges = sorted(edges, key=lambda item: item[2])
    # Adding first edge (with smallest weight) to result list and deleting it from input edges.
    result = [edges.pop(0)]
    # Adding to array first set of expanded points.
    array = [{result[0][0], result[0][1]}]

    # For each edge in sorted list (without deleted first)
    for edge in edges:
        # Looking for start point occurrences in expanded points sets and trying to get set index.
        start_connection = next(iter([i for i in range(len(array)) if edge[0] in array[i]]), None)
        # Looking for end point occurrences in expanded points sets and trying to get set index.
        end_connection = next(iter([i for i in range(len(array)) if edge[1] in array[i]]), None)

        # If edge makes cycle - skip it.
        if start_connection is not None and start_connection == end_connection:
            continue

        # Adding edge to result list.
        result.append(edge)
        # If edge first point found in expanded points set - add second edge point.
        if start_connection is not None:
            array[start_connection].add(edge[1])
        # If edge second point found in expanded points set - add first edge point.
        if end_connection is not None:
            array[end_connection].add(edge[0])

        # If edge is not connected with any chains - add new set of expanded points. (new chain)
        if start_connection is None and end_connection is None:
            array.append({edge[0], edge[1]})

        # If edge connects two chains - merge these chains. (union from two expanded points sets)
        if start_connection is not None and end_connection is not None:
            array.append(array[start_connection].union(array[end_connection]))
            array = [array[i] for i in range(len(array)) if i != start_connection and i != end_connection]

    return result

Result

[('a', 'd', 5), ('c', 'e', 5), ('d', 'f', 6), ('a', 'b', 7), ('b', 'e', 7), ('e', 'g', 9)]

Credits

Author: Danil Andreev.
Thanks for inspiration: Wikipedia.

def kruskal(edges: list) -> list:
"""
kruskal - function for finding the minimum spanning tree for weighted connected undirected graph.
:param edges: List of edges represented as tuple(a, b, weight)
:return: List of edges in the minimum spanning tree.
"""
# Sorting input edges by weight
edges = sorted(edges, key=lambda item: item[2])
# Adding first edge (with smallest weight) to result list and deleting it from input edges.
result = [edges.pop(0)]
# Adding to array first set of expanded points.
array = [{result[0][0], result[0][1]}]
# For each edge in sorted list (without deleted first)
for edge in edges:
# Looking for start point occurrences in expanded points sets and trying to get set index.
start_connection = next(iter([i for i in range(len(array)) if edge[0] in array[i]]), None)
# Looking for end point occurrences in expanded points sets and trying to get set index.
end_connection = next(iter([i for i in range(len(array)) if edge[1] in array[i]]), None)
# If edge makes cycle - skip it.
if start_connection is not None and start_connection == end_connection:
continue
# Adding edge to result list.
result.append(edge)
# If edge first point found in expanded points set - add second edge point.
if start_connection is not None:
array[start_connection].add(edge[1])
# If edge second point found in expanded points set - add first edge point.
if end_connection is not None:
array[end_connection].add(edge[0])
# If edge is not connected with any chains - add new set of expanded points. (new chain)
if start_connection is None and end_connection is None:
array.append({edge[0], edge[1]})
# If edge connects two chains - merge these chains. (union from two expanded points sets)
if start_connection is not None and end_connection is not None:
array.append(array[start_connection].union(array[end_connection]))
array = [array[i] for i in range(len(array)) if i != start_connection and i != end_connection]
return result
from kruskal import kruskal
# Creating list of graph edges with their weights.
EDGES = [
("a", "b", 7),
("a", "d", 5),
("d", "b", 9),
("b", "c", 8),
("c", "e", 5),
("b", "e", 7),
("d", "e", 15),
("d", "f", 6),
("f", "e", 8),
("e", "g", 9),
("f", "g", 11)
]
# Printing minimal spanning tree for input graph.
print(kruskal(EDGES))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment