Ngày 13 của #30DaysOfCode: Khám Phá Đồ Thị và Thuật Toán

Giới thiệu

Ngày 20 tháng 9 năm 2025 là một ngày đặc biệt trong hành trình học lập trình của tôi. Hôm nay, tôi đã bắt đầu ngày mới bằng việc tập gym, điều này giúp tôi tỉnh táo và sẵn sàng cho những thử thách mới trong lập trình. Trong bài viết này, tôi sẽ chia sẻ những gì tôi đã học được về đồ thị, các thuật toán tìm kiếm BFS và DFS, cùng với một số mẹo và thủ thuật hữu ích cho những ai đang theo đuổi con đường lập trình.

Nội dung chính

1. Đồ thị: Khái niệm và các loại

Đồ thị là một trong những cấu trúc dữ liệu quan trọng trong lập trình. Nó được sử dụng để mô hình hóa các mối quan hệ giữa các đối tượng. Có hai loại đồ thị chính:

• Đồ thị có hướng: Là đồ thị mà các cạnh có hướng, tức là từ một đỉnh này đến một đỉnh khác.
• Đồ thị vô hướng: Là đồ thị mà các cạnh không có hướng, tức là không phân biệt được chiều đi của cạnh.

1.1. Cách biểu diễn đồ thị

Có nhiều cách để biểu diễn đồ thị trong lập trình:

• Ma trận kề: Sử dụng một ma trận 2 chiều để biểu diễn các đỉnh và cạnh.
• Danh sách kề: Sử dụng một danh sách để lưu trữ các đỉnh và các cạnh liên quan.

# Ví dụ về danh sách kề trong Python
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}

2. Các thuật toán tìm kiếm trong đồ thị

Hai thuật toán phổ biến nhất để tìm kiếm trong đồ thị là Breadth-First Search (BFS) và Depth-First Search (DFS).

2.1. Thuật toán BFS

BFS là thuật toán tìm kiếm theo chiều rộng, hoạt động bằng cách khám phá tất cả các đỉnh kề trước khi di chuyển đến các đỉnh sâu hơn.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(set(graph[vertex]) - visited)
    return visited

2.2. Thuật toán DFS

DFS là thuật toán tìm kiếm theo chiều sâu, hoạt động bằng cách khám phá một nhánh của đồ thị cho đến khi không còn đỉnh nào để khám phá.

def dfs(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    visited.add(vertex)
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

3. Thực hành giải bài tập

Hôm nay, tôi đã thực hiện hai bài tập trên LeetCode liên quan đến đồ thị. Một trong số đó là bài toán tìm đường đi ngắn nhất, một bài toán phổ biến trong lập trình.

4. Mẹo học tập hiệu quả

• Tăng dần số lượng bài tập: Tôi nhận ra rằng để cải thiện kỹ năng lập trình của mình, tôi cần phải tăng dần số lượng bài tập từ 1 lên 2-3 bài mỗi ngày. Điều này giúp tôi tiếp thu kiến thức nhanh hơn.
• Thực hành và thử nghiệm: Đừng chỉ đọc lý thuyết, hãy thực hành và thử nghiệm với mã nguồn của bạn. Hãy tạo ra những bài tập cho riêng mình để kiểm tra kiến thức.

5. Lời khuyên và lưu ý

• Đừng ngại sai lầm: Mỗi lỗi là một bài học quý giá trong hành trình lập trình của bạn.
• Dành thời gian cho bản thân: Đôi khi, một giấc ngủ ngắn cũng giúp bạn làm việc hiệu quả hơn. Hôm nay, tôi đã dành thời gian để nghỉ ngơi và sẽ cố gắng hoàn thành công việc vào ngày mai.

Kết luận

Ngày hôm nay đã diễn ra với nhiều hoạt động và học hỏi thú vị. Việc hiểu rõ về đồ thị và các thuật toán tìm kiếm sẽ giúp tôi trong nhiều dự án tương lai. Hãy cùng tôi tiếp tục hành trình này trong những ngày tới!

Câu hỏi thường gặp (FAQ)

1. Đồ thị là gì?
Đồ thị là một cấu trúc dữ liệu dùng để biểu diễn các mối quan hệ giữa các đối tượng.

2. BFS và DFS khác nhau như thế nào?
BFS tìm kiếm theo chiều rộng, còn DFS tìm kiếm theo chiều sâu.

3. Tôi nên bắt đầu từ đâu nếu muốn học về đồ thị?
Hãy bắt đầu từ lý thuyết cơ bản và thực hành với các bài tập đơn giản trước khi tiến tới các thuật toán phức tạp hơn.