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 $\rightarrow$ 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 $\rightarrow$ 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 $\rightarrow$ xử lý thằng nào lưu trước $\rightarrow$ FIFO $\rightarrow$ dùng queue.

Độ phức tạp: $O(V + E)$

*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 $V^2$. Phần tử ô $[i][j]$ đại diện có cạnh giữa node $i$ và $j$ 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 $\rightarrow$ 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

1. 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 $i$ là đỉnh nào trong đường đi ngắn nhất từ đỉnh gốc đến đỉnh $i$.
• Queue để lưu các đỉnh cần xét: queue

2. Khởi tạo dữ liệu:

• visited và path khởi tạo giá trị ban đầu là 0
• queue khởi tạo giá trị ban đầu là đỉnh gốc

3. 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 trong queue)
• 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

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ỏ

Java

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);
      }
    }
  }
}

C++

#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

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)

Java

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);
  }
}

C++

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

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=" ")

Java

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) + " ");
  }
}

C++

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

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=" ")

Java

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 + " ");
    }
  }
}

C++

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.

$\rightarrow$ 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: $O(V + E)$

*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

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

Java

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);
        }
      }
    }
  }
}

C++

#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

def DFSRecursion(s):
  visited[s] = True
  for v in graph[s]:
    if not visited[v]:
      path[v] = s
      DFSRecursion(v)

Java

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);
    }
  }
}

C++

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

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)

Java

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);
}

C++

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

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)

Java

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);
}

C++

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;
}