Trong thế giới lập trình, nhiều vấn đề phức tạp có thể được giải quyết hiệu quả qua mô hình hóa dưới dạng đồ thị và ứng dụng các thuật toán đồ thị phù hợp. Ví dụ như các mạng lưới đường bộ, hệ thống vận chuyển thành phố, hay các cấu trúc quan hệ giữa các đối tượng. Tuy nhiên, không phải lúc nào cũng dễ dàng nhận ra rằng vấn đề bạn đang gặp phải có thể được mô hình hóa bằng đồ thị. Chính vì điều đó, trong bài viết này, chúng ta sẽ tìm hiểu những khái niệm cơ bản về đồ thị và các thuật toán thường được sử dụng để khai thác tối đa sức mạnh của đồ thị trong các bài toán thực tiễn.

Các Khái Niệm Cơ Bản Về Đồ Thị

Đồ Thị (Graph)

Một đồ thị (Graph) bao gồm các nút (node) và cạnh (edges). Trong loạt bài này, ta sử dụng biến n để đại diện cho số lượng nút và m để đại diện cho số lượng cạnh. Các nút thường được đánh số từ 1 đến n. Một đồ thị với 5 nút và 7 cạnh sẽ được mô tả như sau.

Đường Dẫn (Path)

Một đường dẫn (Path) là chuỗi các cạnh nối từ nút a đến nút b. Độ dài của một đường dẫn là tổng số cạnh trong nó. Một ví dụ cụ thể là đường dẫn từ nút 1 đến nút 5 qua các nút 3 và 4.

Chu Kỳ (Cycle)

Một đường dẫn được gọi là chu kỳ (cycle) nếu nút đầu tiên và nút cuối cùng giống nhau, tức là nó tạo thành một vòng kín. Ví dụ như đường dẫn 1 -> 3 -> 4 -> 1.

Khái Niệm Liên Thông (Connectivity)

Đồ thị được gọi là liên thông nếu cho bất kỳ hai nút nào trong đồ thị, luôn tồn tại một đường dẫn nối giữa chúng. Ngược lại, đồ thị không liên thông sẽ có ít nhất một cặp nút không có đường dẫn nối. Mỗi đồ thị liên thông được chia thành các thành phần liên thông (components).

Cây (Tree)

Cây là một dạng đồ thị liên thông đặc biệt có n nút và n - 1 cạnh. Đặc điểm chính là nó không có chu kỳ. Mỗi cặp nút trong cây chỉ có duy nhất một đường dẫn nối nhau.

Đồ Thị Có Hướng (Directed Graph)

Một đồ thị được gọi là có hướng nếu các cạnh chỉ có thể di chuyển theo một chiều. Chẳng hạn, từ nút 3 đến 5 nhưng không thể đi ngược lại.

Đồ Thị Có Trọng Số (Weighted Graph)

Trong một đồ thị có trọng số, mỗi cạnh đi kèm với một trọng số, có thể là độ dài hay chi phí di chuyển qua cạnh đó. Để tính toán độ dài hoặc chi phí của một đường dẫn trong đồ thị có trọng số, ta chỉ cần cộng tổng các trọng số của các cạnh trên đường dẫn đó.

Hàng Xóm và Bậc Của Nút (Neighbors and Degree)

Hai nút được gọi là hàng xóm (Neighbors) nếu giữa chúng có một cạnh kết nối. Bậc (Degree) của một nút là số lượng cạnh nối với nút đó. Tổng bậc của tất cả các nút trong một đồ thị luôn bằng 2m, trong đó m là số cạnh của đồ thị.

Tô Màu Đồ Thị (Graph Coloring)

Quá trình tô màu một đồ thị liên quan đến việc gán màu cho các nút sao cho không có hai nút kề nhau có cùng màu. Đồ thị gọi là đồ thị hai phần (bipartite) nếu có thể tô bằng hai màu mà không vi phạm nguyên tắc này.

Tính Đơn Giản (Simplicity)

Một đồ thị được coi là đơn giản nếu không có cạnh nào nối từ một nút đến chính nó và không có nhiều hơn một cạnh giữa hai nút.

Một Số Cách Biểu Diễn Đồ Thị

Biểu Diễn Dưới Dạng Danh Sách Kề (Adjacency List)

Trong biểu diễn này, mỗi nút được gán với danh sách các nút mà nó kết nối. Đây là cách phổ biến nhất để biểu diễn đồ thị do tính hiệu quả của nó trong việc truy cập các nút kề.

Biểu Diễn Thông Qua Ma Trận Kề (Adjacency Matrix)

Ma trận kề là một mảng hai chiều cho biết sự tồn tại của các cạnh giữa các nút. Dễ dàng kiểm tra xem hai nút có nối với nhau không qua ma trận này.

Biểu Diễn Danh Sách Cạnh (Edge List)

Danh sách cạnh chứa tất cả các cạnh của đồ thị, giúp việc xử lý tất cả các cạnh trở nên dễ dàng hơn. Đây là cách biểu diễn thuận tiện cho các thuật toán cần thao tác với toàn bộ các cạnh mà không phụ thuộc vào các nút.

Tóm lại, lý thuyết đồ thị mở ra một cách tiếp cận mạnh mẽ trong việc giải quyết nhiều vấn đề trong lập trình. Bằng cách hiểu rõ các khái niệm và cách biểu diễn đồ thị, lập trình viên có thể tối ưu hóa và áp dụng chúng một cách hiệu quả trong thực tiễn.
source: viblo