Thuật Toán Tìm Chu Trình Hamilton

Hế lô các bạn, mình đã quay trở lại rồi đây. Cũng lâu rồi không đăng về thuật toán nhờ, nhân tiện mấy hôm bảo trì blog xem lại một vài thuật toán được học trong môn Cấu Trúc Dữ Liệu Và Thuật Toán, để trở lại đăng bài cho anh em xem liền.

Thuật Toán Tìm Chu Trình Hamilton Trong Đồ Thị Vô Hướng

Như các bạn đã thấy ở tiêu đề bài viết, thuật toán mà mình muốn chia sẻ ngày hôm nay là thuật toán tìm chu trình Hamilton trong đồ thị vô hướng. Chúng ta sẽ tìm hiểu kĩ hơn về thuật toán ở bên dưới nhé!

Tìm Hiểu Thuật Toán

Tại Sao Lại Gọi Là Chu Trình Hamilton?

Chu trình Hamilton hay đường đi Hamilton có nguồn gốc từ bài toán: "Xuất phát từ một đỉnh của khối thập nhị diện đều hãy đi dọc theo các cạnh của khối đó sao cho đi qua tất cả các đỉnh khác, mỗi đỉnh đúng một lần sau đó quay về đỉnh xuất phát.
Đường đi được gọi theo tên của William Rowan Hamilton phát biểu vào năm 1859.

Mô Tả Thuật Toán:

Thuật toán tìm chu trình Hamilton được giải theo đệ quy quay lui và bằng ngôn ngữ C++.
Đầu vào đồ thị vô hướng có n đỉnh và m cạnh. Danh sách đỉnh kề adj được khai báo dưới dạng vector<list> với adj[i] là danh sách đỉnh kề của đỉnh i.
vector<bool> mark để đánh dấu các đỉnh là true nếu đã đi qua và false nếu ngược lại.
vector<int> x là mô hình hóa của chu trình Hamilton.
Thuật toán được bắt đầu từ một đỉnh được chọn làm đỉnh xuất phát x[1] sau đó gọi hàm quay lui TRY(k) để tìm tiếp các đỉnh tiếp theo trong chu trình.
Hàm đệ quy quay lui được mô tả như sau:
Với mỗi hàm TRY(k) ta sẽ xét lần lượt các đỉnh e thuộc danh sách kề của x[k - 1].
Nếu mark[e] = false ta chọn x[k] = e và đánh dấu mark[e] = true.
Nếu x[k] thỏa mãn điều kiện k = n và x[k] thuộc danh sách đỉnh kề của x[1] thì ghi nhận chu trình Hamilton.
Nếu k < n, ta tiếp tục xét TRY(k + 1).
Sau khi thực hiện xong hàm TRY(k + 1) ta đánh dấu e là chưa được xét (mark[e] = false) rồi tiếp tục xét tới các điểm tiếp theo trong danh sách đỉnh kề của x[k - 1].

Mã Nguồn:

Mình code dựa trên mô tả thuật toán ở bên trên, nếu các bạn đọc phần mô tả thuật toán mà chưa hiểu rõ thì có thể xem thêm phần code để hiểu hơn nhé!

Ví Dụ:

Đồ Thị:

Đồ Thị

Input:

Dòng đầu là n đỉnh mà m cạnh, và m dòng tiếp theo là mô hình hóa của các cạnh.

7 12
1 3
1 6
2 4
2 5
2 6
2 7
3 4
3 6
3 7
4 5
4 7
6 7

Output:

1 3 4 5 2 7 6 1
1 3 7 4 5 2 6 1
1 6 2 5 4 7 3 1
1 6 7 2 5 4 3 1

Lời Kết

Trên đây là những chia sẻ của mình về cách tìm chu trình Hamilton. Tất cả chỉ dựa trên những gì mình học và mình hiểu, nếu có bất kì sai sót ở đâu các bạn hãy để lại comment ở bên dưới để mình biết và sửa lại nhé!