Phương pháp duyệt theo chiều rộng (Breadth-First Search - BFS)

• Thuật toán:
  • Khởi tạo hàng đợi rỗng
  • Thêm đỉnh nguồn vào , đặt là đã thăm
  • Lặp cho đến khi rỗng:
    • Lấy đỉnh khỏi
    • Thao tác với đỉnh
    • Thêm các đỉnh kề với mà chưa được thăm vào , đánh dấu các đỉnh là đã thăm
• Độ phức tạp: , trong đó
  • Khởi tạo:
  • Khi làm việc với hàng đợi, ta đưa các đỉnh lần lượt vào và ra khỏi hàng đợi, nên thời gian là
  • Khi làm việc với danh sách kề để lấy đỉnh cho vào hàng đợi, ta duyệt qua tất cả các đỉnh, thời gian là
• Cây BFS: là đồ thị con của có được khi thực hiện BFS
• Việc thực hiện BFS sẽ thăm đỉnh với đường đi ngắn nhất về số cạnh

Phương pháp duyệt theo chiều sâu (Depth-First Search - DFS)

• Thuật toán:
  • Đặt tất cả các đỉnh là chưa thăm
  • Từ đỉnh đầu tiên:
    • Đặt đỉnh hiện tại là đã thăm
    • Thao tác với đỉnh hiện tại
    • Duyệt DFS với tất cả các đỉnh kề với nó
• Thời gian bắt đầu và kết thúc duyệt
  • Xét biến , bắt đầu bằng 0
  • Mỗi lần thăm một đỉnh , tăng lên 1, đặt
  • Khi đã thăm hết các đỉnh kề với , tăng lên 1, đặt
• Bổ đề các khoảng cách lồng nhau: Trong quá trình duyệt DFS:
  • là đỉnh con của nếu đoạn nằm trong đoạn
  • là đỉnh tổ tiên của nếu đoạn chứa đoạn
  • Nếu hai đoạn trên rời nhau, ta gọi và là hai đỉnh không có quan hệ họ hàng
• Phân loại cạnh:
  • Cạnh cây là cạnh đi từ tổ tiên đến đỉnh con đầu tiên của nó
  • Cạnh tới là cạnh đi từ tổ tiên đến con cháu, khác cạnh cây
  • Cạnh ngược là cạnh đi từ con cháu đến tổ tiên
  • Cạnh vòng là cạnh kề với hai đỉnh không có quan hệ họ hàng

Ứng dụng của DFS và BFS

• Kiểm tra tính liên thông:
  • Nếu ta duyệt DFS/BFS đến khi tất cả các đỉnh đều được thăm, mỗi lần một đỉnh được gọi DFS và BFS để bắt đầu duyệt, ta có một thành phần liên thông
• Tìm đường đi
• Phát hiện chu trình:
  • Đồ thị không có chu trình nếu và chỉ nếu việc duyệt DFS không phát hiện cạnh ngược
• Xét tính liên thông mạnh:
  • Từ một đỉnh nào đó, duyệt DFS, nếu có đỉnh chưa được duyệt, đồ thị không liên thông
  • Đảo ngược hướng tất cả các cạnh trên đồ thị, lặp lại bước trên
  • Nếu qua hai bước đều không tìm thấy đỉnh chưa được duyệt, ta có đồ thị liên thông mạnh
• Định hướng đồ thị:
  • Xét đồ thị vô hướng liên thông
  • Duyệt DFS trên , phân loại cạnh và chọn ra cạnh cây, cạnh tới và cạnh ngược, lập thành đồ thị con .
  • định hướng được nếu liên thông mạnh