Oleksii Trekhleb | Javascript algorithms (Hamiltonian path)

This is a series of books diving deep into the core mechanisms of the JavaScript language.

 · 2 phút đọc.

This is a series of books diving deep into the core mechanisms of the JavaScript language.

Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem.

Hamiltonian cycle

One possible Hamiltonian cycle through every vertex of a dodecahedron is shown in red – like all platonic solids, the dodecahedron is Hamiltonian.

Naive Algorithm

Generate all possible configurations of vertices and print a configuration that satisfies the given constraints. There will be n! (n factorial) configurations.

while there are untried configurations
{
generate the next configuration
if ( there are edges between two consecutive vertices of this
configuration and there is an edge from the last vertex to       the first ).
{
print this configuration;
break;
}
}

Backtracking Algorithm

Create an empty path array and add vertex 0 to it. Add other vertices, starting from the vertex 1. Before adding a vertex, check for whether it is adjacent to the previously added vertex and not already added. If we find such a vertex, we add the vertex as part of the solution. If we do not find a vertex then we return false.

nhavantuonglai

Share:
Quay lại.

Có thể bạn chưa đọc

Xem tất cả »

Đăng ký nhận bảng tin hàng tuần

Liên lạc trao đổi

Liên lạc thông qua Instagram

Thông qua Instagram, bạn có thể trao đổi trực tiếp và tức thời, cũng như cập nhật những thông tin mới nhất từ nhavantuonglai.

Tức thời

Bạn có thể gửi và nhận tin nhắn nhanh chóng, trực tiếp, giúp những vấn đề cá nhân của bạn được giải quyết tức thời và hiệu quả hơn.

Thân thiện

Vì tính chất là kênh liên lạc nhanh, nên bạn có thể bỏ qua những nghi thức giao tiếp thông thường, chỉ cần lịch sự và tôn trọng thì sẽ nhận được sự phản hồi đầy thân thiện, thoải mái từ tác giả.

Trao đổi trên email

Thông qua email cá nhân, bạn có thể trao đổi thỏa thuận hợp tác, kết nối chuyên sâu và mang tính chuyên nghiệp.

Tin cậy

Trong một số trường hợp, email được dùng như một tài liệu pháp lý, chính vì vậy mà bạn có thể an tâm và tin cậy khi trao đổi với tác giả thông qua email.

Chuyên nghiệp

Cấu trúc của email đặt tính chuyên nghiệp lên hàng đầu, nên những thông tin, nội dung được viết trong email từ tác giả sẽ luôn đảm bảo điều này ở mức cao nhất.