TRONG DFS , các nút đang khám phá được lưu trữ trong cấu trúc dữ liệu ngăn xếp. Các cạnh hướng chúng ta đến các nút chưa được khám phá được gọi là ' cạnh khám phá ‘ trong khi các cạnh sẽ dẫn đến các nút đã được truy cập được gọi là ‘ cạnh khối '. DFS hữu ích trong các tình huống khi lập trình viên muốn tìm các thành phần hoặc chu trình được kết nối trong biểu đồ.
Thực hiện theo hướng dẫn của bài viết này để thực hiện DFS trong C++.
Triển khai DFS trong C++
Trong phần sau, chúng ta sẽ xem xét cách DFS được thực hiện trong C++. Người ta có thể làm theo các bước nhất định để thực hiện DFS .
- Chèn nút gốc của cây hoặc biểu đồ vào ngăn xếp.
- Thêm mục trên cùng của ngăn xếp vào danh sách đã truy cập của bạn.
- Khám phá tất cả các nút liền kề với nút đã truy cập và thêm các nút chưa truy cập vào ngăn xếp.
- Lặp lại bước 2 và 3 cho đến khi ngăn xếp trống.
Mã giả DFS
Các DFS mã giả được hiển thị bên dưới. bên trong nhiệt() chức năng, chúng tôi thực hiện DFS chức năng trên mỗi nút. Vì biểu đồ có thể có hai phần không liên kết với nhau nên chúng ta có thể chạy DFS thuật toán trên mỗi nút để đảm bảo rằng chúng tôi đã bao phủ mọi đỉnh.
DFS ( g một )
Một. đã đến thăm = ĐÚNG VẬY
vì mọi b ∈ g. Tính từ [ Một ]
nếu như b. đã đến thăm == SAI
DFS ( g, b )
nhiệt ( )
{
Với mỗi a ∈ g
Một. đã đến thăm = SAI
Với mỗi a ∈ g
DFS ( g, một )
}
Ở đây g, a và b đại diện cho biểu đồ, nút được truy cập đầu tiên và nút trong ngăn xếp tương ứng.
Triển khai DFS trong C++
Một chương trình C++ cho DFS thực hiện được đưa ra dưới đây:
#include
#bao gồm
#bao gồm
sử dụng không gian tên tiêu chuẩn ;
bản mẫu < tên loại t >
lớp học Độ sâuĐầu tiênTìm kiếm
{
riêng tư :
bản đồ < t, danh sách < t > > adjList ;
công cộng :
Độ sâuĐầu tiênTìm kiếm ( ) { }
khoảng trống Add_edge ( t a, t b, bool Bạn = ĐÚNG VẬY )
{
adjList [ Một ] . đẩy lùi ( b ) ;
nếu như ( Bạn )
{
adjList [ b ] . đẩy lùi ( Một ) ;
}
}
khoảng trống In ( )
{
vì ( tự động Tôi : adjList ) {
cout << Tôi. Đầu tiên << '->' ;
vì ( mục t : Tôi. thứ hai ) {
cout << lối vào << ',' ;
}
cout << kết thúc ;
}
}
khoảng trống dfs_helper ( nút t, bản đồ < t, bool > & đã đến thăm ) {
đã đến thăm [ nút ] = ĐÚNG VẬY ;
cout << nút << '' << kết thúc ;
vì ( hàng xóm : adjList [ nút ] ) {
nếu như ( ! đã đến thăm [ hàng xóm ] ) {
dfs_helper ( hàng xóm, thăm viếng ) ;
}
}
}
khoảng trống DFS ( t src )
{
bản đồ < t, bool > đã đến thăm ;
dfs_helper ( src, đã truy cập ) ;
}
} ;
int chủ yếu ( ) {
Độ sâuĐầu tiênTìm kiếm < int > g ;
g. Add_edge ( 0 , 5 ) ;
g. Add_edge ( 0 , 7 ) ;
g. Add_edge ( 4 , 7 ) ;
g. Add_edge ( 7 , số 8 ) ;
g. Add_edge ( 2 , 1 ) ;
g. Add_edge ( 0 , 6 ) ;
g. Add_edge ( 2 , 4 ) ;
g. Add_edge ( 3 , 2 ) ;
g. Add_edge ( 3 , 6 ) ;
g. Add_edge ( 7 , 5 ) ;
g. Add_edge ( 5 , số 8 ) ;
g. In ( ) ;
g. DFS ( 6 ) ;
cout << kết thúc ;
}
Trong mã này, chúng tôi đã thực hiện DFS thuật toán theo mã giả đã cho ở trên. Chúng tôi có 12 cặp nút. Chúng tôi đã định nghĩa một lớp “ g ” đại diện cho một đồ thị có các đỉnh a và b đại diện cho các nút được truy cập và chưa được truy cập.
đầu ra
Phần kết luận
DFS là một thuật toán tìm kiếm phổ biến hữu ích cho một số tình huống, chẳng hạn như tìm các chu trình trong biểu đồ và nhận thông tin về các thành phần được kết nối hoặc tất cả các đỉnh trong biểu đồ. Chúng tôi cũng mô tả hoạt động của DFS phương pháp với một ví dụ. DFS sử dụng ngăn xếp để thực hiện kỹ thuật và cũng có thể được sử dụng trên cây.