Bài tập Python từ cơ bản đến nâng cao – Phần 9

Dưới đây là 10 bài tập thuật toán nâng cao hơn, tập trung vào đồ thị, quy hoạch động và tối ưu hóa.

Bài 78: Thuật toán Floyd-Warshall (Đường đi ngắn nhất giữa mọi cặp đỉnh)

Đề bài: Nhập vào một ma trận trọng số của đồ thị có hướng và tìm đường đi ngắn nhất giữa mọi cặp đỉnh bằng thuật toán Floyd-Warshall.

Giải:

INF = float('inf')

def floyd_warshall(graph):
    n = len(graph)
    dist = 
 for row in graph]
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

graph = [
    [0, 3, INF, INF, INF, INF],
    [INF, 0, 1, INF, INF, INF],
    [INF, INF, 0, 7, INF, 2],
    [INF, INF, INF, 0, 2, 3],
    [INF, INF, INF, INF, 0, INF],
    [INF, INF, INF, INF, 1, 0]
]

print("Ma trận khoảng cách ngắn nhất:")
for row in floyd_warshall(graph):
    print(row)

Bài 79: Thuật toán Kruskal (Cây khung nhỏ nhất – MST)

Đề bài: Nhập vào một đồ thị vô hướng có trọng số và tìm cây khung nhỏ nhất bằng thuật toán Kruskal.

Giải:

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

    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
            else:
                self.parent[root_u] = root_v
                if self.rank[root_u] == self.rank[root_v]:
                    self.rank[root_v] += 1

def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])
    ds = DisjointSet(n)
    mst = []
    
    for u, v, weight in edges:
        if ds.find(u) != ds.find(v):
            ds.union(u, v)
            mst.append((u, v, weight))
    
    return mst

edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
n = 4  # Số đỉnh
print("Cây khung nhỏ nhất:", kruskal(n, edges))

Bài 80: Thuật toán Prim (Cây khung nhỏ nhất – MST)

Đề bài: Tìm cây khung nhỏ nhất của đồ thị bằng thuật toán Prim.

Giải:

import heapq

def prim(graph, start):
    mst = []
    visited = set()
    pq = [(0, start, -1)]

    while pq:
        weight, u, parent = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        if parent != -1:
            mst.append((parent, u, weight))

        for v, w in graph[u]:
            if v not in visited:
                heapq.heappush(pq, (w, v, u))

    return mst

graph = {
    0: [(1, 10), (2, 6), (3, 5)],
    1: [(0, 10), (3, 15)],
    2: [(0, 6), (3, 4)],
    3: [(0, 5), (1, 15), (2, 4)]
}
print("Cây khung nhỏ nhất:", prim(graph, 0))

Bài 81: Đếm thành phần liên thông trong đồ thị

Đề bài: Cho một đồ thị vô hướng, đếm số thành phần liên thông.

Giải:

def dfs(graph, node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

def count_connected_components(graph):
    visited = set()
    count = 0
    for node in graph:
        if node not in visited:
            count += 1
            dfs(graph, node, visited)
    return count

graph = {
    0: [1, 2], 1: [0], 2: [0], 3: [4], 4: [3]
}
print("Số thành phần liên thông:", count_connected_components(graph))

Bài 82: Tìm đường đi Euler trong đồ thị

Đề bài: Kiểm tra xem đồ thị có chứa đường đi Euler hay không.

Giải:

def has_eulerian_path(graph):
    odd_degree = sum(1 for node in graph if len(graph[node]) % 2 == 1)
    return odd_degree == 0 or odd_degree == 2

graph = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}
print("Có đường đi Euler" if has_eulerian_path(graph) else "Không có đường đi Euler")

Bài 83: Tô màu đồ thị

Đề bài: Tô màu các đỉnh của đồ thị sao cho hai đỉnh kề nhau không cùng màu.

Giải:

def graph_coloring(graph):
    colors = {}
    for node in graph:
        available_colors = {0, 1, 2, 3} - {colors.get(neigh) for neigh in graph[node] if neigh in colors}
        colors[node] = min(available_colors)
    return colors

graph = {0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 3], 3: [1, 2]}
print("Kết quả tô màu:", graph_coloring(graph))

Bài 84: Đếm số đường đi từ đỉnh A đến B trong đồ thị

Đề bài: Cho một đồ thị, tìm số đường đi từ đỉnh A đến B.

Giải:

def count_paths(graph, start, end, visited):
    if start == end:
        return 1
    visited.add(start)
    count = sum(count_paths(graph, neighbor, end, visited.copy()) for neighbor in graph[start] if neighbor not in visited)
    return count

graph = {0: [1, 2], 1: [2, 3], 2: [3], 3: []}
print("Số đường đi từ 0 đến 3:", count_paths(graph, 0, 3, set()))