Trang chủ » Tìm đường đi Euler trên đồ thị
Thuật toán

Tìm đường đi Euler trên đồ thị

cplusplus

Xin chào mọi người!

Hôm nọ có đứa bảo mình chơi thử trò One Touch Drawing, thật sự khá ức chế khi mới clear dc mấy World đã bí (hơi bị ngớ :'( ). Tình cờ mấy ngày sau trường mình lại có giao deadline về phần này (đúng là ghét của nào trời trao của nấy :)) ). Xem thử demo video nhé 😀

Liệu rằng ta có thể tạo ra 1 game tương tự? Điều đó sẽ thành sự thật nếu các bạn hiểu rõ về đồ thị Euler mà mình xin được trình bày dưới đây 😀

1. Nguồn gốc

Ý tưởng của thuật toán này xuất phát từ Bài toán bảy cây cầu Euler (hay còn gọi là Bảy cây cầu ở Königsberg – lấy tên từ thành phố Königsberg, Đức). Bài toán đặt ra là tìm 1 tuyến đường mà đi qua mỗi cây cầu chỉ đúng 1 lần duy nhất (bất kể là đi theo chiều nào của cây cầu).

Bài toán bảy cây cầu Euler
Bài toán bảy cây cầu Euler

Năm 1736, Leonhard Euler đã chứng minh điều đó là không thể được dựa vào thuật ngữ của Lý thuyết đồ thị.

Leonhard Euler (1707 - 1783), nhà toán học và là nhà vật lý học Thuỵ Sỹ.
Leonhard Euler (1707 – 1783), nhà toán học và là nhà vật lý học Thuỵ Sỹ.

2. Khái niệm

Trong Lý thuyết đồ thị, đồ thị vô hướng G = (X, E) có chứa dây chuyền Euler nếu nó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng 1 lần. Nếu đỉnh cuối cùng trùng với đỉnh xuất phát thì ta gọi đây là chu trình Euler. Đồ thị Euler vô hướng là đồ thị vô hướng có chứa ít nhất 1 chu trình Euler.

Đồ thị có hướng G = (X, E) có chứa đường đi Euler nếu nó đi qua tất cả các cạnh của đồ thị đúng 1 lần, phải tôn trọng hướng của cạnh. Nếu đỉnh đầu trùng với đỉnh cuối thì ta gọi đây là mạch Euler. Đồ thị Euler có hướng là đồ thị có hướng chứa ít nhất 1 mạch Euler.

Có lẽ mọi người đã gặp khái niệm này khi còn bé (hay còn gọi là thời trẻ trâu, sửu nhi các kiểu :v ) qua tấm ảnh huyền thoại dưới đây (vẽ xấu đừng ném đá tội nghiệp :'( ):

Ngôi nhà huyền thoại, thứ gắn liền với tuổi thơ mỗi người, được vẽ bằng 1 nét
Ngôi nhà huyền thoại, thứ gắn liền với tuổi thơ mỗi người, được vẽ bằng 1 nét

Ta có các định nghĩa quan trọng:

  • Đồ thị vô hướng G = (X, E) là đồ thị Euler nếu G liên thông và không có đỉnh bậc lẻ.
  • Đồ thị vô hướng G = (X, E) có dây chuyền Euler và KHÔNG chứa chu trình Euler nếu G liên thông và có ĐÚNG 2 đỉnh bậc lẻ.
  • Đồ thị có hướng G = (X, E) có chu trình Euler khi số đỉnh bậc trong của G bằng với số đỉnh bậc ngoài.

Quay trở lại với bài toán bảy cây cầu Euler phía trên, nhà toán học Euler đã loại bỏ các chi tiết dư thừa, và xem vùng đất như đỉnh và cây cầu như cạnh. Ta thu được 1 đồ thị:

Hình thù của đồ thị sau khi chuyển đổi.
Hình thù của đồ thị sau khi chuyển đổi.

Ta nhận thấy rằng trong đồ thị trên có 3 nút bậc 3 và 1 nút bậc 5. Điều đó hoàn toàn trái ngược với định nghĩa ta đã nêu phía trên. Vì vậy không có con đường nào giống như đề bài đã yêu cầu.

2. Cài đặt thuật toán

Ở bài viết này, mình cài đặt thuật toán tìm chu trình Euler trong đồ thị vô hướng G. Các bạn có thể tự mở rộng thêm với đồ thị có hướng nhé 😀

Input đầu vào là 1 file INPUT.txt có dạng như sau:

5
0 1 0 0 1
1 0 1 1 1
0 1 0 1 1
0 1 1 0 1
1 1 1 1 0

Đầu tiên ta tạo 1 class:

class Euler
{
int vertices; // Số đỉnh trong đồ thị
int** graph; // Đồ thị
vector<int> list_vertices; // Danh sách các đỉnh tạo thành chu trình Euler
int count_even_degree_vertex();
int count_odd_degree_vertex();
bool find_path();
public:
Euler() {}
// Việc đọc file với các bạn có lẽ đã quá quen thuộc, cho nên mình xin phép không đề cập ở đây.
Euler(string file_path);
~Euler();
void get_path(string file_path);
};

Ta cần phải đếm danh sách các đỉnh bậc lẻ và bậc chẵn ở đây

// Có lẽ sẽ có bạn thắc mắc tại sao mình lại tạo 2 methods đếm đỉnh bậc chẵn và lẻ làm gì
// Trong khi nếu ta lấy tổng số đỉnh trừ cho đỉnh bậc chẵn thì sẽ ra đỉnh bậc lẻ
//
// Mình muốn xét luôn cả trường hợp đỉnh cô lập nên sẽ tạo 2 methods để đảm bảo 😀
int Euler::count_even_degree_vertex()
{
int total = 0;
for (int i = 0; i < vertices; i++)
{
int count_neighbour = 0;
for (int j = 0; j < vertices; j++)
{
if (graph[i][j] == 1) ++count_neighbour;
}
// Nếu có đỉnh lân cận
// Thêm trường hợp count_neighbour > 0 để loại trừ đỉnh cô lập
if (count_neighbour % 2 == 0 && count_neighbour > 0) ++total;
}
return total;
}
int Euler::count_odd_degree_vertex()
{
int total = 0;
for (int i = 0; i < vertices; i++)
{
int count_neighbour = 0;
for (int j = i + 1; j < vertices; j++)
{
if (graph[i][j] == 1) ++count_neighbour;
}
if (count_neighbour % 2 == 1) ++total;
}
return total;
}

Thuật toán mà mình sử dụng sẽ như sau:

[B1] Khởi tạo 1 stack rỗng và mảng chu trình (đường đi) rỗng

  • Nếu tất cả các đỉnh bậc chẵn => Chọn bất kì đỉnh nào làm đỉnh bắt đầu để đưa vào stack (thường chọn 0).
  • Nếu có đúng 2 đỉnh bậc lẻ => Chọn 1 trong 2 đỉnh để đưa vào stack.
  • Trường hợp còn lại, ta không tìm được chu trình/đường đi Euler.

[B2] Pop đỉnh trong stack:

  • Nếu đỉnh ta đang xét có đỉnh lân cận, xoá cạnh giữa đỉnh lân cận và đỉnh ta đang xét, sau đó push đỉnh lân cận đó vào stack.
  • Nếu đỉnh ta đang xét không có đỉnh lân cận, push vào chu trình/đường đi. Sau đó pop đỉnh ra khỏi stack.
bool Euler::find_path()
{
int even = count_even_degree_vertex();
int odd = count_odd_degree_vertex();
// Đỉnh bậc chẵn + bậc lẻ = tổng số đỉnh => Không có đỉnh cô lập
if (even + odd == vertices && (even == vertices || odd == 2))
{
// Tìm đỉnh bắt đầu
int start_vertex = -1;
for (int i = 0; i < vertices; i++)
{
int count_degree = 0;
for (int j = 0; j < vertices; j++)
{
if (graph[i][j] == 1) count_degree++;
}
if (count_degree % 2 == 1)
{
start_vertex = i;
break;
}
}
// Nếu không tìm được đỉnh bậc lẻ nào => Toàn bộ đỉnh là bậc chẵn
// Lấy đỉnh đầu tiên làm default
if (start_vertex == -1) start_vertex = 0;
stack<int> stack;
stack.push(start_vertex);
while (!stack.empty())
{
int current_vertex = stack.top();
// Biến để kiểm tra xem đỉnh đang xét có đỉnh lân cận hay không
bool has_neighbour = false;
for (int i = 0; i < vertices; i++)
{
if (graph[current_vertex][i] == 1)
{
has_neighbour = true;
graph[current_vertex][i] = graph[i][current_vertex] = 0;
stack.push(i);
break;
}
}
if (!has_neighbour)
{
int vertex = stack.top();
stack.pop();
list_vertices.push_back(vertex);
}
}
return true;
}
else return false;
}

Cuối cùng ta xuất kết quả ra file OUTPUT.txt

void Euler::get_path(string file_path)
{
bool is_found_path = this->find_path();
ofstream file_out(file_path);
if (is_found_path)
{
for (int i = list_vertices.size() - 1; i > 0; i--)
{
file_out << list_vertices[i] << "->";
}
file_out << list_vertices[0];
}
else
{
file_out << "Khong tim thay duong di!";
}
file_out.close();
}

Vậy là với những thao tác đơn giản, ta đã có thể tạo 1 game “One Touch Drawing” rồi. Thật thú vị phải không nào?

Trên đây là bài viết về Tìm đường đi Euler trên đồ thị. Cảm ơn các bạn đã chú ý theo dõi. Hẹn gặp lại ở những bài viết tiếp theo!

About the author

Võ Hoài Sơn

Tính tình bất định
Chọc vào là bịnh
Rất yêu lập trình
Luôn code hết mình
Mình hiện đang là sinh viên của trường ĐH Khoa học tự nhiên TPHCM. Bản thân rất thích code, kiêm luôn cả mần thơ nên thường hơi hâm hâm dở dở. Ngoài ra chém gió, chém chuối, chém trái cây các kiểu cũng là sở trường của mình. Rất mong được làm quen với các bạn :D

Add Comment