Category: Python Coding Test

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:

• GeeksforGeeks – Minimum Spanning Tree
• Khan Academy – Prim’s Algorithm

1. What is a Minimum Spanning Tree?

A Minimum Spanning Tree (MST) is a subgraph of a connected graph that includes all vertices while minimizing the sum of the weights of the edges. In other words, the Minimum Spanning Tree is the process of finding a tree that connects all vertices in the given graph with the least total cost while avoiding cycles.

2. Problem Description

The following is the Minimum Spanning Tree problem:

Given n cities and m roads, find the minimum cost to connect all the cities with roads.

Input format: The first line contains two integers n (the number of cities) and m (the number of roads). The next m lines contain three integers a, b, c representing that the cost of the road connecting city a and city b is c.

3. Approach

To solve the Minimum Spanning Tree problem, two algorithms are commonly used:

• Prim’s Algorithm
• Kruskal’s Algorithm

In this article, we will use Kruskal’s algorithm to solve the problem.

3.1 Kruskal’s Algorithm

Kruskal’s algorithm proceeds in the following steps:

1. Sort all the edges in ascending order by weight (cost).
2. Starting from the smallest edge, select it. If the selected edge does not form a cycle, include it in the MST.
3. Repeat step 2 until all edges have been examined.

4. Algorithm Implementation

Now, let’s start implementing Kruskal’s algorithm in Python to solve the above problem.

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)

        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1
    

4.1 Input and Edge Sorting

We will take the number of cities and road information as input, and sort the edges by weight.

import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    edges = []

    for _ in range(m):
        a, b, c = map(int, input().split())
        edges.append((c, a, b))

    edges.sort()  # Sort by ascending weight
    

4.2 Applying Kruskal's Algorithm

We examine the sorted edges one by one to construct the MST.

    ds = DisjointSet(n)
    mst_cost = 0

    for cost, a, b in edges:
        if ds.find(a) != ds.find(b):  # Check for cycles
            ds.union(a, b)
            mst_cost += cost

    print(mst_cost)  # Output the minimum spanning tree cost
if __name__ == "__main__":
    main()
    

5. Conclusion

In this article, we explored the concept of the Minimum Spanning Tree and how to solve the problem using Kruskal's algorithm. I hope you can develop the ability to analyze and solve given problems in your own way.

Hello! In this article, we will discuss the “Minimum Cost Finding” algorithm problem based on the pathfinding problem. Coding tests are one of the essential elements to prepare for employment in IT companies. To develop problem-solving strategies, understand algorithms, and improve implementation skills, we will solve the problem step by step through this article.

Problem Description

The problem of finding the minimum cost is about finding the minimum cost from a starting point to a destination in a given graph.
Let’s take the following graph as an example.

    1 --> 2 (cost: 4)
    1 --> 3 (cost: 2)
    2 --> 3 (cost: 1)
    2 --> 4 (cost: 5)
    3 --> 4 (cost: 8)
    

Find the minimum cost to get from node 1 to node 4 in the graph above.

Input Format

• The first line contains the number of nodes N and the number of edges M (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10^4).
• From the second line onwards, M lines provide the information of each edge in the format “u v c” (u, v are node numbers, c is the cost).
• The last line contains the starting node and the destination node.

Output Format

Print the minimum cost to get from the starting node to the target node. If there is no path, print -1.

Problem Approach

This problem is a typical problem of finding the shortest path in a graph, and we will use Dijkstra’s algorithm. Dijkstra’s algorithm is very efficient for finding the shortest path in weighted graphs. We will implement the algorithm through the following steps.

1. Input: Enter node and edge information.
2. Graph Structuring: Represent the graph as an adjacency list based on the input edge information.
3. Priority Queue Initialization: Set up a priority queue to manage the costs of adjacent nodes from the current node.
4. Perform Dijkstra’s Algorithm: Extract the node with the lowest cost from the queue and update the costs to the adjacent nodes.
5. Output the Result: Verify if the destination is reachable and output the minimum cost.

Code Implementation

import sys
import heapq

def dijkstra(start, goal, graph, n):
    # Initialize cost table
    INF = float('inf')
    distance = [INF] * (n + 1)
    distance[start] = 0
    queue = []
    heapq.heappush(queue, (0, start))  # (cost, node)

    while queue:
        current_cost, current_node = heapq.heappop(queue)

        # Ignore if the current cost is greater than the existing minimum cost
        if current_cost > distance[current_node]:
            continue

        for neighbor, cost in graph[current_node]:
            new_cost = current_cost + cost

            # Update the cost of adjacent nodes
            if new_cost < distance[neighbor]:
                distance[neighbor] = new_cost
                heapq.heappush(queue, (new_cost, neighbor))

    return distance[goal] if distance[goal] != INF else -1

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().strip().split())
    graph = [[] for _ in range(n + 1)]

    for _ in range(m):
        u, v, c = map(int, sys.stdin.readline().strip().split())
        graph[u].append((v, c))

    start, goal = map(int, sys.stdin.readline().strip().split())
    result = dijkstra(start, goal, graph, n)
    print(result)

Code Explanation

The above code implements Dijkstra's algorithm in Python. It takes the starting node, destination node, graph structure, and total number of nodes as input parameters.

- Cost Table Initialization: Initializes a list with infinity for the number of nodes. Sets the cost of the starting node to 0.

- Using a Priority Queue: Utilizes Python's heap feature, heapq, to process the node with the lowest cost.

- Updating Adjacent Nodes: Iterates through adjacent nodes to update them with the optimal cost.

Execution Example

Input
4 5
1 2 4
1 3 2
2 3 1
2 4 5
3 4 8
1 4

Output
6

This example shows that the minimum cost from node 1 to node 4 is 6.

Finding Minimum Cost in a Grid Graph

The above problem is a general graph, but there is also the problem of finding the minimum cost in a 2D grid. In the following sections, we will explain how to find the minimum cost using a 2D array.

Problem 2: Finding Minimum Cost in a Grid

In the given 2D array, you need to find the minimum cost to move from the starting point (0, 0) to the destination point (n-1, m-1). The value of each cell represents the cost of moving. You can only move up, down, left, or right.

Input Format

3 3
1 2 3
4 1 2
1 5 3

The given array is as follows:

1  2  3
4  1  2
1  5  3

Output Format

Print the minimum cost to get from the starting point to the target point.

Problem Approach

This problem can be solved using dynamic programming. The minimum cost is calculated at each cell by updating the minimum cost from the previously reachable cells.

Code Implementation

def min_cost_in_grid(grid):
    n = len(grid)
    m = len(grid[0])
    dp = [[0] * m for _ in range(n)]
    dp[0][0] = grid[0][0]
    
    for i in range(n):
        for j in range(m):
            if i == 0 and j == 0:
                continue
            up = dp[i-1][j] if i > 0 else float('inf')
            left = dp[i][j-1] if j > 0 else float('inf')
            dp[i][j] = grid[i][j] + min(up, left)

    return dp[n-1][m-1]

if __name__ == '__main__':
    grid = [
        [1, 2, 3],
        [4, 1, 2],
        [1, 5, 3]
    ]
    result = min_cost_in_grid(grid)
    print(result)

Code Explanation

The above code shows how to find the minimum cost in a 2D array. It stores the minimum cost for each cell in a dp array and sets the current cell's minimum cost by comparing costs coming from the left or above.

Execution Example

Output
8

This example shows that the minimum cost to go from (0, 0) to (2, 2) is 8.

Conclusion

In this article, we explored various approaches and algorithms to solve the minimum cost problem. I hope the insights from the graph problem using Dijkstra's algorithm and the grid problem using dynamic programming will help you prepare for coding tests. Challenge yourself with various problems to enhance your problem-solving skills!

If you have any questions or additional inquiries during the process, please leave a comment. Thank you!

In this article, we will explore one of the problems related to finding the ‘Lowest Common Ancestor (LCA)’ called ‘Finding the Lowest Common Ancestor 2’. This problem involves finding the lowest common ancestor of two nodes in a specific tree structure, particularly in a binary tree. The LCA problem is a fundamental problem associated with tree traversal and manipulation, frequently appearing in coding interviews and algorithm competitions.

Problem Description

Given a binary tree, we need to find the lowest common ancestor of two nodes u and v.
A binary tree can have a maximum of 2 children for each node, starting from the root node, and
each node has a unique value.

Input Format

• First line: Number of nodes n (1 ≤ n ≤ 100,000)
• Second line: Tree structure (given parent nodes and child nodes)
• Third line: Two nodes u, v

Output Format

Output the lowest common ancestor of nodes u and v.

Example

Input:
7
1 2
1 3
2 4
2 5
3 6
3 7
4 5

Output:
2

Approach to the Problem

To solve this problem, we first need to construct the tree. The tree can be represented as an array or linked list, but
using a linked list is more efficient. Then, we will record the depth of each node through DFS (Depth First Search) and
store the parent nodes to easily find the LCA later.

Tree Construction

Based on the given edge information, we will establish the parent-child relationships for the nodes.
We will use Python’s dictionary to store the parent-child relationships.

from collections import defaultdict

def build_tree(edges):
    tree = defaultdict(list)
    for parent, child in edges:
        tree[parent].append(child)
    return tree

Storing Depth and Parent Node Information via DFS

def dfs(tree, node, parent, depth, depths, parents):
    depths[node] = depth
    parents[node] = parent
    for child in tree[node]:
        if child != parent:
            dfs(tree, child, node, depth + 1, depths, parents)

Implementing the LCA Function

After aligning the positions of the two nodes based on depth, we proceed upward along their parents until
both nodes converge at the same node.

def lca(u, v, depths, parents):
    # Aligning Depths
    if depths[u] < depths[v]:
        u, v = v, u

    while depths[u] > depths[v]:
        u = parents[u]

    while u != v:
        u = parents[u]
        v = parents[v]

    return u

Complete Code

def main():
    n = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    u, v = map(int, input().split())

    tree = build_tree(edges)
    depths = {}
    parents = {}

    # Collecting depth and parent information via DFS
    dfs(tree, 1, -1, 0, depths, parents)

    # Finding the lowest common ancestor
    ancestor = lca(u, v, depths, parents)
    print(ancestor)

if __name__ == "__main__":
    main()

Time Complexity

The time complexity of the above algorithm is O(n). This is because each node is visited once during the tree construction and traversal.

Conclusion

The ‘Finding the Lowest Common Ancestor 2’ problem is helpful for understanding the basics of searching and manipulating binary trees,
and it is a practical algorithm. Through the process of solving this problem, one can gain a deep understanding of tree structures and the concept of DFS.
This algorithm can be extended to various other problems and is also very useful in the application of other data structures.