Back to Repositories

Testing Prim's Minimum Spanning Tree Algorithm Implementation in TheAlgorithms/Python

This test suite validates the implementation of Prim’s Minimum Spanning Tree algorithm in Python. It focuses on verifying the correctness of the algorithm’s output by testing graph edge selection and weight calculations.

Test Coverage Overview

The test coverage focuses on validating Prim’s MST algorithm with a specific graph configuration containing 9 nodes and 14 edges. The test verifies:

Correct edge selection in the minimum spanning tree
Proper handling of undirected graph connections
Accurate weight calculations
Edge reversibility validation

Implementation Analysis

The testing approach uses a predefined graph structure with known expected outcomes to verify the algorithm’s correctness. It implements bidirectional edge creation using defaultdict for adjacency list representation and validates results by checking both forward and reverse edge configurations.

Technical Details

Key technical components include:

Python’s collections.defaultdict for graph representation
Custom edge validation logic
Tuple-based edge comparison
Assertion-based result verification

Best Practices Demonstrated

The test demonstrates several testing best practices:

Clear test data setup and initialization
Comprehensive edge case handling
Explicit expected results definition
Flexible result validation supporting bidirectional edges

thealgorithms/python

graphs/tests/test_min_spanning_tree_prim.py

            
from collections import defaultdict

from graphs.minimum_spanning_tree_prims import prisms_algorithm as mst


def test_prim_successful_result():
    num_nodes, num_edges = 9, 14  # noqa: F841
    edges = [
        [0, 1, 4],
        [0, 7, 8],
        [1, 2, 8],
        [7, 8, 7],
        [7, 6, 1],
        [2, 8, 2],
        [8, 6, 6],
        [2, 3, 7],
        [2, 5, 4],
        [6, 5, 2],
        [3, 5, 14],
        [3, 4, 9],
        [5, 4, 10],
        [1, 7, 11],
    ]

    adjacency = defaultdict(list)
    for node1, node2, cost in edges:
        adjacency[node1].append([node2, cost])
        adjacency[node2].append([node1, cost])

    result = mst(adjacency)

    expected = [
        [7, 6, 1],
        [2, 8, 2],
        [6, 5, 2],
        [0, 1, 4],
        [2, 5, 4],
        [2, 3, 7],
        [0, 7, 8],
        [3, 4, 9],
    ]

    for answer in expected:
        edge = tuple(answer[:2])
        reverse = tuple(edge[::-1])
        assert edge in result or reverse in result