{"id":33776,"date":"2024-11-01T09:20:15","date_gmt":"2024-11-01T09:20:15","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33776"},"modified":"2024-11-01T11:46:44","modified_gmt":"2024-11-01T11:46:44","slug":"python-coding-test-course-finding-the-minimum-spanning-tree","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33776\/","title":{"rendered":"python coding test course, finding the minimum spanning tree"},"content":{"rendered":"

<\/p>\n

Hello! Today we will learn about an important concept in graph theory called Minimum Spanning Tree (MST)<\/strong>. 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.<\/p>\n

Problem Description<\/h2>\n

The problem is as follows:<\/p>\n

\n

Write a program to find the Minimum Spanning Tree of a given undirected weighted graph<\/strong>. The graph is given within the constraints 1 \u2264 V \u2264 1000<\/code> (number of vertices) and 1 \u2264 E \u2264 10000<\/code> (number of edges), with all edge weights in the range 1 \u2264 w \u2264 1000<\/code>.<\/p>\n<\/blockquote>\n

Problem Solving Approach<\/h2>\n

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

Overview of Prim’s Algorithm<\/h3>\n

Prim’s Algorithm is an algorithm that proceeds by always selecting the edge with the minimum weight, following these steps:<\/p>\n

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

    Time Complexity of Prim’s Algorithm<\/h3>\n

    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)<\/code>, while using an adjacency matrix results in a complexity of O(V2<\/sup>)<\/code>. Generally, using a heap is more efficient.<\/p>\n

    Implementation<\/h2>\n

    Now let’s implement Prim’s Algorithm. Below is the Python code:<\/p>\n

    \nimport heapq  # Importing to use heap\n\ndef prim(graph, start):\n    mst = []  # List for the Minimum Spanning Tree\n    visited = set()  # Set of visited vertices\n    min_heap = [(0, start)]  # Initializing heap (weight, vertex)\n\n    total_weight = 0  # Total weight\n\n    while min_heap:\n        weight, vertex = heapq.heappop(min_heap)  # Selecting edge with minimum weight\n        if vertex not in visited:\n            visited.add(vertex)  # Mark as visited\n            total_weight += weight  # Summing weights\n            mst.append((weight, vertex))\n\n            for next_vertex, next_weight in graph[vertex].items():\n                if next_vertex not in visited:\n                    heapq.heappush(min_heap, (next_weight, next_vertex))  # Adding to heap\n\n    return mst, total_weight  # Returning Minimum Spanning Tree and total weight\n\n# Graph definition (adjacency list)\ngraph = {\n    1: {2: 3, 3: 1},\n    2: {1: 3, 3: 1, 4: 6},\n    3: {1: 1, 2: 1, 4: 5},\n    4: {2: 6, 3: 5}\n}\n\nmst, total_weight = prim(graph, 1)\nprint(\"Minimum Spanning Tree:\", mst)\nprint(\"Total Weight:\", total_weight)\n    <\/code><\/pre>\n
    Code Explanation<\/h3>\n
    The above code defines a function called prim<\/code>. This function takes the graph and the starting vertex as arguments and returns the Minimum Spanning Tree along with its total weight.<\/p>\n