Tạo bài viết
Đăng ký
02/10/2018, 15:08

Bài 4: Thuật toán tìm kiếm theo chiều sâu DFS pascal c++

Bài viết này là phần 4 trong 7 bài của Series Lý thuyết đồ thị căn bản Lý thuyết đồ thị căn bản Bài 1: Ma trận kề C++/Pascal Lý thuyết đồ thị Bài 2: Danh sách cạnh C++ Lý thuyết đồ thị Bài 3: Danh sách kề C++ Lý thuyết đồ thị Bài 4: Thuật toán tìm kiếm theo chiều sâu DFS ...

Bài viết này là phần 4 trong 7 bài của Series Lý thuyết đồ thị căn bản

Lý thuyết đồ thị căn bản
  • Bài 1: Ma trận kề C++/Pascal Lý thuyết đồ thị
  • Bài 2: Danh sách cạnh C++ Lý thuyết đồ thị
  • Bài 3: Danh sách kề C++ Lý thuyết đồ thị
  • Bài 4: Thuật toán tìm kiếm theo chiều sâu DFS pascal c++
  • Bài 5: Thuật toán tìm kiếm theo chiều rộng BFS pascal c++
  • Bài 6: Thuật toán loang trên ma trận
  • Cấu trúc dữ liệu Disjoint Sets

Thuật toán tìm kiếm theo chiều sâu DFS là thuật toán tìm kiếm trên cây hoặc đồ thị. Thuật toán này khác với BFS ở chỗ BFS duyệt theo chiều rộng (những đỉnh gần đỉnh gốc sẽ được thăm trước), còn DFS duyệt theo chiều sâu (Xuất phát từ đỉnh gốc, từ đỉnh đó phát triển xa nhất có thể theo mỗi nhánh)

1. Ý tưởng và cài đặt thuật toán DFS

Hình ảnh minh họa DFS, nguồn wikipedia

Tư tưởng thuật toán có thể trình bày như sau: Từ một đỉnh S ban đầu ta sẽ có các đỉnh kề là x, từ đỉnh x ta sẽ có các đỉnh kề là y, và nó cũng thuộc nhánh s-x-y… Chúng ta thăm các nhánh đó theo chiều sâu (thăm đến khi không còn đỉnh kề chưa duyệt). Điều đó gợi cho chúng ta viết một thủ tục đệ quy DFS(u) để mô tả việc duyệt từ đỉnh u sang đỉnh kề v chưa được thăm.

Bạn có thể tham khảo thêm:

Thuật toán tìm kiếm theo chiều rộng BFS pascal c++

a. Mô hình giải thuật DFS

Giải thuật DFS có thể viết theo mô hình dưới đây:

void dfs(int u) { free[u]=false; // đánh dấu đỉnh u đã được thăm for (int v=1; v<=n; v++) if ((tồn tại cạnh u, v) và (free[u][v]==true)) // tồn tại đỉnh kề với u, chưa được thăm dfs(v); //duyệt đỉnh v }
1
2
3
4
5
6
7
void dfs(int u)
{
    free[u]=false; // đánh dấu đỉnh u đã được thăm
    for (int v=1; v<=n; v++)
        if ((tồn tại cạnh u, v) và (free[u][v]==true)) // tồn tại đỉnh kề với u, chưa được thăm
            dfs(v); //duyệt đỉnh v
}

b. Đề bài ví dụ

Ví dụ: Viết chương trình ghi ra thứ tự duyệt DFS xuất phát từ đỉnh s. Đồ thi gồm n đỉnh, m cạnh 2 chiều, các thành phần trên đồ thị liên thông với nhau.

Dữ liệu vào:

  • Dòng đầu: gồm 3 số nguyên n, m, s (1<=n, m<=100, 1<=s<=n)
  • M dòng tiếp theo: mỗi dòng gồm 2 số u, v, mô tả 1 cạnh trong đồ thị

Dữ liệu ra:

  • Gồm nhiều dòng, là thứ tự duyệt DFS

c. Code thuật toán DFS

1. Code DFS C++ tổ chức ma trận kề

Tham khảo thêm về ma trận kề: https://kienthuc24h.com/ma-tran-ke-cpascal-ly-thuyet-thi/

#include <bits/stdc++.h> using namespace std; int a[101][101]; int n, m, Free[101], u, v, s; void DFS(int u) { cout << u << endl; Free[u] = false; for (int v = 1; v <= n; v++) if (a[u][v] == 1 && Free[v]) DFS(v); } int main() { cin >> n >> m >> s; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) a[i][j] = 0; for (int i = 1; i <= m; i++) { cin >> u >> v; a[u][v] = 1; a[v][u] = 1; } for (int i = 1; i <= n; i++) Free[i] = 1; DFS(s); return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
int a[101][101];
int n, m, Free[101], u, v, s;
 
void DFS(int u)
{
    cout << u << endl;
    Free[u] = false;
    for (int v = 1; v <= n; v++)
        if (a[u][v] == 1 && Free[v])
            DFS(v);
}
 
int main()
{
    cin >> n >> m >> s;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = 0;
 
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v;
        a[u][v] = 1;
        a[v][u] = 1;
    }
 
    for (int i = 1; i <= n; i++)
        Free[i] = 1;
    DFS(s);
    return 0;
}

2. Code DFS Pascal tổ chức ma trận kề

Const maxn = 101; Var a : array [1..maxn,1..maxn] of boolean; free : array [1..maxn] of boolean; Q : array [1..maxn] of integer; n, m, s: integer; dau, cuoi : integer; Procedure init; Begin fillchar(a,sizeof(a),false); fillchar(Free,sizeof(Free),true); end; Procedure readf; Var i, u, v : integer; Begin readln(n,m,s); for i := 1 to m do begin readln(u,v); A[u,v] := true; A[v,u] := true; end; end; Procedure DFS(u : integer); Var v : integer; Begin writeln(u); Free[u] := false; For v := 1 to n do If A[u,v] and Free[v] then dfs(v); end; Procedure main; Var i : integer; Begin init; readf; DFS(s); end; BEGIN main; END.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
Const    maxn = 101;
Var    a : array [1..maxn,1..maxn] of boolean;
    free : array [1..maxn] of boolean;
    Q : array [1..maxn] of integer;
    n, m, s: integer;
    dau, cuoi : integer;
                
Procedure    init;
Begin
    fillchar(a,sizeof(a),false);
    fillchar(Free,sizeof(Free),true);
end;
Procedure    readf;
Var        i, u, v : integer;
Begin
    readln(n,m,s);
    for i := 1 to m do
        begin
            readln(u,v);
            A[u,v] := true;
            A[v,u] := true;
        end;
end;
  
  
Procedure    DFS(u : integer);
Var     v : integer;
Begin
writeln(u);
    Free[u] := false;
    
   For v := 1 to n do
If A[u,v] and Free[v] then
dfs(v);
end;
Procedure    main;
Var        i : integer;
Begin
    init;
    readf;
    DFS(s);
end;
BEGIN
    main;
END.

d. Test ví dụ

Các bạn có thể thử các bộ test sau:

Test 1:

InputOutput
7 7 11 2

1 3

1 5

2 4

2 6

3 7

5 6

1

2

4

6

5

3

7

Test 2:

InputOutput
7 7 41 2

1 3

1 5

2 4

2 6

3 7

5 6

4

2

1

3

7

5

6

2. Độ phức tạp DFS

Độ phức tạp thời gian: O(|V|+|E|) với |V| là số đỉnh của đồ thị, |E| là số cạnh

3. Bài tập ứng dụng thuật toán DFS

Bạn có thể áp dụng ngay để làm các bài tập sau về DFS:

Yêu cầu hiểu về thành phần liên thông
VBGRASS spoj – Bãi cỏ ngon nhất
BCLKCOUN spoj PTIT – Đếm số ao

MTNTRAI spoj THPTCBT – 21697. Nông Trại

BCISLAND PTIT spoj – Nước biển

ADS spoj – Quảng cáo

Yêu cầu có kiến thức về cầu – khớp

BCACM11E spoj PTIT – Phương án bắn pháo

Trần Trung Dũng

15 chủ đề

2610 bài viết

Có thể bạn quan tâm
0
Các chủ đề đang được quan tâm
phần mềm lập trình php | lập trình web php + mysql | khóa học lập trình php | tự học lập trình php | học php cơ bản thachpham | Code24h | Cho thuê phòng trọ hà nội | Cho thuê phòng trọ bình thạnh | Cho thuê phòng trọ | Cho thuê nhà trọ
Đăng ký

Đăng ký nhận thông báo

Các bài học thú vị sẽ được gửi đến inbox của bạn

HỖ TRỢ HỌC VIÊN
VỀ CODE24H
HỢP TÁC VÀ LIÊN KẾT
KẾT NỐI VỚI CHÚNG TÔI
TẢI ỨNG DỤNG TRÊN ĐIỆN THOẠI

CCode 24h, code mọi lúc, mọi nơi

© Copy right 2018 - 2024