Theo Lý thuyết đồ thị - Lê Minh Hoàng
[Hướng dẫn] Tìm đường đi trong đồ thị: Phần 1 - Thuật toán DFS
doreamonhihi
Posts: 38Registered
Ở trong bài viết trước, mình đã giới thiệu qua về đồ thị và một số ứng dụng của nó trong lập trình. Như mình đã viết, một trong những ứng dụng phổ biến nhất trong cuộc sống của chúng ta là sử dụng trong hệ thống định vị toàn cầu (GPS), hoặc cụ thể hơn trong game chính là việc tìm đường đi từ điểm nay đến điểm kia khi các bạn chơi những game chiến thuật thời gian thực (RTS). Vậy các bạn đã khi nào thắc mắc làm như thế nào mà có thể kiểm tra xem có tồn tại đường đi từ điểm này đến điểm khác như thế nào chưa ? 
Trong bài viết này, mình sẽ bắt đầu với thuật toán DFS (Depth-First Search) hay còn gọi là tìm kiếm theo chiều sâu.
Kiến thức cần chuẩn bị:
- Nắm vững kiến thức cơ bản về C/ C++, STL trong C++.
I - Tư tưởng thuật toán:
II - Cài đặt:
Chú ý:
- Cần khởi tạo mảng visited ban đầu là false hết (chưa thăm bất kì đỉnh nào).
- Mảng pre khởi tạo ban đầu là 0 hết, sẽ dùng cho việc sau này in ra đường đi từ 1 đỉnh đến đỉnh còn lại.
- Mặc định bên dưới mình không truyền vector hay mảng nào vào hàm vì mình mặc định chúng sẽ là biến toàn cục.
- Kết quả khi in ra đường đi của thuật toán khi dùng ma trận kề và danh sách kề sẽ khác nhau (dù kết quả kiểm tra có tồn tại đường đi từ đỉnh này đến đỉnh khác không đổi, nhưng đường đi in ra có thể sẽ khác nhau do thứ tự duyệt đỉnh khác nhau)
1. Đối với ma trận kề:
- Mảng visited: đánh dấu những đỉnh đã được thăm kể từ đỉnh khởi đầu.
- Mảng pre: lưu lại đỉnh liền trước đó là đỉnh thăm đỉnh hiện tại, vì vậy nếu muốn truy tìm đường đi đến 1 đỉnh nào đó sau khi kiểm tra đỉnh v đấy có thể thăm được từ đinh xuất phát (kiểm tra giá trị visited[v]) thì cần phải truy ngược từ cuối về đầu, trong trường hợp muốn in theo thứ tự xuôi từ đầu đến cuối có thể lưu tạm lại vào 1 mảng nào đó rồi đảo ngược mảng (vector cũng được, khuyến khích dùng vector hơn nếu dùng C++)
- Như cách hoạt động của cả 2 code trên thì từ 1 đỉnh nó sẽ đánh dấu tất cả những đỉnh mà nó có thể thăm được trên đồ thị.
3. Ứng dụng:
- Kiểm tra xem có thể di chuyển từ điểm này đến điểm khác không.
- Duyệt cây.
VD cụ thể:
Với lệnh Component.GetComponentInChildren trong Unity, ta có thể tìm được component ở trong object con của 1 object nào đó. Tư tưởng của lệnh này là dựa trên thuật toán DFS, duyệt từ object cha (giả sử bạn đặt object B trong object A, thì object A gọi là object cha của object B ), sau đó sẽ duyệt tiếp đến các object con cho đến khi nào không còn object con nào của nó nữa thì thôi.
Tuy DFS có thể giúp ta tìm được đường đi từ đỉnh này đến đỉnh khác, nhưng nó hoàn toàn không chắc chắn sẽ là đường đi có độ dài ngắn nhất, nên cần phải lưu ý để sau này tránh áp dụng nhầm trong game. Ở bài viết sau, mình sẽ giới thiệu thuật toán tìm đường đi ngắn nhất (cũng là cơ bản nhất) trong đồ thị
Trong bài viết này, mình sẽ bắt đầu với thuật toán DFS (Depth-First Search) hay còn gọi là tìm kiếm theo chiều sâu. Kiến thức cần chuẩn bị:
- Nắm vững kiến thức cơ bản về C/ C++, STL trong C++.
- Kiến thức cơ bản về đồ thị và cách biểu diễn đồ thị trong C/ C++.
- Nắm được khái niệm đệ quy là gì.
- Nắm được khái niệm đệ quy là gì.
I - Tư tưởng thuật toán:
Tư tưởng của thuật toán có thể trình bày như sau: Trước hết, mọi đỉnh x kề với S tất nhiên sẽ đếnđược từ S. Với mỗi đỉnh x kề với S đó thì tất nhiên những đỉnh y kề với x cũng đến được từ S...Điều đó gợi ý cho ta viết một thủ tục đệ quy DFS(u) mô tả việc duyệt từ đỉnh u bằng cách thông báo thăm đỉnh u và tiếp tục quá trình duyệt DFS(v) với v là một đỉnh chưa thăm kề với u
Chú ý:
- Cần khởi tạo mảng visited ban đầu là false hết (chưa thăm bất kì đỉnh nào).
- Mảng pre khởi tạo ban đầu là 0 hết, sẽ dùng cho việc sau này in ra đường đi từ 1 đỉnh đến đỉnh còn lại.
- Mặc định bên dưới mình không truyền vector hay mảng nào vào hàm vì mình mặc định chúng sẽ là biến toàn cục.
- Kết quả khi in ra đường đi của thuật toán khi dùng ma trận kề và danh sách kề sẽ khác nhau (dù kết quả kiểm tra có tồn tại đường đi từ đỉnh này đến đỉnh khác không đổi, nhưng đường đi in ra có thể sẽ khác nhau do thứ tự duyệt đỉnh khác nhau)
1. Đối với ma trận kề:
void DFS(int u, int m)
{
visited[u]=true;
for (int v=0; v<m; v++)
{
if (!visited[v] && G[u][v])
{
pre[v]=u;
DFS(v, m);
}
}
}
{
visited[u]=true;
for (int v=0; v<m; v++)
{
if (!visited[v] && G[u][v])
{
pre[v]=u;
DFS(v, m);
}
}
}
2. Đối với danh sách kề:
void DFS(int u)
{
visited[u]=true;
for (int v: G[u])
{
if (!visited[v] && G[u][v])
{
pre[v]=u;
DFS(v);
}
}
}
Giải thích:{
visited[u]=true;
for (int v: G[u])
{
if (!visited[v] && G[u][v])
{
pre[v]=u;
DFS(v);
}
}
}
- Mảng visited: đánh dấu những đỉnh đã được thăm kể từ đỉnh khởi đầu.
- Mảng pre: lưu lại đỉnh liền trước đó là đỉnh thăm đỉnh hiện tại, vì vậy nếu muốn truy tìm đường đi đến 1 đỉnh nào đó sau khi kiểm tra đỉnh v đấy có thể thăm được từ đinh xuất phát (kiểm tra giá trị visited[v]) thì cần phải truy ngược từ cuối về đầu, trong trường hợp muốn in theo thứ tự xuôi từ đầu đến cuối có thể lưu tạm lại vào 1 mảng nào đó rồi đảo ngược mảng (vector cũng được, khuyến khích dùng vector hơn nếu dùng C++)
- Như cách hoạt động của cả 2 code trên thì từ 1 đỉnh nó sẽ đánh dấu tất cả những đỉnh mà nó có thể thăm được trên đồ thị.
3. Ứng dụng:
- Kiểm tra xem có thể di chuyển từ điểm này đến điểm khác không.
- Duyệt cây.
VD cụ thể:
Với lệnh Component.GetComponentInChildren trong Unity, ta có thể tìm được component ở trong object con của 1 object nào đó. Tư tưởng của lệnh này là dựa trên thuật toán DFS, duyệt từ object cha (giả sử bạn đặt object B trong object A, thì object A gọi là object cha của object B ), sau đó sẽ duyệt tiếp đến các object con cho đến khi nào không còn object con nào của nó nữa thì thôi.
Tuy DFS có thể giúp ta tìm được đường đi từ đỉnh này đến đỉnh khác, nhưng nó hoàn toàn không chắc chắn sẽ là đường đi có độ dài ngắn nhất, nên cần phải lưu ý để sau này tránh áp dụng nhầm trong game. Ở bài viết sau, mình sẽ giới thiệu thuật toán tìm đường đi ngắn nhất (cũng là cơ bản nhất) trong đồ thị
Comments
THAM GIA GROUP CỦA TTC TRÊN FACEBOOK
THAM GIA GROUP CỦA TTC TRÊN FACEBOOK