Xét đơn đồ thị vô hướng G = [V, E] có n[1> s >> f; for [int i = 1; i > u >> v; adj[u].push_back[v]; adj[v].push_back[u]; } dfs[s]; // Tìm kiếm theo chiều sâu bắt đầu từ s. if [trace[f] == 0] // Đỉnh f chưa được thăm thì thông báo không tìm được đường đi. cout 2 -> 3 -> 5
Hình vẽ dưới đây cho ta minh họa về quá trình duyệt DFS\text{DFS}:
Nhận xét:
- Nhờ vào kĩ thuật đánh dấu đường đi, nên hàm DFS[u]\text{DFS}[u] chỉ được gọi không quá nn lần.
- Có thể tồn tại nhiều đường đi từ ss tới f,f, nhưng giải thuật DFS\text{DFS} luôn luôn trả về đường đi có thứ tự từ điển nhỏ nhất.
- Quá trình DFS\text{DFS} sẽ cho ta một cây DFS\text{DFS} gốc ss. Khi đó, tồn tại một quan hệ cha - con trên cây được định nghĩa là: Nếu từ đỉnh uu tới thăm đỉnh vv [DFS[u]\big[\text{DFS}[u] gọi DFS[v]]\text{DFS}[v]\big] thì uu là cha của vv.
III. Giải thuật tìm kiếm theo chiều rộng [Breadth First Search]
Tư tưởng thuật toán:
- Dựa trên tư tưởng lập ra một thứ tự duyệt các đỉnh, sao cho các đỉnh gần ss hơn sẽ luôn luôn được duyệt xong trước các đỉnh xa ss hơn. Ví dụ, từ đỉnh ss ta thăm các đỉnh kề với nó là x1,x2,...,xkx_1,x_2,...,x_k. Khi thăm tới x1x_1, sẽ phát sinh việc thăm các đỉnh kề với x1x_1 là x1′,x2′,...,xk′′x'_1 , x'_2,...,x'_{k'}. Dĩ nhiên các đỉnh này đều xa ss hơn so với x1,x2,...,xkx_1, x_2,..., x_k, cho nên chúng sẽ chỉ được thăm sau khi toàn bộ các đỉnh x1,x2,...,xkx_1, x_2,..., x_k đã được thăm hết.
- Quá trình thăm theo cách này sẽ tạo ra một cây BFS\text{BFS} rộng và hẹp, do đó gọi là tìm kiếm theo chiều rộng.
Thứ tự thăm các đỉnh bằng BFS
- Để xây dựng một thứ tự như vậy, ta sẽ tạo ra một danh sách gồm các đỉnh đang được "chờ" thăm. Tại mỗi bước, thăm đỉnh ở đầu danh sách và thêm toàn bộ các đỉnh kề với đỉnh đó [mà chưa được thăm] vào cuối danh sách, như vậy danh sách sẽ được xây dựng thành các lớp liền nhau, mỗi lớp bao gồm các đỉnh cùng kề với một đỉnh nào đó. Cấu trúc dữ liệu phù hợp nhất để xây dựng danh sách này là hàng đợi [queue].
- Việc truy vết cũng diễn ra tương tự như giải thuật DFS\text{DFS}, ta dùng một mảng tracevtrace_v để lưu lại đỉnh liền trước với đỉnh vv trong quá trình duyệt, và kiêm luôn chức năng đánh dấu đỉnh vv đã được thăm hay chưa.
Cài đặt:
void trace[int s, int f]
{
vector < int > path; // Lưu đường đi từ s tới f.
while [f != 0]
{
path.push_back[f];
f = trace[f];
}
for [int i = path.size[] - 1; i >= 0; --i] // In ngược lại để thu được thứ tự từ s -> f.
cout vertexes;
vertexes.push[s];
while [!vertexes.empty[]]
{
int u = vertexes.front[];
vertexes.pop[]; Thăm xong đỉnh ở đầu queue, pop nó ra.
if [u == f] // Nếu đã tới được f thì truy vết và dừng luôn BFS.
{
trace[s, f];
return;
}
for [int v: adj[u]] // Duyệt các đỉnh kề với u.
if [trace[v] == 0] // Nếu đỉnh đó chưa thăm.
{
trace[v] = u; // Lưu vết đường đi tới v.
vertexes.push[v]; // Đẩy vào queue.
}
}
cout adj[100001];
void dfs[int u]
{
visited[u] = true;
for [int v: par[u]]
if [!visited[v]]
dfs[v];
}
int count_ccp[]
{
int ccp_amount = 0; // Số thành phần liên thông.
// Duyệt từng đỉnh, đỉnh nào chưa thăm thì thăm DFS từ đỉnh đó.
for [int u = 1; u > n >> m;
// Xây dựng danh sách kề của đồ thị.
for [int i = 1; i > u >> v;
// Do đồ thị là vô hướng nên u thuộc danh sách kề của v và ngược lại.
adj[u].push_back[v];
adj[v].push_back[u];
}
cout