Bài viết này trình bày quy trình triển khai DFS cho một cây hoặc biểu đồ được cung cấp.
Làm cách nào để triển khai Tìm kiếm theo chiều sâu hoặc DFS cho một biểu đồ trong Java?
DFS chủ yếu được sử dụng để tìm kiếm biểu đồ bằng cách truy cập từng nhánh/đỉnh chính xác một lần. Nó có thể phát hiện hoặc xác định các chu kỳ trong biểu đồ giúp ngăn chặn bế tắc. Nó có thể được sử dụng để giải quyết các vấn đề về câu đố hoặc mê cung. DFS có thể được triển khai/sử dụng trong thuật toán đồ thị, thu thập dữ liệu web và thiết kế trình biên dịch.
Để được giải thích, hãy truy cập mã bên dưới của Tìm kiếm theo chiều sâu hoặc DFS:
lớp học đồ thị {
riêng tư LinkedList thêmNode [ ] ;
riêng tư boolean đi qua [ ] ;
đồ thị ( int đỉnh ) {
thêmNode = mới LinkedList [ đỉnh ] ;
đi qua = mới boolean [ đỉnh ] ;
vì ( int Tôi = 0 ; Tôi < đỉnh ; Tôi ++ )
thêmNode [ Tôi ] = mới LinkedList ( ) ;
}
khoảng trống thêm cạnh ( int src, int bắt đầu ) {
thêmNode [ src ] . thêm vào ( bắt đầu ) ;
}
Mô tả đoạn mã trên:
- Đầu tiên, lớp có tên là “ đồ thị ' được tạo ra. Bên trong nó, tuyên bố một “ LinkedList ” đặt tên “ thêmNode[] ” và một mảng kiểu boolean có tên “ Đã đi qua[] ”.
- Tiếp theo, chuyển các đỉnh cho hàm tạo của “ đồ thị ” lớp làm tham số.
- Sau đó, “ vì ” vòng lặp được tạo để di chuyển qua từng nút của nhánh đã chọn.
- Cuối cùng, kiểu void “ thêmEdge() ” được sử dụng để thêm các cạnh giữa các đỉnh. Hàm này nhận hai tham số: nguồn của đỉnh “ src ” và đỉnh đích “ bắt đầu ”.
Sau khi tạo biểu đồ, bây giờ chúng ta hãy thêm mã tìm kiếm theo chiều sâu hoặc DFS cho biểu đồ đã tạo ở trên:
khoảng trống DFS ( int đỉnh ) {
đi qua [ đỉnh ] = ĐÚNG VẬY ;
Hệ thống . ngoài . in ( đỉnh + '' ) ;
Trình lặp cái này = thêmNode [ đỉnh ] . listIterator ( ) ;
trong khi ( cái này. hasNext ( ) ) {
int tính từ = cái này. Kế tiếp ( ) ;
nếu như ( ! đi qua [ tính từ ] )
DFS ( tính từ ) ;
}
}
Trong khối mã trên:
- Đầu tiên ' DFS() ” hàm được tạo đang nhận “ đỉnh ” như một tham số. Đỉnh đó được đánh dấu là đã truy cập.
- Tiếp theo, in đỉnh đã truy cập bằng lệnh “ ra.print() ' phương pháp.
- Sau đó, tạo một phiên bản của “ Trình lặp ” lặp qua các đỉnh liền kề của đỉnh hiện tại.
- Nếu đỉnh không được thăm, thì nó sẽ chuyển đỉnh đó tới “ DFS() ' chức năng.
Bây giờ, chúng ta hãy tạo một “ chủ yếu() ” để tạo biểu đồ và sau đó áp dụng DFS cho phần đó:
công cộng tĩnh khoảng trống chủ yếu ( Sợi dây tranh luận [ ] ) {
Đồ thị k = mới đồ thị ( 4 ) ;
k. thêm cạnh ( 0 , 1 ) ;
k. thêm cạnh ( 1 , 2 ) ;
k. thêm cạnh ( 2 , 3 ) ;
k. thêm cạnh ( 3 , 3 ) ;
Hệ thống . ngoài . bản in ( 'Sau đây là độ sâu đầu tiên đi qua' ) ;
k. DFS ( 1 ) ;
}
}
Giải thích đoạn mã trên:
- Đầu tiên, tạo một đối tượng “ k ' cho ' đồ thị() ' phương pháp.
- Tiếp theo, phần “ thêmEdge() ” được sử dụng để thêm các cạnh giữa nhiều đỉnh. Điều này tạo ra cấu trúc của biểu đồ của chúng tôi.
- Cuối cùng, chuyển bất kỳ giá trị đỉnh nào làm đối số cho “ DFS() ' chức năng. Để tìm đường dẫn đỉnh đó từ gốc, hãy sử dụng thuật toán tìm kiếm theo chiều sâu. Chẳng hạn, một giá trị của “ 1 ” được chuyển đến “ DFS() ' chức năng.
Sau khi kết thúc giai đoạn biên dịch:
Đầu ra cho thấy tìm kiếm theo chiều sâu đã được triển khai thành công.
Phần kết luận
Tìm kiếm theo chiều sâu là một thuật toán duyệt đồ thị tạo cơ sở cho nhiều thuật toán đồ thị như tìm đường đi ngắn nhất, cây bao trùm và phân tích kết nối. Nó bắt đầu từ nút gốc và sau đó di chuyển càng sâu càng tốt cho đến nút rời hoặc nút cuối cùng của nhánh đó trước khi quay lại. Bài viết này đã trình bày quy trình triển khai tìm kiếm theo chiều sâu hoặc DFS cho một biểu đồ trong Java.