# DFS - BFS

## Note
Để đệ quy được sâu, thêm 2 dòng này vào đầu bài:

import sys
sys.setrecursionlimit(độ sâu đệ quy cần dùng)

DFS: Depth-first search (Tìm kiếm theo chiều sâu)
BFS: Breadth-first search (Tìm kiếm theo chiều rộng)

## Mục tiêu chung của DFS + BFS
Hai thuật toán duyệt này nhìn được dùng để duyệt qua toàn bộ tất cả các đỉnh (trong một thành phần liên thông), để từ đó lấy thông tin của các đỉnh.

## DFS
Bắt đầu từ một đỉnh $u$, ta lần lượt duyệt các đỉnh bằng cách sau:
1. Đánh dấu đỉnh $u$ hiện tại đã thăm
2. Chọn một đỉnh $v$ kề $u$ sao cho $v$ chưa được thăm.
- Nếu tìm được đỉnh $v$ phù hợp, chuyển sang thăm đỉnh $v$ và làm tương tự hai điều 1 & 2
- Ngược lại, quay về đỉnh $u$ cũ ngay trước đó để thực hiện lại bước 2.


Nếu ta đã dựng được danh sách kề `graph`, ta có thể code như sau:

visited = [False] * (n + 1)        # đánh dấu tất cả chưa được thăm
def dfs(u):
    visited[u] = True
    # (thông thường) xử lý đỉnh u
    
    for v in graph[u]:             # với mỗi đỉnh kề với u
        if visited[v] == True:     # đỉnh nào thăm rồi thì bỏ qua
            continue
        dfs(v)
        

vector<int> graph[MAX];

bool visited[MAX] = {};
void dfs(int u){
    visited[u] = true;
    // (thông thường) xử lý đỉnh u ở đây 
    
    for (int v: graph[u]){
        if (visited[v] == true) 
            continue;
        dfs(v);
    }
}

**Nhắc lại:** DFS/BFS chỉ duyệt được các đỉnh cùng thuộc thành phần liên thông (đối với đồ thị vô hướng

**Tính chất:** Nếu sắp xếp lại danh sách cạnh, sẽ luôn cho được đường đi có **thứ tự từ điển nhỏ nhất**.
- Chứng minh: giả sử $u$ kề $v_1$ và $v_2$, và $v_1 < v_2$. Để có thứ tự từ điển nhỏ nhất, $u$ **bắt buộc** phải đi tới $v_1$ trước, thay vì $v_2$. Vì vậy thuật toán trên phải tạo được đường đi tttđ nhỏ nhất.

## BFS
**Kiến thức cần học:** QUEUE

Chiến thuật duyệt của BFS:
1. Tạo ra một danh sách chờ các đỉnh
2. Từ một đỉnh, ta duyệt hết toàn bộ các đỉnh chưa được thăm kề nó, rồi cho vào danh chờ
3. Tiếp tục rút một đỉnh từ danh sách chờ và làm lại điều 2

Nếu thứ tự duyệt như trên, ta có tính chất: khoảng cách của các đỉnh được duyệt tăng dần.

bool visited[MAX];
int distance[MAX];
queue<int> q;

void bfs(int root){
    visited[root] = true; 
    distance[root] = 0;
    q.push(root);
    
    while (!q.empty()){
        int node = q.front(); q.pop();
        for (int child: graph[node])
            if (visited[child] == true) continue;
            else {
                // giống dòng đầu
                visited[child] = true; 
                distance[child] = distance[node] + 1;
                q.push(child); 
            }
    }
}

## Bài tập

### BDFS (DFS Cơ bản)
Duyệt các đỉnh từ $1 \rightarrow n$, đỉnh nào chưa được thăm tức là có tplt chưa được thăm, đỉnh nào thăm rồi thì bỏ qua.

### BFS (BFS Cơ bản)
Bước đầu tiên, ta sẽ BFS bắt đầu từ đỉnh S

bool visited[MAX];
int distance[MAX];
queue<int> q;

void bfs(int root){
    visited[root] = true; 
    distance[root] = 0;
    q.push(root);
    
    while (!q.empty()){
        int node = q.front(); q.pop();
        for (int child: graph[node])
            if (visited[child] == true) continue;
            else {
                // giống dòng đầu
                visited[child] = true; 
                distance[child] = distance[node] + 1;
                q.push(child); 
            }
    }
}

Sau đó, theo đề bài, ta sắp xếp tăng dần theo khoảng cách, nếu bằng nhau thì theo chỉ số $\Rightarrow$ lưu lại bằng mảng `pair`

pair<int, int> results[MAX];
for (int i = 1; i <= n; i++)
    results[i] = {distance[i], i};

sort(results + 1, results + 1 + n);
for (int i = 1; i <= n; i++)
    cout << results[i].second << ' ' << results[i].first << '\n';

### CSES 1666 - building road
Cho một đồ thị vô hướng $n$ đỉnh $m$ cạnh, cần tạo thêm bao nhiêu cạnh để đảm bảo cả $n$ đỉnh liên thông?

#### Solution
Giả sử đồ thị bị chia thành $X$ vùng liên thông, ta cần dùng $X-1$ cạnh để nối chúng lại thành một thể.

Để xác định một thành phần liên thông, ta dùng thuật toán duyệt trên đồ thị (DFS):
- duyệt i = 1 -> n, nếu đỉnh nào chưa được thăm => chưa thuộc tplt nào cả => dfs(i) để duyệt tplt mới

Để dựng một cách nối, ta chỉ cần bốc ra $X$ đỉnh đại diện của $X$ thành phần liên thông, rồi nối vào nhau thành một đường thẳng.

# setrecursionlimit: 10^5
# nhập vào

visited = [False] * (n + 1)
def dfs(u):
    visited[u] = True
    for v in graph[u]:
        if visited[v] == True:
            continue
        dfs(v)

số_tplt = 0
đại_diện = []

for i = 1-> n
    if visited[i] == False:
        # có một tplt mới
        số_tplt += 1;
        đại_diện.append(i)
        dfs(i)

print(số_tplt - 1)
for i = 1 -> số_tplt - 1:
    print(đại_diện[i - 1], đại_diện[i])

### Đường đi đẹp nhất
dựa vào tính chất của đường đi DFS, ta sắp xếp lại danh sách cạnh rồi duyệt.
để có đỉnh của đường đi, ta lưu lại.
khi vừa tới $t$, dừng luôn.

### Đếm phòng

khai báo kiểu dữ liệu tọa độ ô, tạo sẵn 4 hướng:

duyệt các ô:

thuật toán:

## cses1667
Đề yêu cầu tìm đường đi ngắn nhất từ $1$ tới $n$, và in ra đường đi đó.

Ta sẽ BFS từ đỉnh $1$, và ngoài lưu `distance[i]`, thì với mỗi đỉnh $i$ ta lưu thêm `prev[i]`, cho biết trên đường đi ngắn nhất từ $1 \rightarrow i$, đỉnh ngay phía trước nó là đỉnh nào.

int prev[MAX];

void bfs(int root){
    visited[root] = true; 
    distance[root] = 0;
    q.push(root);
    
    while (!q.empty()){
        int node = q.front(); q.pop();
        for (int child: graph[node])
            if (visited[child] == true) continue;
            else {
                // giống dòng đầu
                visited[child] = true; 
                distance[child] = distance[node] + 1;
                prev[child] = node; // THÊM DÒNG NÀY VÀO
                q.push(child); 
            }
    }
}

Để in ra đường đi từ 1 tới n, ta lần lượt đi ngược từ $n \rightarrow prev[n] \rightarrow prev[prev[n]] \rightarrow \dots \rightarrow 1$

vector<int> answer;
void trace(){
    int node = n;
    answer.push_back(node);
    
    while (node != 1){
        node = prev[node];
        answer.push_back(node);
    }
    
    // đảo ngược thứ tự
    reverse(answer.begin(), answer.end());
}