Hướng dẫn về cấu trúc dữ liệu biểu đồ
Một lập trình viên hiệu quả cần có hiểu biết vững chắc về cấu trúc dữ liệu và thuật toán. Các cuộc phỏng vấn kỹ thuật thường sẽ kiểm tra kỹ năng giải quyết vấn đề và tư duy phản biện của bạn.
Đồ thị là một trong nhiều cấu trúc dữ liệu quan trọng trong lập trình. Trong hầu hết các trường hợp, việc hiểu đồ thị và giải các bài toán dựa trên đồ thị không hề dễ dàng.
Biểu đồ là gì và bạn cần biết gì về nó?
Mục Lục
Đồ thị là gì?
Đồ thị là một cấu trúc dữ liệu phi tuyến tính có các nút (hoặc đỉnh) với các cạnh kết nối chúng. Tất cả các cây đều là các kiểu con của đồ thị, nhưng không phải tất cả các đồ thị đều là cây và biểu đồ là cấu trúc dữ liệu mà cây bắt nguồn từ đó.
Mặc dù bạn có thể xây dựng cấu trúc dữ liệu bằng JavaScript và các ngôn ngữ khác, nhưng bạn có thể triển khai biểu đồ theo nhiều cách khác nhau. Các cách tiếp cận phổ biến nhất là danh sách cạnh, danh sách gần kềvà ma trận kề.
Hướng dẫn biểu diễn đồ thị của Học viện Khan là một nguồn tài nguyên tuyệt vời để tìm hiểu về cách biểu diễn đồ thị.
Có nhiều dạng đồ thị khác nhau. Một sự khác biệt phổ biến là giữa Chỉ đạo và vô hướng đồ thị; chúng xuất hiện rất nhiều trong các thách thức mã hóa và sử dụng trong đời thực.
Các loại đồ thị
- Đồ thị có hướng: Một đồ thị trong đó tất cả các cạnh đều có hướng, còn được gọi là đồ thị.
- Biểu đồ vô hướng: Đồ thị vô hướng còn được gọi là đồ thị hai chiều. Trong đồ thị vô hướng, hướng của các cạnh không quan trọng và đường truyền có thể đi theo bất kỳ hướng nào.
- Đồ thị có trọng số: Đồ thị có trọng số là đồ thị mà các nút và cạnh của nó có giá trị liên quan. Trong hầu hết các trường hợp, giá trị này đại diện cho chi phí khám phá nút hoặc cạnh đó.
- Đồ thị hữu hạn: Một đồ thị có số nút và số cạnh hữu hạn.
- Đồ thị vô hạn: Một đồ thị có vô số nút và số cạnh.
- Biểu đồ tầm thường: Một đồ thị chỉ có một nút và không có cạnh.
- Đồ thị đơn giản: Khi chỉ có một cạnh nối từng cặp nút của đồ thị, nó được gọi là đồ thị đơn giản.
- Đồ thị rỗng: Đồ thị rỗng là đồ thị không có cạnh nối các nút của nó.
- Nhiều đồ thị: Trong một đồ thị, ít nhất một cặp nút có nhiều hơn một cạnh nối chúng. Trong nhiều đồ thị, không có vòng lặp tự.
- Hoàn thành đồ thị: Một biểu đồ hoàn chỉnh là một biểu đồ trong đó mọi nút kết nối với mọi nút khác trong biểu đồ. Nó còn được gọi là đồ thị đầy đủ.
- Đồ thị giả: Một đồ thị có một vòng tự ngoài các cạnh đồ thị khác được gọi là đồ thị giả.
- Biểu đồ thông thường: Đồ thị thông thường là đồ thị trong đó tất cả các nút đều có hoành độ bằng nhau; tức là mọi nút đều có số lân cận như nhau.
- Biểu đồ được kết nối: Một đồ thị được kết nối đơn giản là bất kỳ đồ thị nào trong đó hai nút bất kỳ kết nối với nhau; tức là một đồ thị có ít nhất một đường đi giữa mỗi hai nút của đồ thị.
- Biểu đồ bị ngắt kết nối: Một đồ thị không kết nối là đối lập trực tiếp với một đồ thị được liên thông. Trong một biểu đồ bị ngắt kết nối, không có cạnh nào liên kết các nút của biểu đồ, chẳng hạn như trong vô giá trị đồ thị.
- Đồ thị tuần hoàn: Đồ thị tuần hoàn là đồ thị có chứa ít nhất một chu trình đồ thị (đường dẫn kết thúc tại nơi nó bắt đầu).
- Đồ thị acyclic: Đồ thị mạch hở là đồ thị không có chu trình nào cả. Nó có thể được định hướng hoặc vô hướng.
- Đoạn con: Một đồ thị con là một đồ thị dẫn xuất. Nó là một đồ thị được hình thành từ các nút và các cạnh là các tập con của một đồ thị khác.
Một vòng trong một đồ thị là một cạnh bắt đầu từ một nút và kết thúc tại cùng một nút. Do đó, một vòng lặp bản thân là một vòng lặp chỉ qua một nút đồ thị, như được thấy trong đồ thị giả.
Thuật toán duyệt đồ thị
Là một loại cấu trúc dữ liệu phi tuyến tính, việc duyệt qua một biểu đồ là khá phức tạp. Đi ngang qua một biểu đồ có nghĩa là đi qua và khám phá từng nút được cung cấp bởi có một đường dẫn hợp lệ qua các cạnh. Các thuật toán duyệt đồ thị chủ yếu có hai loại.
- Breadth-First Search (BFS): Tìm kiếm theo chiều rộng là một thuật toán duyệt đồ thị truy cập vào một nút đồ thị và khám phá các vùng lân cận của nó trước khi tiếp tục đến bất kỳ nút con nào của nó. Mặc dù bạn có thể bắt đầu duyệt qua biểu đồ từ bất kỳ nút nào đã chọn, Nút gốc thường là điểm xuất phát ưu tiên.
- Tìm kiếm theo độ sâu-đầu tiên (DFS): Đây là thuật toán duyệt đồ thị chính thứ hai. Nó truy cập vào một nút đồ thị và khám phá các nút hoặc nhánh con của nó trước khi tiếp tục đến nút tiếp theo — nghĩa là đi sâu trước trước khi đi rộng.
Tìm kiếm theo chiều rộng là thuật toán được khuyến nghị để tìm đường đi giữa hai nút nhanh nhất có thể, đặc biệt là đường đi ngắn nhất.
Tìm kiếm theo chiều sâu chủ yếu được đề xuất khi bạn muốn truy cập mọi nút trong biểu đồ. Cả hai thuật toán truyền tải đều hoạt động tốt trong mọi trường hợp, nhưng một thuật toán có thể đơn giản hơn và tối ưu hóa hơn thuật toán kia trong các tình huống đã chọn.
Một minh họa đơn giản có thể giúp hiểu rõ hơn cả hai thuật toán. Hãy coi các trạng thái của một quốc gia như một biểu đồ và cố gắng kiểm tra xem hai trạng thái, X và Y, được kết nối. Tìm kiếm theo chiều sâu có thể đi trên một con đường gần như khắp đất nước mà không nhận ra đủ sớm rằng Y chỉ cách 2 tiểu bang X.
Ưu điểm của tìm kiếm theo chiều rộng là nó duy trì sự gần gũi với nút hiện tại nhất có thể trước khi chuyển sang nút tiếp theo. Nó sẽ tìm thấy mối liên hệ giữa X và Y trong thời gian ngắn mà không cần phải khám phá cả nước.
Một sự khác biệt chính giữa hai thuật toán này là cách chúng được triển khai trong mã. Tìm kiếm theo chiều rộng là một thuật toán lặp lại và sử dụng một xếp hàngtrong khi tìm kiếm theo chiều sâu thường được triển khai dưới dạng thuật toán đệ quy điều đó thúc đẩy cây rơm.
Dưới đây là một số mã giả chứng minh việc triển khai cả hai thuật toán.
Breadth-First Search
bfs(Graph G, GraphNode root) {
let q be new Queue
root.visited = true
q.enqueue(root)
while (q is not empty) {
let current be q.dequeue()
for(neighbors n of current in G) {
if (n is not yet visited) {
q.enqueue(n)
n.visited = true
}
}
}
}
Tìm kiếm sâu-đầu tiên
dfs(Graph G, GraphNode root) {
if (root is null) return
root.visited = true
for (neighbors n of root in G)
if (n is not yet visited)
dfs(G, n)
}
Một số thuật toán duyệt đồ thị khác bắt nguồn từ các tìm kiếm theo chiều rộng và tìm kiếm theo chiều sâu. Những cái phổ biến nhất là:
- Tìm kiếm hai chiều: Thuật toán này là một cách tối ưu hóa để tìm đường đi ngắn nhất giữa hai nút. Nó sử dụng hai tìm kiếm theo chiều rộng mà xung đột nhau nếu có một đường dẫn.
- Sắp xếp tôpô: Điều này được sử dụng trong đồ thị có hướng để sắp xếp các nút theo thứ tự mong muốn. Bạn không thể áp dụng sắp xếp tôpô cho đồ thị vô hướng hoặc đồ thị có chu trình.
- Thuật toán Dijkstra: Đây cũng là một loại BFS. Nó cũng được sử dụng để tìm đường đi ngắn nhất giữa hai nút trong đồ thị có hướng có trọng sốcó thể có chu kỳ hoặc không.
Các câu hỏi phỏng vấn phổ biến dựa trên đồ thị
Đồ thị là một trong những cấu trúc dữ liệu quan trọng mà mọi lập trình viên nên biết. Các câu hỏi thường xuất hiện về chủ đề này trong các cuộc phỏng vấn kỹ thuật và bạn có thể gặp phải một số vấn đề kinh điển liên quan đến chủ đề này. Chúng bao gồm những thứ như vấn đề “thẩm phán thị trấn”, “số đảo” và “nhân viên bán hàng lưu động”.
Đây chỉ là một vài trong số rất nhiều vấn đề phỏng vấn dựa trên đồ thị phổ biến. Bạn có thể dùng thử chúng trên LeetCode, HackerRank hoặc GeeksforGeeks.
Hiểu cấu trúc dữ liệu đồ thị và thuật toán
Đồ thị không chỉ hữu ích cho các cuộc phỏng vấn kỹ thuật. Họ cũng có các trường hợp sử dụng trong thế giới thực, chẳng hạn như trong mạng, bản đồ, và hệ thống hàng không để tìm các tuyến đường. Chúng cũng được sử dụng trong logic cơ bản của hệ thống máy tính.
Đồ thị rất tuyệt vời để tổ chức dữ liệu và giúp chúng ta hình dung các vấn đề phức tạp. Tuy nhiên, đồ thị chỉ nên được sử dụng khi thực sự cần thiết để ngăn ngừa sự phức tạp về không gian hoặc các vấn đề về bộ nhớ.