Chúng ta biết rằng biểu đồ là một cấu trúc dữ liệu phi tuyến tính. Trong cấu trúc dữ liệu này, chúng tôi đặt một số giá trị vào các nút và các nút được kết nối thông qua các cạnh khác nhau. Khi chúng ta có thể lưu trữ dữ liệu vào cấu trúc biểu đồ, chúng ta cũng cần tìm kiếm các phần tử từ biểu đồ để sử dụng chúng.
Để tìm kiếm trong đồ thị, có hai phương pháp khác nhau. Kỹ thuật tìm kiếm đầu tiên theo chiều rộng và kỹ thuật tìm kiếm theo chiều sâu.
Tìm kiếm đầu tiên theo chiều rộng (BFS)
Duyệt tìm kiếm đầu tiên theo chiều rộng (BFS) là một thuật toán, được sử dụng để truy cập tất cả các nút của một biểu đồ nhất định. Trong thuật toán duyệt này, một nút được chọn và sau đó lần lượt tất cả các nút lân cận được truy cập. Sau khi hoàn thành tất cả các đỉnh liền kề, nó di chuyển tiếp để kiểm tra một đỉnh khác và kiểm tra lại các đỉnh lân cận của nó. Để thực hiện thuật toán này, chúng ta cần sử dụng cấu trúc dữ liệu Queue. Tất cả các đỉnh liền kề được thêm vào hàng đợi khi tất cả các đỉnh liền kề đã hoàn thành, một mục được xóa khỏi hàng đợi và bắt đầu đi ngang qua đỉnh đó một lần nữa.
Độ sâu Tìm kiếm Đầu tiên (DFS)
Tìm kiếm theo độ sâu-đầu tiên (DFS) là một thuật toán duyệt đồ thị. Trong thuật toán này, một đỉnh bắt đầu được đưa ra và khi một đỉnh lân cận được tìm thấy, nó sẽ di chuyển đến đỉnh lân cận đó trước và cố gắng đi ngang theo cách tương tự. Nó di chuyển qua toàn bộ độ sâu, hết mức có thể, sau đó nó quay trở lại các đỉnh trước đó để tìm con đường mới.
Để triển khai DFS theo cách lặp lại, chúng ta cần sử dụng cấu trúc dữ liệu ngăn xếp. Nếu chúng ta muốn thực hiện điều đó một cách đệ quy, thì không cần các ngăn xếp bên ngoài, nó có thể được thực hiện ngăn xếp bên trong cho các lệnh gọi đệ quy.