Bình luận

Thông báo

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Test link

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

17 min read

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 = nx[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é!

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
using namespace std;
int n, m;
int u[128], v[128];
vector< list<int> > adj;
vector<bool> mark(128, 0);
vector<int> x;
void printSol() {
for (int i = 1; i <= n; i++) {
cout << x[i] << " ";
}
cout << x[1] << endl;
}
void TRY(int k) {
for (int e : adj[x[k - 1]]) {
if (!mark[e]) {
x[k] = e;
mark[e] = 1;
if (k == n) {
if (find(adj[x[1]].begin(), adj[x[1]].end(), e) != adj[x[1]].end()) {
printSol();
}
}
else {
TRY(k + 1);
}
mark[e] = 0;
}
}
}
int main() {
cin >> n >> m;
adj.resize(n + 1);
x.resize(n + 1);
for (int i = 1; i <= m; i++) {
cin >> u[i] >> v[i];
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
x[1] = 1;
mark[1] = 1;
TRY(2);
return 0;
}
view raw Hamilton.cpp hosted with ❤ by GitHub

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é!

Copyright © Phạm Văn Linh

Đánh Giá Bài Viết:
No pain, no gain !

قد تُعجبك هذه المشاركات

إرسال تعليق

© 2025Phạm Văn Linh. All rights reserved. Developed by Jago Desain
-->

Đã phát hiện Ad Blocker

Vui lòng tắt trình chặn quảng cáo của bạn để tiếp tục!

  1. Click on the AdBlock icon in your browser.
    Nhấp vào biểu tượng AdBlock trong trình duyệt của bạn.
    Adblock
  2. Choose, Don't run on pages on this domain.
    Chọn "Always".
    Adblock
  3. The browser icon should have turned green.
    Biểu tượng trình duyệt phải chuyển sang màu xanh lá.
    Adblock
  4. Refresh the page if it didn't refresh automatically. Thanks!
    Làm mới trang nếu nó không tự động làm mới. Cảm ơn bạn rất nhiều!
  1. Click on the AdBlock Plus icon in your browser.
    Nhấp vào biểu tượng AdBlock Plus trong trình duyệt của bạn.
    Adblock
  2. Click the "This Website" button.
    Nhấp vào nút "Trang web này".
    Adblock
  3. The browser icon should have turned grey.
    Biểu tượng trình duyệt phải chuyển sang màu xám.
    Adblock