Cài đặt thuật toán Topological Sorting trong lập trình

Sắp xếp topo (Topological Sorting) là một kỹ thuật quan trọng trong lập trình và khoa học máy tính, đặc biệt là trong việc xử lý các đồ thị có hướng và không có chu trình. Kỹ thuật này thường được sử dụng để sắp xếp các tác vụ trong các hệ thống như lập lịch trình công việc, phân tích chuỗi phụ thuộc và nhiều ứng dụng khác. Bài viết sau đây sẽ đi sâu vào việc cài đặt thuật toán Topological Sorting trong lập trình.

Khái niệm Sắp Xếp Topo

Sắp xếp topo là một cách sắp xếp các đỉnh của đồ thị sao cho với mỗi cung (u, v), đỉnh u luôn đứng trước đỉnh v trong danh sách sắp xếp. Do đó, sắp xếp topo chỉ tồn tại trong các đồ thị có hướng và không có chu trình (DAG - Directed Acyclic Graph).

Phương Pháp Tiến Hành Sắp Xếp Topo

Có nhiều phương pháp để thực hiện sắp xếp topo, nhưng hai trong số các thuật toán phổ biến nhất là DFS (Depth First Search) và Kahn’s Algorithm.

Sử Dụng DFS (Depth First Search)

1. Bước khởi tạo: Khởi tạo một danh sách trống để lưu kết quả sắp xếp và một mảng đánh dấu để theo dõi các đỉnh đã được thăm.
2. DFS đối với mỗi đỉnh chưa được thăm:
   • Đánh dấu đỉnh hiện tại là đã thăm.
   • Đệ quy cho các đỉnh kề.
   • Thêm đỉnh vào danh sách kết quả sau khi đã xử lý tất cả các đỉnh kề của nó.
3. Kết quả: Danh sách kết quả sẽ chứa các đỉnh được sắp xếp theo thứ tự topo khi kết thúc quá trình DFS.

Mã nguồn Python sử dụng DFS:

def topological_sort_util(v, visited, stack, graph):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            topological_sort_util(i, visited, stack, graph)
    stack.append(v)

def topological_sort(graph, num_vertices):
    visited = [False] * num_vertices
    stack = []
    for i in range(num_vertices):
        if not visited[i]:
            topological_sort_util(i, visited, stack, graph)
    return stack[::-1]  # Đảo ngược ngăn xếp để có thứ tự topo

# Ví dụ sử dụng
graph = [[2, 3], [3, 4], [], [5], [], []]
num_vertices = 6
print(topological_sort(graph, num_vertices))  # Kết quả: [1, 0, 2, 3, 5, 4]

Sử Dụng Kahn’s Algorithm

1. Tính toán bậc vào của mỗi đỉnh: Khởi tạo một mảng để lưu trữ bậc vào (in-degree) của mỗi đỉnh.
2. Sử dụng hàng đợi (queue) để lưu trữ các đỉnh có bậc vào bằng 0.
3. Xử lý hàng đợi:
   • Lấy đỉnh từ hàng đợi
   • Thêm đỉnh đó vào danh sách kết quả
   • Giảm bậc vào của tất cả các đỉnh kề
   • Nếu bậc vào của đỉnh kề giảm về 0, thêm nó vào hàng đợi
4. Kết quả: Thu được danh sách các đỉnh sắp xếp theo thứ tự topo khi hàng đợi rỗng.

Mã nguồn Python sử dụng Kahn’s Algorithm:

from collections import deque

def topological_sort_kahn(graph, num_vertices):
    in_degree = [0] * num_vertices
    for i in range(num_vertices):
        for j in graph[i]:
            in_degree[j] += 1

    queue = deque([i for i in range(num_vertices) if in_degree[i] == 0])
    topo_order = []

    while queue:
        v = queue.popleft()
        topo_order.append(v)
        for neighbor in graph[v]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(topo_order) == num_vertices:
        return topo_order
    else:
        return []  # Đồ thị có chu trình.

# Ví dụ sử dụng
graph = [[2, 3], [3, 4], [], [5], [], []]
num_vertices = 6
print(topological_sort_kahn(graph, num_vertices))  # Kết quả: [0, 1, 2, 3, 4, 5]

Kết luận

Việc sắp xếp topo là một kỹ thuật hữu ích và quan trọng trong nhiều bài toán và ứng dụng khác nhau. Sử dụng các thuật toán DFS và Kahn’s Algorithm, bạn có thể dễ dàng cài đặt sắp xếp topo trong lập trình. Với sự hiểu biết sâu hơn về đồ thị và các thuật toán xử lý, bạn có thể phát triển nhiều ứng dụng hiệu quả hơn trong tương lai.