BFS & DFS
Xem sơ đồ thị 🌴. Do BFS và DFS là 2 thuật toán duyệt đồ thị.
BFS (Breathe-First Search)
Xài khi nào?
Tìm kiếm theo chiều rộng. Dùng trên đồ thị không trọng số (vô hướng hoặc có hướng). Nếu có trọng số thì trọng số các đường đi phải giống nhau (do thuật toán chỉ đếm số cạnh đi qua).
BFS trả lời được câu hỏi:
- có đường từ u v hay không?
- tìm được đường đi ngắn nhất (nếu tồn tại)
Giới thiệu cơ chế
Tưởng tượng giống như nhỏ giọt dầu xuống, giọt dầu loang ra khắp rộng. Duyệt BFS sẽ đi tất cả đường đi có thể đi.
TODO: Giả sử với cái hình như này (14:41)
Nó sẽ đi từ đỉnh ra, đỉnh nào gần đỉnh gốc trước thì đi trước. Làm thế nào để biết phải đi đỉnh nào trước dùng array để lưu lại. Những điểm gần hơn thì mình cần ưu tiên xử lý hơn xử lý thằng nào lưu trước FIFO dùng queue.
Độ phức tạp:
*V: total of vertices E: total of edges
Cách lưu trữ
Có 3 cách:
Ma trận kề (Adjacency matrix)
Tạo ma trận vuông kích thước . Phần tử ô đại diện có cạnh giữa node và hay không (0 là không, 1 là có). Đồ thị vô hướng thì đường chéo là 0 hết.
6 (đỉnh)
0 1 0 1 0 0
1 0 1 1 0 1
0 1 0 0 0 1
1 1 0 0 1 1
0 0 0 1 0 0
0 1 1 1 0 0
Cách lưu trữ đơn giản nhưng tốn bộ nhớ. Có những cạnh không tồn tại nhưng vẫn tốn bộ nhớ để lưu nó. Khả năng truy xuất cũng kém hơn, ví dụ muốn biết node 0 kết nối với những đỉnh nào thì phải dò hết hàng 0.
Danh sách cạnh (Edge list)
Lưu theo E cạnh. Ví dụ ở đây có 8 cạnh lưu 8 dòng.
6 8 <- 6 đỉnh, 8 cạnh
0 1
0 3
1 2
1 3
1 5
2 5
3 4
3 5
Cách lưu tiết kiệm bộ nhớ hơn tuy nhiên vẫn chưa giải quyết vấn đề duyệt xem node đó kề với node nào. Ví dụ tìm 1 kề với cái nào? 1 kề với 0, 2, 3, 5 (ví dụ trên đã sort đẹp rồi, ví dụ không theo thứ tự đẹp thì vẫn phải duyệt toàn bộ cạnh).
Danh sách kề (Adjacency list)
Lưu theo V đỉnh. Mỗi đỉnh sẽ có 1 danh sách các đỉnh kề với nó.
0: 1 3
1: 0 2 3 5
2: 1 5
3: 0 1 4 5
4: 3
5: 1 2 3
Có thể thấy nó là cải tiến của adjacency matrix. Loại bỏ đi các số 0 dư thừa (cạnh không tồn tại). Ngoài ra, cũng trực quan cho biết node nào kề với node nào.
Cách lưu này tiết kiệm bộ nhớ nhất. Cách lưu này cũng giải quyết được vấn đề duyệt.
*Note: thứ tự danh sách kề không nhất thiết tăng dần, lưu thứ tự nào cũng được. Vì các cạnh đều sẽ đi qua.
Cài đặt
- Chuẩn bị dữ liệu:
- Danh sách cạnh kề:
graph
- Mảng đánh dấu các đỉnh đã xét:
visited
- Mảng lưu đường đi:
path
.path[i]
nghĩa là đỉnh trước đỉnh là đỉnh nào trong đường đi ngắn nhất từ đỉnh gốc đến đỉnh . - Queue để lưu các đỉnh cần xét:
queue
- Khởi tạo dữ liệu:
visited
vàpath
khởi tạo giá trị ban đầu là 0queue
khởi tạo giá trị ban đầu là đỉnh gốc
- Duyệt:
- Lấy đỉnh đầu tiên trong
queue
ra (gần đỉnh gốc nhất) - Duyệt các đỉnh kề với đỉnh đó
- Nếu đỉnh kề chưa được xét thì đánh dấu đã xét và lưu vào
queue
- Lưu đỉnh đó vào
path
(đỉnh trước đỉnh đó là đỉnh đầu tiên trongqueue
) - Lặp lại bước 1
Muốn biết đường đi đi như thế nào thì nhìn vào mảng path
.
- Python
- Java
- C++
from queue import Queue
MAX = 100
V = None
E = None
visited = [False for i in range(MAX)]
path = [0 for i in range(MAX)]
graph = [[] for i in range(MAX)]
def BFS(s):
for i in range(V):
visited[i] = False
path[i] = -1
q = Queue()
visited[s] = True
q.put(s)
while not q.empty():
u = q.get()
for v in graph[u]:
if not visited[v]:
visited[v] = True # đôi khi có thể dùng cái khác đánh dấu mà ko cần visited luôn
q.put(v) # ví dụ cần lưu thông tin phụ thì thêm vô đây (dùng tuple)
path[v] = u # nếu bài toán ko cần tìm đường đi thì có thể bỏ
import java.util.Scanner;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
private static void BFS(int s) {
Queue<Integer> q = new LinkedList<>();
path = new ArrayList<>();
visited = new ArrayList<>();
for (int i = 0; i < V; i++) {
visited.add(false);
path.add(-1);
}
visited.set(s, true);
q.add(s);
while (!q.isEmpty()) {
int u = q.remove();
for (int i = 0; i < graph.get(u).size(); i++) {
int v = graph.get(u).get(i);
if (!visited.get(v)) {
visited.set(v, true);
path.set(v, u);
q.add(v);
}
}
}
}
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAX 100 // tùy bài toán mà thay đổi
int V, E;
bool visited[MAX];
int path[MAX];
vector<int> graph[MAX];
void BFS(int s) {
// Khởi tạo
for (int i = 0; i < V; i++) {
visited[i] = false; // các đỉnh chưa được ghé thăm
path[i] = -1; // và chưa có đường đi
}
queue<int> q;
visited[s] = true; // mặc định luôn có đường đi từ đỉnh gốc đến chính nó
q.push(s); // lưu vào hàng đợi
while (!q.empty()) {
int u = q.front(); // lấy đỉnh đầu tiên queue ra (gần đỉnh gốc nhất)
q.pop();
// duyệt các đỉnh kề với đỉnh u
for (int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i]; // lấy v là đỉnh kề với u
// nếu trước đây chưa có đường đi tới đỉnh v
// (nếu trước đây đã có đường đi tới đỉnh v thì đó là đường đi tốt hơn rồi)
if (!visited[v]) {
visited[v] = true;
q.push(v);
path[v] = u; // cập nhật đường đi: muốn tới v thì phải tới u trước
}
}
}
}
Thêm
Chứng minh đồ thị không liên thông
Khi 2 đỉnh cần tìm không có đường đi tới được nhau (ví dụ 2 đồ thị không liên thông).
Làm sao chứng minh được đường đi đó là ngắn nhất?
Hàm main
- Python
- Java
- C++
if __name__ == "__main__":
V, E = map(int, input().split())
for i in range(E):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
s = 0
f = 5
BFS(s)
printPath(s, f)
public class Main {
private static int V;
private static int E;
private static ArrayList<Integer> path;
private static ArrayList<Boolean> visited;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
V = sc.nextInt();
E = sc.nextInt();
graph = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < E; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
graph.get(u).add(v);
graph.get(v).add(u);
}
int s = 0;
int f = 5;
BFS(s);
printPath(s, f);
}
}
int main() {
int u, v;
cin >> V >> E;
for (int i = 0; i < E; i++) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
int s = 0;
int f = 5;
BFS(s);
printPath(s, f);
return 0;
}
In đường đi từ mảng lưu vết
C1: Khử đệ quy:
- Python
- Java
- C++
def printPath(s, f):
b = []
if f == s:
print(s)
return
if path[f] == -1:
print("No path")
return
while True:
b.append(f)
f = path[f]
if f == s:
b.append(s)
break
for i in range(len(b) - 1, -1, -1):
print(b[i], end=" ")
private static void printPath(int s, int f) {
if (f == s) {
System.out.println(s);
return;
}
if (path.get(f) == -1) {
System.out.println("No path");
return;
}
ArrayList<Integer> b = new ArrayList<>();
while (true) {
b.add(f);
f = path.get(f);
if (f == s) {
b.add(f);
break;
}
}
for (int i = b.size() - 1; i >= 0; i--) {
System.out.print(b.get(i) + " ");
}
}
void printPath(int s, int f) {
int b[MAX]; // mảng lưu đường đi
int m = 0; // số đỉnh trong đường đi
if (f == s) {
cout << s;
return;
}
if (path[f] == -1) {
cout << "No path";
return;
}
while (true) {
b[m++] = f;
f = path[f];
if (f == s) {
b[m++] = s;
break;
}
}
for (int i = m - 1; i >= 0; i--) {
cout << b[i] << " ";
}
}
C2: Dùng đệ quy:
- Python
- Java
- C++
def printPathRecursion(s, f):
if s == f:
print(f, end=" ")
else:
if path[f] == -1:
print("No path")
else:
printPathRecursion(s, path[f])
print(f, end=" ")
private static void printPathRecursion(int s, int f) {
if (s == f)
System.out.print(f + " ");
else {
if (path.get(f) == -1)
System.out.println("No path");
else {
printPathRecursion(s, path.get(f));
System.out.print(f + " ");
}
}
}
void printPathRecursion(int s, int f) {
if (s == f) {
cout << f << "";
}
else {
if (path[f] == -1) {
cout << "No path";
}
else {
printPathRecursion(s, path[f]);
cout << " " << f;
}
}
}
DFS (Depth-First Search)
Xài khi nào?
Tìm kiếm theo chiều sâu. Dùng trên đồ thị không trọng số (vô hướng hoặc có hướng). Nếu có trọng số thì trọng số các đường đi phải giống nhau (do thuật toán chỉ đếm số cạnh đi qua).
DFS luôn tìm được đường đi từ 1 đỉnh bất kỳ tới 1 đỉnh bất kỳ khác. Tuy nhiên, nó không chắc chắn tìm được đường đi ngắn nhất.
Mục tiêu khi dùng là để xét xem có đường đi hay không thôi. Hoặc dùng hỗ trợ bài toán khác. Muốn kết quả tốt nhất thì xài BFS. Nhiều bài toán BFS hay DFS đều như nhau.
Giới thiệu cơ chế
Khác với BFS giống như nhỏ giọt nước, DFS giống như đi mê cung, khi đi thì mình không biết mình sẽ đi đâu, về đâu. Mình sẽ chọn 1 đường đi tiếp hoài tới khi đường cụt hoặc lối ra.
Độ phức tạp:
*V: total of vertices E: total of edges
Cách lưu trữ
Cài đặt
Vì DFS xài stack nên có 2 cách cài. Không dùng đệ quy (giống BFS), xài stack:
- Python
- Java
- C++
MAX = 100
V = None
E = None
visited = [False for i in range(MAX)]
path = [0 for i in range(MAX)]
graph = [[] for i in range(MAX)]
def DFS(src):
for i in range(V):
visited[i] = False
path[i] = -1
s = []
visited[src] = True
s.append(src)
while len(s) > 0:
u = s.pop()
for v in graph[u]:
if not visited[v]:
visited[v] = True
s.append(v)
path[v] = u
import java.util.*;
public class Main {
private static ArrayList<ArrayList<Integer>> graph;
private static int V;
private static int E;
private static ArrayList<Boolean> visited;
private static ArrayList<Integer> path;
private static void DFS(int src){
Stack<Integer> s = new Stack<>();
visited = new ArrayList<>();
path = new ArrayList<>();
for (int i = 0; i < V; i++) {
visited.add(false);
path.add(-1);
}
visited.set(src, true);
s.add(src);
while(!s.empty()) {
int u = s.pop();
for (int i = 0; i < graph.get(u).size(); i++) {
int v = graph.get(u).get(i);
if (!visited.get(v)) {
visited.set(v, true);
s.add(v);
path.set(v, u);
}
}
}
}
}
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
#define MAX 100
int V;
int E;
vector<int> graph[MAX];
bool visited[MAX];
int path[MAX];
void DFS(int src){
for(int i = 0; i < V; i++){
visited[i] = false;
path[i] = -1;
}
stack<int> s;
visited[src] = true;
s.push(src);
while(!s.empty()) {
int u = s.top();
s.pop();
for(int i = 0; i < graph[u].size(); i++){
int v = graph[u][i];
if(!visited[v]){
visited[v] = true;
s.push(v);
path[v] = u;
}
}
}
}
Dùng đệ quy:
- Python
- Java
- C++
def DFSRecursion(s):
visited[s] = True
for v in graph[s]:
if not visited[v]:
path[v] = s
DFSRecursion(v)
private static void DFSRecursion(int s) {
visited.set(s, true);
for (int i = 0; i < graph.get(s).size(); i++) {
int v = graph.get(s).get(i);
if (!visited.get(v)) {
path.set(v, s);
DFSRecursion(v);
}
}
}
void DFSRecursion(int s) {
visited[s] = true;
for (int i = 0; i < graph[s].size(); i++) {
int v = graph[s][i];
if (!visited[v]) {
path[v] = s;
DFSRecursion(v);
}
}
}
Note that BFS cho đường đi tốt hơn DFS stack hoặc DFS recursion. Do DFS stack & recursion sử dụng cấu trúc khác nhau nên có thể cho đường đi khác nhau (k chắc chắn stack sẽ tốt hơn recursion & ngc lại).
Thêm
Hàm main
- Python
- Java
- C++
if __name__ == "__main__":
V, E = map(int, input().split())
for i in range(E):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
s = 0
f = 5
DFS(s)
printPath(s, f)
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
V = sc.nextInt();
E = sc.nextInt();
graph = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < E; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
graph.get(u).add(v);
graph.get(v).add(u);
}
int s = 0, f = 5;
DFS(s);
printPath(s, f);
}
int main() {
int u, v;
cin >> V >> E;
for (int i = 0; i < E; i++) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
int s = 0;
int f = 5;
DFS(s);
printPath(s, f);
return 0;
}
Nếu xài DFS đệ quy thì cần khởi tạo lại mảng visited
và path
trước khi gọi đệ
quy (vì để trong đệ quy thì mỗi lần gọi lại reset trạng thái)
- Python
- Java
- C++
if __name__ == "__main__":
V, E = map(int, input().split())
for i in range(E):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
s = 0
f = 5
for i in range(V):
visited[i] = False
path[i] = -1
DFSRecursion(s)
printPath(s, f)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
V = sc.nextInt();
E = sc.nextInt();
graph = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < E; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
graph.get(u).add(v);
graph.get(v).add(u);
}
int s = 0, f = 5;
path = new ArrayList<>();
visited = new ArrayList<>();
for (int i = 0; i < V; i++) {
visited.add(false);
path.add(-1);
}
DFSRecursion(s);
printPath(s, f);
}
int main() {
int u, v;
cin >> V >> E;
for (int i = 0; i < E; i++) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
int s = 0;
int f = 5;
for (int i = 0; i < V; i++) {
visited[i] = false;
path[i] = -1;
}
DFSRecursion(s);
printPath(s, f);
return 0;
}