python coding test course, finding the minimum spanning tree

Hello! Today we will learn about an important concept in graph theory called Minimum Spanning Tree (MST). A Minimum Spanning Tree is a tree that includes all connected vertices while minimizing the total weight of the edges. This concept is utilized in various fields such as network design, road connectivity, and clustering.

Problem Description

The problem is as follows:

Write a program to find the Minimum Spanning Tree of a given undirected weighted graph. The graph is given within the constraints 1 ≤ V ≤ 1000 (number of vertices) and 1 ≤ E ≤ 10000 (number of edges), with all edge weights in the range 1 ≤ w ≤ 1000.

Problem Solving Approach

There are several algorithms to find the Minimum Spanning Tree, but the two most commonly used are Prim’s Algorithm and Kruskal’s Algorithm. Here, we will describe how to solve the problem using Prim’s Algorithm.

Overview of Prim’s Algorithm

Prim’s Algorithm is an algorithm that proceeds by always selecting the edge with the minimum weight, following these steps:

  1. Select a starting vertex. (Any vertex can be chosen as the starting point.)
  2. Select the edge with the smallest weight among the edges connected to the currently selected vertex.
  3. Add the vertex connected by the selected edge to the tree.
  4. Repeat steps 2 and 3 until all vertices are included.

Time Complexity of Prim’s Algorithm

The time complexity of Prim’s Algorithm depends on the data structure used. Using a heap (priority queue) results in a complexity of O(E log V), while using an adjacency matrix results in a complexity of O(V2). Generally, using a heap is more efficient.

Implementation

Now let’s implement Prim’s Algorithm. Below is the Python code:


import heapq  # Importing to use heap

def prim(graph, start):
    mst = []  # List for the Minimum Spanning Tree
    visited = set()  # Set of visited vertices
    min_heap = [(0, start)]  # Initializing heap (weight, vertex)

    total_weight = 0  # Total weight

    while min_heap:
        weight, vertex = heapq.heappop(min_heap)  # Selecting edge with minimum weight
        if vertex not in visited:
            visited.add(vertex)  # Mark as visited
            total_weight += weight  # Summing weights
            mst.append((weight, vertex))

            for next_vertex, next_weight in graph[vertex].items():
                if next_vertex not in visited:
                    heapq.heappush(min_heap, (next_weight, next_vertex))  # Adding to heap

    return mst, total_weight  # Returning Minimum Spanning Tree and total weight

# Graph definition (adjacency list)
graph = {
    1: {2: 3, 3: 1},
    2: {1: 3, 3: 1, 4: 6},
    3: {1: 1, 2: 1, 4: 5},
    4: {2: 6, 3: 5}
}

mst, total_weight = prim(graph, 1)
print("Minimum Spanning Tree:", mst)
print("Total Weight:", total_weight)

Code Explanation

The above code defines a function called prim. This function takes the graph and the starting vertex as arguments and returns the Minimum Spanning Tree along with its total weight.

  • min_heap: Manages the currently selectable edges using a heap.
  • visited: Tracks the selected vertices to prevent duplicates.
  • After selecting the minimum weight edge from the heap, it adds the corresponding vertex to the tree and adds the connected vertices to the heap.

Running Test Cases

When you run the code above, you will get the following results:


Minimum Spanning Tree: [(0, 1), (1, 3), (1, 2)]
Total Weight: 2

Here, the Minimum Spanning Tree includes vertices 1, 2, and 3, with a total weight of 2.

Complex Example

You can also find the Minimum Spanning Tree for more complex graphs using the same method. For example, consider a graph with multiple vertices and edges:


# Defining a complex graph
complex_graph = {
    'A': {'B': 4, 'H': 8},
    'B': {'A': 4, 'C': 8, 'H': 11},
    'C': {'B': 8, 'D': 7, 'F': 4, 'I': 2},
    'D': {'C': 7, 'E': 9, 'F': 14},
    'E': {'D': 9, 'F': 10},
    'F': {'C': 4, 'D': 14, 'E': 10, 'G': 2},
    'G': {'F': 2, 'H': 1, 'I': 6},
    'H': {'A': 8, 'B': 11, 'G': 1},
    'I': {'C': 2, 'G': 6}
}

mst_complex, total_weight_complex = prim(complex_graph, 'A')
print("Minimum Spanning Tree of the complex graph:", mst_complex)
print("Total Weight:", total_weight_complex)

Result Interpretation

In this complex graph, multiple selections are needed to find the Minimum Spanning Tree. Prim’s Algorithm is effective in choosing optimal edges to construct the tree. The execution result displays the final Minimum Spanning Tree and its total weight.

Conclusion

The Minimum Spanning Tree plays an important role in network design and optimization problems. Through this tutorial, we have implemented Prim’s Algorithm in Python and applied it to real problems. Verifying the algorithm’s accuracy through various test cases is also an important process. I hope this helps you prepare for coding tests through problem-solving using algorithms!

Additional Learning Resources

Besides Prim’s Algorithm, it’s also beneficial to explore other methods like Kruskal’s Algorithm. Here are some resources to help understand the algorithms better: