[DSA] Graph - P1

Ha Ngoc HieuHa Ngoc Hieu
41 min read

Table of contents

Chủ đề của chúng ta là về đồ thị vô hướng (undirected graphs) và các thuật toán xử lý chúng. Đây là một mô hình cực kỳ phổ biến, được dùng trong vô vàn ứng dụng thực tế.

I. Giới thiệu về Đồ thị (Graph)

1. Giới thiệu về Đồ thị Vô hướng

  • Đồ thị vô hướng là gì?

    • Rất đơn giản: Nó là một tập hợp các đỉnh (vertices) được nối với nhau từng cặp bởi các cạnh (edges).

    • Hãy tưởng tượng các đỉnh như những địa điểm (như thành phố, nhà ga, máy tính, hay thậm chí là con người), còn các cạnh là những kết nối giữa chúng (như đường đi, đường ray, dây cáp mạng, hay mối quan hệ bạn bè).

    • "Vô hướng" nghĩa là cạnh nối hai đỉnh A và B thì không có chiều cụ thể, đi từ A đến B cũng như từ B đến A (ví dụ: đường hai chiều, mối quan hệ bạn bè).

    • Ví dụ bản đồ tàu điện ngầm: mỗi nhà ga là một đỉnh, và nếu có đường tàu chạy thẳng giữa hai ga thì có một cạnh nối chúng.

  • Tại sao chúng ta học về đồ thị và thuật toán đồ thị?

    • Ứng dụng thực tế siêu nhiều: Từ mạng máy tính (Internet), mạng xã hội (Facebook), bản đồ đường đi, mạng lưới sinh học (tương tác protein), đến phân tích mối quan hệ trong kinh doanh, xã hội học... đâu đâu cũng có thể mô hình hóa bằng đồ thị.

    • Thuật toán đa dạng và quan trọng: Vì có nhiều ứng dụng nên cũng có hàng trăm thuật toán đồ thị đã được phát triển, từ đơn giản đến rất phức tạp. Hiểu các thuật toán này giúp chúng ta giải quyết các vấn đề thực tế hiệu quả.

    • Là một cấu trúc trừu tượng thú vị: Bản thân đồ thị, dù định nghĩa đơn giản, lại tạo ra những cấu trúc rất phức tạp và hấp dẫn để nghiên cứu.

    • Là một nhánh quan trọng của Khoa học Máy tính: Lý thuyết đồ thị và thuật toán đồ thị là một phần cốt lõi, đầy thử thách.

  • Ví dụ về các đồ thị "khủng":

    • Mạng Internet: Các máy tính/thiết bị mạng là đỉnh, kết nối vật lý/logic là cạnh. Đồ thị này khổng lồ và liên tục thay đổi.

    • Mạng xã hội (Facebook): Người dùng là đỉnh, quan hệ bạn bè là cạnh. Cũng cực lớn và động.

    • Mạng lưới sinh học: Protein là đỉnh, tương tác giữa chúng là cạnh. Giúp hiểu các quá trình sinh học.

    • Mạng lưới giao thông, mạng lưới quan hệ,...

\=> Đồ thị rất linh hoạt, có thể mô tả đủ thứ, và thường có kích thước rất lớn, cấu trúc phức tạp. Thách thức của chúng ta là tìm ra các thuật toán hiệu quả để phân tích và hiểu được cấu trúc của chúng.

2. Một số thuật ngữ cơ bản khi làm việc với đồ thị (Rất quan trọng!)

  • Đỉnh (Vertex): Các đối tượng trong đồ thị (điểm đen trong hình vẽ).

  • Cạnh (Edge): Đường nối giữa hai đỉnh (đường kẻ đen).

  • Đường đi (Path): Một chuỗi các đỉnh liên tiếp được nối với nhau bằng các cạnh.

    Ví dụ: đi từ A -> B -> C -> D.

  • Chu trình (Cycle): Một đường đi mà điểm bắt đầu và điểm kết thúc là cùng một đỉnh.

    Ví dụ: A -> B -> C -> A.

  • Liên thông (Connected): Hai đỉnh được gọi là liên thông nếu có ít nhất một đường đi giữa chúng.

  • Thành phần liên thông (Connected Component): Một nhóm các đỉnh trong đồ thị mà mọi cặp đỉnh trong nhóm đều liên thông với nhau, và không có cạnh nào nối từ một đỉnh trong nhóm này tới một đỉnh bên ngoài nhóm (nói nôm na là một "mảnh" riêng biệt của đồ thị). Một đồ thị có thể có một hoặc nhiều thành phần liên thông.

3. Một số bài toán thường gặp trên đồ thị

Dựa trên các khái niệm trên, có rất nhiều bài toán thú vị và hữu ích:

  • Tìm đường đi (Pathfinding): Cho hai đỉnh A và B, có đường đi nào giữa chúng không? (Ví dụ: Liệu có thể gửi tin từ máy A đến máy B trên Internet?)

  • Đường đi ngắn nhất (Shortest Path): Nếu có đường đi, đâu là đường đi có tổng "chiều dài" (số cạnh hoặc trọng số cạnh) nhỏ nhất? (Ví dụ: Tìm đường đi nhanh nhất trên bản đồ).

  • Phát hiện chu trình (Cycle Detection): Đồ thị có chứa chu trình nào không? (Ví dụ: Trong mạch điện, chu trình có thể gây đoản mạch).

  • Tính liên thông (Connectivity): Toàn bộ đồ thị có liên thông không? (Tức là mọi cặp đỉnh đều có đường đi tới nhau).

  • Cây khung nhỏ nhất (Minimum Spanning Tree - MST): Tìm một tập hợp các cạnh sao cho tất cả các đỉnh đều được kết nối với nhau và tổng "chiều dài" (trọng số) của các cạnh này là nhỏ nhất có thể. (Ví dụ: Xây dựng mạng lưới cáp quang nối các thành phố với chi phí thấp nhất).

  • Các bài toán phức tạp hơn:

    • Euler Tour: Tìm một chu trình đi qua mỗi cạnh đúng một lần.

    • Hamilton Tour: Tìm một chu trình đi qua mỗi đỉnh đúng một lần.

    • Vẽ đồ thị (Graph Drawing): Liệu có thể vẽ đồ thị trên mặt phẳng mà không có cạnh nào cắt nhau không?

    • Đồng cấu đồ thị (Graph Isomorphism): Hai đồ thị trông khác nhau (tên đỉnh khác, vẽ khác) nhưng có thực sự cùng cấu trúc không?

4. Thách thức về độ khó

Điều quan trọng cần nhận thức ngay từ đầu là: các bài toán đồ thị có độ khó rất khác nhau!

  • Có những bài toán rất dễ giải, thuật toán đơn giản và hiệu quả (như tìm đường đi, kiểm tra liên thông).

  • Có những bài toán cực kỳ khó, hiện tại chưa có thuật toán nào hiệu quả cho các đồ thị lớn (như Hamilton Tour).

  • Thậm chí có những bài toán mà người ta vẫn chưa biết chắc chắn nó khó đến mức nào!

Vì vậy, khi tiếp cận một vấn đề về đồ thị, việc đầu tiên là phải hiểu rõ bài toán và nhận biết được độ khó của nó để tìm hướng giải quyết phù hợp.

II. Graph API

Bây giờ chúng ta sẽ đi sâu hơn vào việc làm thế nào để "biểu diễn" đồ thị trong máy tính và cách xây dựng một "giao diện" chuẩn (gọi là API - Application Programming Interface) để các thuật toán xử lý đồ thị có thể sử dụng nhé. Đây là bước cực kỳ quan trọng để chúng ta có thể viết code xử lý đồ thị một cách hiệu quả và có tổ chức.

1. Tại sao cần API và cách biểu diễn đồ thị?

  • Ý tưởng cốt lõi: Thay vì mỗi thuật toán lại phải tự định nghĩa cách lưu trữ đồ thị, chúng ta sẽ xây dựng một lớp (class) Graph với các phương thức (methods) cơ bản. Các thuật toán xử lý đồ thị (gọi là clients) sẽ chỉ cần gọi các phương thức này mà không cần quan tâm chi tiết bên trong đồ thị được lưu trữ như thế nào. Đây chính là sức mạnh của tính trừu tượng (abstraction).

  • Về việc vẽ đồ thị: Bạn có thể vẽ một đồ thị bằng nhiều cách khác nhau trên giấy, và đôi khi hai hình vẽ trông rất khác nhau nhưng lại biểu diễn cùng một đồ thị. Hình vẽ giúp ta có cảm nhận ban đầu, nhưng đừng quá phụ thuộc vào nó, cách biểu diễn dữ liệu trong máy tính mới là thứ quyết định.

  • Biểu diễn đỉnh (Vertices): Để cho đơn giản và hiệu quả, chúng ta quy ước dùng các số nguyên từ 0 đến V-1 để đặt tên cho V đỉnh trong đồ thị.

    • Tại sao? Vì làm vậy cho phép chúng ta dùng mảng (array) để truy cập thông tin liên quan đến đỉnh rất nhanh (dùng chỉ số mảng chính là tên đỉnh).

    • Vậy nếu tên đỉnh là tên thành phố, tên người thì sao? Chúng ta có thể dùng một cấu trúc dữ liệu khác gọi là Bảng ký hiệu (Symbol Table) - để chuyển đổi giữa tên thật (chuỗi ký tự) và tên số nguyên (0 đến V-1) này. Trong phần này, ta tạm giả định đã có các đỉnh được đánh số sẵn rồi.

  • Lưu ý nhỏ: Đồ thị trong thực tế có thể có cạnh song song (nhiều cạnh nối cùng 2 đỉnh) hoặc khuyên (cạnh nối một đỉnh với chính nó - self-loop). Cách biểu diễn chúng ta chọn cần phải tính đến hoặc làm rõ giới hạn của nó.

2. Graph API - Giao diện lập trình ứng dụng cho Đồ thị

Đây là bộ "hợp đồng" các phương thức mà lớp Graph của chúng ta sẽ cung cấp:

  • __init__(self, V): Hàm khởi tạo (constructor) để tạo ra một đồ thị rỗng có V đỉnh (chưa có cạnh nào).

  • addEdge(self, v: int, w: int): Thêm một cạnh nối giữa đỉnh v và đỉnh w. Vì là đồ thị vô hướng, cạnh này là hai chiều.

  • V(self)→ int: Trả về số lượng đỉnh của đồ thị.

  • E(self)→ int: Trả về số lượng cạnh của đồ thị.

  • adj(v: int): Trả về một danh sách tất cả các đỉnh kề với đỉnh v (các đỉnh có cạnh nối trực tiếp tới v).

3. Các cách biểu diễn đồ thị bên trong (Representations)

Bây giờ mới là phần "ruột" bên trong lớp Graph. Làm sao để lưu trữ dữ liệu hiệu quả?

  • Danh sách cạnh (Set of Edges): Đơn giản là lưu một danh sách (mảng hoặc danh sách liên kết) chứa tất cả các cặp đỉnh (v, w) biểu diễn cạnh.

    • Nhược điểm: Rất không hiệu quả để tìm các đỉnh kề với một đỉnh v (phương thức adj(v)). Bạn phải duyệt qua toàn bộ danh sách cạnh để tìm. Không khả thi cho đồ thị lớn.

  • Ma trận kề (Adjacency Matrix): Dùng một ma trận vuông V x V, gọi là adjMatrix. adjMatrix[v][w] sẽ là true (hoặc 1) nếu có cạnh nối v và w, và false (hoặc 0) nếu không.

    • Ưu điểm: Kiểm tra xem có cạnh giữa v và w không rất nhanh (O(1)).

    • Nhược điểm:

      1. Tốn bộ nhớ khủng khiếp: V^2 phần tử. Nếu V là 1 triệu, bạn cần 1 triệu triệu (10^12) ô nhớ, quá lớn!

      2. Tìm các đỉnh kề với v (adj(v)) vẫn chậm: bạn phải duyệt cả hàng v của ma trận (O(V) thời gian), dù cho đỉnh v có rất ít hàng xóm (đồ thị thưa - sparse).

    • \=> Ít được dùng trong thực tế cho các đồ thị lớn, thưa.

  • Danh sách kề (Adjacency List): Đây là cách phổ biến và hiệu quả nhất trong hầu hết các trường hợp.

    • Cách hoạt động: Dùng một mảng gồm V phần tử. Phần tử thứ v của mảng (adjLists[v]) sẽ trỏ đến một danh sách (thường dùng danh sách liên kết hoặc cấu trúc Bag - Túi) chứa tất cả các đỉnh kề với v.

    • Ví dụ: Nếu đỉnh 4 nối với 5, 6, 3 thì adjLists[4] sẽ là một danh sách chứa [5, 6, 3].

    • Ưu điểm:

      1. Tiết kiệm bộ nhớ: Chỉ lưu trữ các cạnh thực sự tồn tại. Tổng bộ nhớ tỉ lệ với V + E (số đỉnh + số cạnh), tốt hơn nhiều so với V^2 của ma trận kề, đặc biệt với đồ thị thưa (số cạnh E nhỏ hơn nhiều so với V^2).

      2. Tìm hàng xóm nhanh: Duyệt qua các đỉnh kề với v (adj(v)) chỉ mất thời gian tỉ lệ với bậc của v (số hàng xóm thực tế của v), rất nhanh nếu bậc nhỏ.

    • \=> Đây là cách chúng ta sẽ chọn để cài đặt API ở trên.

4. Cài đặt chi tiết dùng Danh sách kề (Adjacency List Implementation)

class Graph:
    """
    Lớp biểu diễn đồ thị vô hướng sử dụng Danh sách kề.
    Các đỉnh được đặt tên bằng số nguyên từ 0 đến V-1.
    """
    def __init__(self, V):
        """
        Khởi tạo đồ thị rỗng với V đỉnh.
        Args:
            V (int): Số lượng đỉnh.
        Raises:
            ValueError: Nếu V < 0.
        """
        if V < 0:
            raise ValueError("Số lượng đỉnh phải không âm")
        # Sử dụng dấu gạch dưới (_) để ám chỉ đây là các thuộc tính "nội bộ"
        self._V = V  # Số đỉnh
        self._E = 0  # Số cạnh, khởi tạo là 0
        # Tạo một list chứa V list rỗng khác nhau: [[],[],[],[]...]
        # Đây là cấu trúc cốt lõi: mảng (list) các danh sách kề
        self._adj = [[] for _ in range(V)]

    # --- Các phương thức cơ bản của API ---

    @property
    def V(self):
        """Trả về số lượng đỉnh."""
        return self._V

    @property
    def E(self):
        """Trả về số lượng cạnh."""
        return self._E

    def _validate_vertex(self, v):
        """Kiểm tra xem đỉnh v có hợp lệ không."""
        if not (0 <= v < self._V):
            raise ValueError(f"Đỉnh {v} không hợp lệ (phải từ 0 đến {self._V - 1})")

    def add_edge(self, v, w):
        """
        Thêm cạnh vô hướng v-w vào đồ thị.
        Args:
            v (int): Đỉnh thứ nhất.
            w (int): Đỉnh thứ hai.
        Raises:
            ValueError: Nếu v hoặc w không phải là đỉnh hợp lệ.
        """
        self._validate_vertex(v)
        self._validate_vertex(w)
        # Thêm w vào danh sách kề của v
        self._adj[v].append(w)
        # Thêm v vào danh sách kề của w (vì đồ thị vô hướng)
        self._adj[w].append(v)
        self._E += 1 # Tăng số cạnh

    def adj(self, v):
        """
        Trả về danh sách các đỉnh kề với đỉnh v.
        Args:
            v (int): Đỉnh cần lấy danh sách kề.
        Returns:
            list: Một list chứa các đỉnh kề với v. Trả về list gốc,
                  cho phép duyệt hiệu quả.
        Raises:
            ValueError: Nếu v không phải là đỉnh hợp lệ.
        """
        self._validate_vertex(v)
        # Trả về list các hàng xóm, list này là iterable
        return self._adj[v]

5. Tại sao Danh sách kề lại "thắng"?

Trong thực tế, hầu hết các đồ thị lớn (mạng xã hội, internet,...) đều là đồ thị thưa (sparse), nghĩa là số cạnh E nhỏ hơn rất nhiều so với số cạnh tối đa có thể có (~V^2).

  • Danh sách kề phù hợp nhất vì:

    • Không gian lưu trữ V + E là chấp nhận được.

    • Thời gian cho thao tác quan trọng nhất là duyệt hàng xóm (adj(v)) tỉ lệ với bậc của v, rất nhanh với các đỉnh có bậc nhỏ (phổ biến trong đồ thị thưa).

  • Ma trận kề tốn quá nhiều bộ nhớ (V^2) và duyệt hàng xóm chậm (O(V)).

  • Danh sách cạnh duyệt hàng xóm quá chậm (O(E)).

6. Một số hàm khác để xử lý với đồ thị

Chúng ta có thể viết các hàm tĩnh (static methods) hữu ích:

  • degree(G: Graph, v: int) → int: Tính bậc của đỉnh v (số cạnh nối tới v). Chỉ cần đếm số phần tử trong G.adj(v).

  • maxDegree(G: Graph) → int: Tìm bậc lớn nhất trong toàn đồ thị. Duyệt qua mọi đỉnh, tính bậc của nó và giữ lại giá trị lớn nhất.

  • avgDegree(Graph G) → double: Tính bậc trung bình. Cách đơn giản là 2.0 * G.E() / G.V() (vì mỗi cạnh đóng góp vào bậc của 2 đỉnh).

  • numberOfSelfLoops(Graph G)→ int: Đếm số khuyên. Duyệt qua mọi đỉnh v, rồi duyệt qua các đỉnh w kề với v. Nếu w == v thì đó là khuyên. (Nhớ chia 2 kết quả cuối vì addEdge thêm khuyên 2 lần vào danh sách kề).

      class Graph:
  # --- Các phương thức khởi tạo và phương thúc cơ bản của Graph ---
  # ...

  # --- Các phương thức phụ trợ ---
      def degree(self, v):
          """
          Trả về bậc (số hàng xóm) của đỉnh v.
          Args:
              v (int): Đỉnh cần tính bậc.
          Returns:
              int: Bậc của đỉnh v.
          Raises:
              ValueError: Nếu v không phải là đỉnh hợp lệ.
          """
          self._validate_vertex(v)
          return len(self._adj[v]) # Bậc chính là độ dài danh sách kề

      def __str__(self):
          """Biểu diễn đồ thị dưới dạng chuỗi để print()."""
          s = f"{self._V} đỉnh, {self._E} cạnh\n"
          for v in range(self._V):
              # Nối các đỉnh kề thành chuỗi, cách nhau bởi dấu cách
              neighbors = " ".join(map(str, self._adj[v]))
              s += f"{v}: {neighbors}\n"
          return s

      def __repr__(self):
          """Biểu diễn chính thức hơn, thường dùng khi debug."""
          return f"Graph(V={self._V}, E={self._E})"

6. Cài đặt chi tiết dùng Danh sách kề đầy đủ

import sys

class Graph:
    """
    Lớp biểu diễn đồ thị vô hướng sử dụng Danh sách kề.
    Các đỉnh được đặt tên bằng số nguyên từ 0 đến V-1.
    """
    def __init__(self, V):
        """
        Khởi tạo đồ thị rỗng với V đỉnh.
        Args:
            V (int): Số lượng đỉnh.
        Raises:
            ValueError: Nếu V < 0.
        """
        if V < 0:
            raise ValueError("Số lượng đỉnh phải không âm")
        # Sử dụng dấu gạch dưới (_) để ám chỉ đây là các thuộc tính "nội bộ"
        self._V = V  # Số đỉnh
        self._E = 0  # Số cạnh, khởi tạo là 0
        # Tạo một list chứa V list rỗng khác nhau: [[],[],[],[]...]
        # Đây là cấu trúc cốt lõi: mảng (list) các danh sách kề
        self._adj = [[] for _ in range(V)]

    # --- Các phương thức cơ bản của API ---

    @property
    def V(self):
        """Trả về số lượng đỉnh."""
        return self._V

    @property
    def E(self):
        """Trả về số lượng cạnh."""
        return self._E

    def _validate_vertex(self, v):
        """Kiểm tra xem đỉnh v có hợp lệ không."""
        if not (0 <= v < self._V):
            raise ValueError(f"Đỉnh {v} không hợp lệ (phải từ 0 đến {self._V - 1})")

    def add_edge(self, v, w):
        """
        Thêm cạnh vô hướng v-w vào đồ thị.
        Args:
            v (int): Đỉnh thứ nhất.
            w (int): Đỉnh thứ hai.
        Raises:
            ValueError: Nếu v hoặc w không phải là đỉnh hợp lệ.
        """
        self._validate_vertex(v)
        self._validate_vertex(w)
        # Thêm w vào danh sách kề của v
        self._adj[v].append(w)
        # Thêm v vào danh sách kề của w (vì đồ thị vô hướng)
        self._adj[w].append(v)
        self._E += 1 # Tăng số cạnh

    def adj(self, v):
        """
        Trả về danh sách các đỉnh kề với đỉnh v.
        Args:
            v (int): Đỉnh cần lấy danh sách kề.
        Returns:
            list: Một list chứa các đỉnh kề với v. Trả về list gốc,
                  cho phép duyệt hiệu quả.
        Raises:
            ValueError: Nếu v không phải là đỉnh hợp lệ.
        """
        self._validate_vertex(v)
        # Trả về list các hàng xóm, list này là iterable
        return self._adj[v]

    # --- Các phương thức phụ trợ ---

    def degree(self, v):
        """
        Trả về bậc (số hàng xóm) của đỉnh v.
        Args:
            v (int): Đỉnh cần tính bậc.
        Returns:
            int: Bậc của đỉnh v.
        Raises:
            ValueError: Nếu v không phải là đỉnh hợp lệ.
        """
        self._validate_vertex(v)
        return len(self._adj[v]) # Bậc chính là độ dài danh sách kề

    def __str__(self):
        """Biểu diễn đồ thị dưới dạng chuỗi để print()."""
        s = f"{self._V} đỉnh, {self._E} cạnh\n"
        for v in range(self._V):
            # Nối các đỉnh kề thành chuỗi, cách nhau bởi dấu cách
            neighbors = " ".join(map(str, self._adj[v]))
            s += f"{v}: {neighbors}\n"
        return s

    def __repr__(self):
        """Biểu diễn chính thức hơn, thường dùng khi debug."""
        return f"Graph(V={self._V}, E={self._E})"

# --- Ví dụ sử dụng (Client code) ---
if __name__ == '__main__':
    # Giả lập dữ liệu từ file tinyG.txt
    # V = 13
    # Edges: (0, 5), (4, 3), (0, 1), (9, 12), (6, 4), (5, 4), (0, 2),
    #        (11, 12), (9, 10), (0, 6), (7, 8), (9, 11), (5, 3)
    num_vertices = 13
    edges_data = [
        (0, 5), (4, 3), (0, 1), (9, 12), (6, 4), (5, 4), (0, 2),
        (11, 12), (9, 10), (0, 6), (7, 8), (9, 11), (5, 3)
    ]

    # Tạo đồ thị
    g = Graph(num_vertices)
    for v, w in edges_data:
        g.add_edge(v, w)

    # In thông tin đồ thị (sử dụng __str__)
    print("Biểu diễn đồ thị (Danh sách kề):")
    print(g)

    # In tất cả các cạnh (mỗi cạnh xuất hiện 2 lần)
    print("\nIn tất cả các cạnh (mỗi cạnh 2 lần):")
    for v_node in range(g.V):
        for w_node in g.adj(v_node):
            print(f"{v_node}-{w_node}")

    # Tính và in bậc của một vài đỉnh
    print(f"\nBậc của đỉnh 0: {g.degree(0)}")
    print(f"Bậc của đỉnh 5: {g.degree(5)}")
    print(f"Bậc của đỉnh 9: {g.degree(9)}")

    # Tính bậc lớn nhất
    max_deg = 0
    for v_node in range(g.V):
        max_deg = max(max_deg, g.degree(v_node))
    print(f"Bậc lớn nhất trong đồ thị: {max_deg}")

    # Tính bậc trung bình
    if g.V > 0:
      avg_deg = 2.0 * g.E / g.V
      print(f"Bậc trung bình của đồ thị: {avg_deg:.2f}") # Làm tròn 2 chữ số thập phân
    else:
      print("Đồ thị không có đỉnh.")

Kết luận:

Chúng ta đã xác định được một Graph API chuẩn và cách cài đặt hiệu quả nhất bằng Danh sách kề (Adjacency List). API này cung cấp các thao tác cơ bản, đặc biệt là adj(v) để duyệt các đỉnh kề, làm nền tảng vững chắc cho việc xây dựng các thuật toán xử lý đồ thị phức tạp hơn mà chúng ta sẽ tìm hiểu tiếp theo. Hiểu rõ cách biểu diễn này và API là chìa khóa để làm việc với đồ thị đó!

III. Depth-First Search - DFS

Tìm kiếm theo chiều sâu (Depth-First Search - DFS). Nghe tên có vẻ hàn lâm nhưng ý tưởng cốt lõi lại khá gần gũi, giống như cách chúng ta tìm đường trong mê cung vậy!

1. Ý tưởng cốt lõi: Khám phá mê cung

  • Giống như tìm đường trong mê cung: Tưởng tượng bạn đang ở cửa vào một mê cung và muốn tìm kho báu hoặc đơn giản là khám phá hết các ngõ ngách. Đồ thị có thể mô hình hóa mê cung này: mỗi ngã ba, ngã tư là một đỉnh, mỗi lối đi nối hai ngã rẽ là một cạnh.

  • Thuật toán Trémaux (Tìm đường bằng cuộn chỉ và phấn): Đây là một phương pháp cổ điển:

    1. Khi bạn đi vào một lối đi mới, hãy rải một sợi chỉ theo sau lưng (để biết đường quay lại).

    2. Đánh dấu (dùng phấn) vào các ngã rẽ và lối đi bạn đã đi qua.

    3. Tại một ngã rẽ, hãy ưu tiên chọn một lối đi chưa được đánh dấu. Cứ đi sâu vào lối đó.

    4. Nếu tại ngã rẽ, tất cả các lối đi đều đã được đánh dấu, nghĩa là bạn đã vào ngõ cụt hoặc quay lại chỗ cũ. Lúc này, hãy lần theo sợi chỉ để quay lui (backtrack) đến ngã rẽ trước đó và thử một lối đi khác chưa được đánh dấu từ ngã rẽ đó.

    5. Lặp lại quá trình này cho đến khi bạn khám phá hết các nơi có thể đến.

  • Mục tiêu của DFS: Giống như khám phá mê cung, mục tiêu chính của DFS là thăm tất cả các đỉnh có thể đến được từ một đỉnh xuất phát s, và đồng thời tìm ra một đường đi từ s đến các đỉnh đó.

2. DFS hoạt động trên đồ thị như thế nào? (Thuật toán đệ quy)

DFS thực hiện ý tưởng "đi sâu hết mức có thể" này bằng đệ quy (recursion):

  • Nguyên tắc:

    1. Bắt đầu từ đỉnh nguồn s. Đánh dấu s là "đã thăm".

    2. Nhìn vào danh sách các đỉnh kề với s.

    3. Với mỗi đỉnh kề w của s:

      • Nếu w chưa được thăm:

        • Ghi nhớ: "Tôi đến được w từ s" (để lát nữa biết đường quay lại hoặc tìm đường đi).

        • Gọi đệ quy: Bắt đầu thực hiện DFS từ đỉnh w (lặp lại bước 1 từ w).

      • Nếu w đã được thăm: Bỏ qua, xét đỉnh kề tiếp theo của s.

    4. Khi đã xét hết các đỉnh kề của s (tức là không còn đỉnh kề nào chưa thăm để đi tiếp từ s), quá trình DFS từ s kết thúc, hàm đệ quy quay lui (return).

  • "Chiều sâu" ở đâu? Vì thuật toán luôn ưu tiên đi tiếp vào một đỉnh kề chưa thăm (bằng cách gọi đệ quy ngay lập tức), nó có xu hướng đi sâu vào một nhánh của đồ thị cho đến khi không thể đi tiếp được nữa mới quay lui.

3. Design Pattern: Tách biệt Thuật toán và Dữ liệu

Thay vì nhét code DFS vào thẳng lớp Graph đã xây dựng trước đó, chúng ta áp dụng một "mẫu thiết kế" (design pattern) tốt hơn:

  • Tạo một lớp riêng: Ví dụ, lớp DepthFirstPaths. Lớp này chuyên trách nhiệm vụ tìm đường đi bằng DFS.

  • Hàm khởi tạo (Constructor): DepthFirstPaths(Graph G, int s) sẽ nhận vào đồ thị G và đỉnh nguồn s. Bên trong constructor này, nó sẽ:

    • Khởi tạo các cấu trúc dữ liệu cần thiết (sẽ nói ở dưới).

    • Gọi hàm dfs(G, s) để thực hiện toàn bộ quá trình duyệt đồ thị bắt đầu từ s.

    • Sau khi constructor chạy xong, đối tượng DepthFirstPaths đã chứa đủ thông tin về các đường đi từ s.

  • Cung cấp API cho Client: Lớp DepthFirstPaths cung cấp các phương thức công khai để các chương trình khác (clients) truy vấn kết quả:

    • hasPathTo(int v): Trả về True nếu có đường đi từ s đến v, False nếu không.

    • pathTo(int v): Trả về một đối tượng (ví dụ: list hoặc stack) chứa đường đi từ s đến v nếu tồn tại.

  • Lợi ích: Cách làm này giúp mã nguồn rõ ràng, dễ quản lý. Lớp Graph chỉ lo việc lưu trữ đồ thị, còn các lớp xử lý như DepthFirstPaths lo việc thực hiện thuật toán cụ thể. Tránh tạo ra một lớp Graph "khổng lồ" chứa hàng trăm thuật toán khác nhau (gọi là "fat interface").

4. Cấu trúc dữ liệu cần thiết cho DFS

Để cài đặt DFS và hỗ trợ truy vấn đường đi, chúng ta cần 2 mảng chính, được đánh chỉ số bằng tên đỉnh (0 đến V-1):

  • marked[]: Một mảng boolean. marked[v] = True nghĩa là đỉnh v đã được thăm, False là chưa. Giúp tránh việc thăm lại một đỉnh nhiều lần và rơi vào vòng lặp vô hạn.

  • edgeTo[]: Một mảng số nguyên. edgeTo[w] = v có nghĩa là: lần đầu tiên chúng ta thăm đỉnh w là đi từ đỉnh v. Mảng này chính là "cuộn chỉ" giúp chúng ta lần ngược lại đường đi từ bất kỳ đỉnh nào về đỉnh nguồn s. Nó ngầm định tạo thành một cây các đường đi gốc tại s.

5. Demo và Cách hoạt động (Tóm tắt ví dụ trong bài giảng)

  1. Khởi tạo: Bắt đầu DFS từ đỉnh 0. Tạo mảng marked (tất cả False) và edgeTo (chưa có gì).

  2. Thăm 0: marked[0] = True. edgeTo[0] không cần (vì là gốc).

  3. Xét hàng xóm của 0: Giả sử thứ tự là 6, 2, 1, 5.

    • Đi tới 6: 6 chưa thăm.

      • marked[6] = True.

      • edgeTo[6] = 0 (ghi nhớ đến 6 từ 0).

      • Gọi đệ quy dfs(G, 6).

  4. Thăm 6:

    • Xét hàng xóm của 6: 0, 4.

    • Xét 0: 0 đã thăm (marked[0] == True). Bỏ qua.

    • Xét 4: 4 chưa thăm.

      • marked[4] = True.

      • edgeTo[4] = 6.

      • Gọi đệ quy dfs(G, 4).

  5. Thăm 4:

    • Xét hàng xóm của 4: 5, 6, 3.

    • Xét 5: 5 chưa thăm.

      • marked[5] = True.

      • edgeTo[5] = 4.

      • Gọi đệ quy dfs(G, 5).

  6. Thăm 5:

    • Xét hàng xóm của 5: 3, 4, 0.

    • Xét 3: 3 chưa thăm.

      • marked[3] = True.

      • edgeTo[3] = 5.

      • Gọi đệ quy dfs(G, 3).

  7. Thăm 3:

    • Xét hàng xóm của 3: 5, 4.

    • Xét 5: Đã thăm. Bỏ qua.

    • Xét 4: Đã thăm. Bỏ qua.

    • Hết hàng xóm chưa thăm của 3 -> Kết thúc dfs(G, 3), quay lui về 5.

  8. Tiếp tục từ 5: (Đã xét 3 rồi)

    • Xét 4: Đã thăm. Bỏ qua.

    • Xét 0: Đã thăm. Bỏ qua.

    • Hết hàng xóm chưa thăm của 5 -> Kết thúc dfs(G, 5), quay lui về 4.

  9. Tiếp tục từ 4: (Đã xét 5 rồi)

    • Xét 6: Đã thăm. Bỏ qua.

    • Xét 3: Đã thăm. Bỏ qua.

    • Hết hàng xóm chưa thăm của 4 -> Kết thúc dfs(G, 4), quay lui về 6.

  10. Tiếp tục từ 6: (Đã xét 0 và 4 rồi)

    • Hết hàng xóm chưa thăm của 6 -> Kết thúc dfs(G, 6), quay lui về 0.

  11. Tiếp tục từ 0: (Đã xét 6 rồi)

    • Xét 2: 2 chưa thăm... (Tiếp tục tương tự)

    • ...

    • Xét 5: (Lúc này 5 đã được thăm từ nhánh 0->6->4->5) Đã thăm. Bỏ qua.

  12. Kết thúc: Khi quay lui về dfs(G, 0) và đã xét hết hàng xóm (6, 2, 1, 5), thuật toán hoàn tất.

6. Tìm lại đường đi (Sử dụng edgeTo[])

Sau khi DFS chạy xong (trong constructor), mảng edgeTo[] đã lưu vết đường đi. Để tìm đường từ s đến v:

  1. Kiểm tra hasPathTo(v) (chính là marked[v]). Nếu False, không có đường đi.

  2. Nếu True:

    • Dùng một Ngăn xếp (Stack).

    • Bắt đầu từ x = v.

    • Lặp:

      • Đẩy x vào Stack.

      • Nếu x == s, dừng lại.

      • Cập nhật x = edgeTo[x] (đi ngược về đỉnh trước đó).

    • Stack bây giờ chứa đường đi theo thứ tự ngược (từ v về s). Khi lấy ra từ Stack, ta sẽ được đường đi đúng thứ tự s -> ... -> v.

    • Thời gian tìm đường đi tỉ lệ với độ dài của đường đi đó.

7. Mã cài đặt (Logic chính)

# Bên trong lớp DepthFirstPaths
# Giả sử self._marked và self._edge_to đã được khởi tạo

def _dfs(self, G, v):
    """Hàm đệ quy thực hiện DFS từ đỉnh v."""
    self._marked[v] = True  # Đánh dấu v đã thăm
    # Duyệt qua các hàng xóm w của v
    for w in G.adj(v):
        # Nếu w chưa được thăm
        if not self._marked[w]:
            self._edge_to[w] = v # Ghi nhớ: đến w từ v
            self._dfs(G, w)      # Gọi đệ quy để thăm w

# Constructor sẽ gọi self._dfs(G, self.source)

Mã rất gọn gàng phải không? Sức mạnh nằm ở tư duy đệ quy và việc sử dụng đúng cấu trúc dữ liệu.

8. Đặc tính và Ứng dụng

  • Tìm mọi đỉnh có thể đến: DFS đảm bảo sẽ thăm tất cả các đỉnh liên thông với đỉnh nguồn s.

  • Thời gian chạy: Rất hiệu quả. Với biểu diễn danh sách kề, thời gian chạy tỉ lệ với V + E (tổng số đỉnh và số cạnh trong thành phần liên thông của s).

  • Không phải đường đi ngắn nhất: DFS đi "sâu" nên đường đi nó tìm ra có thể không phải là đường ngắn nhất (ví dụ về việc chuẩn bị cho buổi hẹn hò trong bài giảng).

  • Ứng dụng:

    • Kiểm tra tính liên thông giữa hai đỉnh.

    • Tìm các thành phần liên thông của đồ thị.

    • Phát hiện chu trình trong đồ thị.

    • Giải mê cung.

    • Thuật toán "Flood Fill" (như công cụ Magic Wand trong Photoshop để chọn vùng màu giống nhau - ví dụ về ảnh Taj Mahal).

Kết luận:

Depth-First Search (DFS) là một thuật toán nền tảng, mạnh mẽ dựa trên ý tưởng đơn giản là khám phá sâu một nhánh rồi mới quay lui. Bằng cách sử dụng đệ quy, mảng marked[] để đánh dấu và mảng edgeTo[] để lưu vết, DFS cho phép chúng ta duyệt đồ thị hiệu quả và giải quyết nhiều bài toán thực tế. Nắm vững DFS là một bước quan trọng trên con đường chinh phục các thuật toán đồ thị!

IV. Breadth-First Search - BFS

Tìm kiếm theo chiều sâu (DFS), chúng ta sẽ cùng khám phá một phương pháp duyệt đồ thị hoàn toàn khác biệt, đó là Tìm kiếm theo chiều rộng (Breadth-First Search - BFS).

BFS cũng giúp chúng ta đi thăm các đỉnh của đồ thị, nhưng cách đi và kết quả nó mang lại có những đặc tính rất khác so với DFS, và cực kỳ hữu ích cho nhiều loại ứng dụng khác nhau, đặc biệt là khi bạn quan tâm đến đường đi ngắn nhất.

1. Ý tưởng cốt lõi: Loang ra như vết dầu trên mặt nước

  • Khác biệt với DFS: Nếu DFS giống như việc lần mò sâu vào một ngõ hẻm trong mê cung cho đến khi cụt đường mới quay lại, thì BFS lại giống như việc bạn đứng ở điểm xuất phát và khám phá đồng thời tất cả các địa điểm chỉ cách bạn 1 bước chân, sau đó mới khám phá tất cả các địa điểm cách bạn 2 bước chân, rồi 3 bước chân,... cứ thế loang rộng ra.

  • Khám phá theo từng lớp (Layer by Layer): BFS duyệt qua các đỉnh theo từng "lớp" khoảng cách tính từ đỉnh nguồn s. Đầu tiên là lớp 0 (chỉ có s), rồi đến lớp 1 (tất cả các hàng xóm trực tiếp của s), rồi lớp 2 (hàng xóm của lớp 1 mà chưa được thăm),...

2. Cách BFS hoạt động: Sức mạnh của Hàng đợi (Queue)

BFS không dùng đệ quy như DFS, mà nó sử dụng một cấu trúc dữ liệu quan trọng là Hàng đợi (Queue), hoạt động theo nguyên tắc Vào trước - Ra trước (First-In, First-Out - FIFO).

  • Thuật toán:

    1. Khởi tạo:

      • Tạo một Hàng đợi (Queue) và cho đỉnh nguồn s vào hàng đợi.

      • Đánh dấu s là "đã thăm" (marked[s] = True).

      • (Thường có thêm) Ghi nhận khoảng cách từ s đến chính nó là 0 (distTo[s] = 0).

      • (Vẫn cần) Mảng edgeTo[] để lưu vết đường đi, khởi tạo edgeTo[s] không cần thiết.

    2. Vòng lặp (Khi hàng đợi còn chưa rỗng): a. Lấy ra (Dequeue): Lấy đỉnh v từ đầu hàng đợi. b. Xét hàng xóm: Với mỗi đỉnh kề w của v: * Nếu w chưa được thăm (!marked[w]): i. Đánh dấu w là đã thăm (marked[w] = True). ii. Ghi nhớ đường đi: edgeTo[w] = v (Tôi đến w từ v). iii. Tính khoảng cách: distTo[w] = distTo[v] + 1. iv. Cho vào hàng đợi (Enqueue): Cho w vào cuối hàng đợi. * Nếu w đã được thăm: Bỏ qua.

    3. Kết thúc: Khi hàng đợi rỗng, nghĩa là đã thăm hết các đỉnh có thể đến được từ s.

3. Demo và Cách hoạt động

(Dùng ví dụ 6 đỉnh, 8 cạnh)

  1. Khởi tạo: Queue = [0], marked[0]=T, edgeTo[], distTo[0]=0.

  2. Dequeue 0:

    • Hàng xóm: 2, 1, 5 (thứ tự tùy cách lưu).

    • Xét 2: Chưa thăm -> marked[2]=T, edgeTo[2]=0, distTo[2]=1, Enqueue 2. Queue = [2].

    • Xét 1: Chưa thăm -> marked[1]=T, edgeTo[1]=0, distTo[1]=1, Enqueue 1. Queue = [2, 1].

    • Xét 5: Chưa thăm -> marked[5]=T, edgeTo[5]=0, distTo[5]=1, Enqueue 5. Queue = [2, 1, 5].

    • Xong với 0.

  3. Dequeue 2: (Đỉnh ở đầu queue bây giờ là 2)

    • Hàng xóm: 0, 1, 3, 4.

    • Xét 0: Đã thăm (marked[0]=T). Bỏ qua.

    • Xét 1: Đã thăm (marked[1]=T). Bỏ qua.

    • Xét 3: Chưa thăm -> marked[3]=T, edgeTo[3]=2, distTo[3]=distTo[2]+1=2, Enqueue 3. Queue = [1, 5, 3].

    • Xét 4: Chưa thăm -> marked[4]=T, edgeTo[4]=2, distTo[4]=distTo[2]+1=2, Enqueue 4. Queue = [1, 5, 3, 4].

    • Xong với 2.

  4. Dequeue 1:

    • Hàng xóm: 0, 2.

    • Xét 0: Đã thăm. Bỏ qua.

    • Xét 2: Đã thăm. Bỏ qua.

    • Xong với 1. Queue = [5, 3, 4].

  5. Dequeue 5:

    • Hàng xóm: 3, 0.

    • Xét 3: Đã thăm. Bỏ qua.

    • Xét 0: Đã thăm. Bỏ qua.

    • Xong với 5. Queue = [3, 4].

  6. Dequeue 3:

    • Hàng xóm: 5, 4, 2. Tất cả đã thăm. Bỏ qua.

    • Xong với 3. Queue = [4].

  7. Dequeue 4:

    • Hàng xóm: 3, 2. Tất cả đã thăm. Bỏ qua.

    • Xong với 4. Queue = [].

  8. Kết thúc: Hàng đợi rỗng.

4. Tại sao BFS tìm được đường đi ngắn nhất?

Đây là đặc tính quan trọng nhất của BFS!

  • Khám phá theo lớp: Vì BFS dùng hàng đợi (FIFO), nó sẽ xử lý hết tất cả các đỉnh ở khoảng cách k trước khi bắt đầu xử lý bất kỳ đỉnh nào ở khoảng cách k+1.

  • Lần đầu gặp là ngắn nhất: Khi BFS lần đầu tiên đi đến một đỉnh v, nó chắc chắn đã đi qua số lượng cạnh ít nhất có thể từ nguồn s. Nếu có một đường đi khác ngắn hơn đến v, BFS đã phải phát hiện ra v ở một "lớp" trước đó rồi.

  • Kết quả: Mảng distTo[] sẽ chứa độ dài đường đi ngắn nhất (số cạnh) từ s đến mọi đỉnh v, và mảng edgeTo[] cho phép ta truy vết lại chính con đường đó.

5. Cài đặt BFS

  • Không đệ quy: BFS thường được cài đặt bằng vòng lặp while và một đối tượng Queue tường minh.

  • Cấu trúc dữ liệu: marked[], edgeTo[], và một Queue. Mảng distTo[] cũng thường được thêm vào để lưu khoảng cách ngắn nhất.

# Bên trong lớp BreadthFirstPaths
# Giả sử self._marked, self._edge_to, self._dist_to đã được khởi tạo
# Giả sử có một lớp Queue hỗ trợ enqueue và dequeue

def _bfs(self, G, s):
    """Hàm thực hiện BFS từ đỉnh nguồn s."""
    queue = Queue() # Tạo hàng đợi

    self._marked[s] = True
    self._dist_to[s] = 0
    queue.enqueue(s) # Cho nguồn vào hàng đợi

    while not queue.is_empty():
        v = queue.dequeue() # Lấy đỉnh từ đầu hàng đợi
        # Xét các hàng xóm w của v
        for w in G.adj(v):
            if not self._marked[w]: # Nếu w chưa thăm
                self._marked[w] = True    # Đánh dấu
                self._edge_to[w] = v      # Lưu vết
                self._dist_to[w] = self._dist_to[v] + 1 # Tính khoảng cách
                queue.enqueue(w)          # Cho w vào cuối hàng đợi

6. Đặc tính và Ứng dụng

  • Tìm đường đi ngắn nhất (số cạnh): Đây là điểm mạnh cốt lõi của BFS trong đồ thị không có trọng số.

  • Thời gian chạy: Vẫn rất hiệu quả, O(V + E) với danh sách kề.

  • Ứng dụng:

    • Tìm đường đi có ít bước nhảy/chặng nhất trong mạng máy tính (ví dụ ARPANET).

    • Tính "Số Kevin Bacon" hoặc "Số Erdos": Tìm chuỗi quan hệ ngắn nhất trong mạng xã hội hoặc mạng lưới hợp tác khoa học.

    • Web crawler (ưu tiên các trang gần).

    • Tìm các thành phần liên thông.

    • Kiểm tra đồ thị hai phía (bipartite).

V. Thành phần liên thông (Connected Components

Tìm thành phần liên thông (Connected Components) trong đồ thị là một ứng dụng xử lý đồ thị rất quan trọng và hữu ích, hơi khác một chút so với việc chỉ tìm đường đi bằng DFS hay BFS mà chúng ta đã xem xét.

1. Bài toán đặt ra là gì?

  • Nhắc lại khái niệm: Hai đỉnh gọi là liên thông (connected) nếu có đường đi giữa chúng. Một thành phần liên thông (connected component) là một nhóm "tối đại" các đỉnh mà trong đó, bất kỳ hai đỉnh nào cũng liên thông với nhau (giống như một hòn đảo riêng biệt trong quần đảo đồ thị).

  • Mục tiêu chính: Chúng ta muốn xử lý trước (preprocess) đồ thị một lần để sau đó có thể trả lời câu hỏi: "Đỉnh v và đỉnh w có liên thông với nhau không?" một cách cực kỳ nhanh chóng, lý tưởng là trong thời gian không đổi (O(1)), ngay cả với những đồ thị khổng lồ có hàng tỷ đỉnh (nơi mà ma trận kề là bất khả thi).

  • Ngoài ra: Chúng ta cũng muốn đếm xem có tất cả bao nhiêu thành phần liên thông trong đồ thị và gán cho mỗi đỉnh một "nhãn" (ID) để biết nó thuộc về thành phần nào.

2. So sánh nhanh với Union-Find

  • Bài toán này nghe có vẻ giống bài toán Union-Find mà chúng ta có thể đã gặp. Union-Find cũng giúp kiểm tra xem hai phần tử có thuộc cùng một nhóm (tập hợp) hay không.

  • Khác biệt:

    • Union-Find: Cho phép xen kẽ thao tác union (thêm cạnh/kết nối) và find (kiểm tra kết nối). Thời gian find rất nhanh nhưng không hoàn toàn là O(1) theo lý thuyết chặt chẽ.

    • Thuật toán CC (Connected Components) này: Giả định đồ thị là cố định (tất cả các cạnh đã có sẵn). Chúng ta xử lý trước một lần, sau đó trả lời truy vấn connected(v, w) trong thời gian đúng O(1).

3. Ý tưởng cốt lõi: Lại là DFS!

  • Tính chất bắc cầu của liên thông: Mối quan hệ "liên thông" là một quan hệ tương đương (có tính phản xạ, đối xứng, bắc cầu). Điều này đảm bảo rằng đồ thị sẽ được phân hoạch (chia) thành các thành phần liên thông rời nhau.

  • Sử dụng DFS: Chúng ta nhận thấy rằng, nếu bắt đầu DFS từ một đỉnh s bất kỳ, nó sẽ thăm tất cả các đỉnh liên thông với s và chỉ những đỉnh đó mà thôi. Điều này hoàn toàn khớp với việc xác định một thành phần liên thông!

4. Thuật toán Tìm thành phần liên thông bằng DFS

Đây là một thuật toán rất thông minh và hiệu quả:

  1. Chuẩn bị:

    • Mảng marked[] (boolean): Đánh dấu các đỉnh đã được thăm trong toàn bộ quá trình. Khởi tạo tất cả là False.

    • Mảng id[] (integer): Lưu ID (mã số) của thành phần liên thông mà mỗi đỉnh thuộc về. Khởi tạo chưa có giá trị.

    • Biến count (integer): Đếm số lượng thành phần liên thông tìm được. Khởi tạo count = 0.

  2. Quét toàn bộ đồ thị:

    • Duyệt qua tất cả các đỉnh v của đồ thị (từ 0 đến V-1).

    • Kiểm tra: Nếu đỉnh v chưa được đánh dấu (!marked[v]):

      • Điều này có nghĩa là v thuộc về một thành phần liên thông mới mà chúng ta chưa khám phá.

      • Bắt đầu DFS: Gọi hàm dfs(G, v) để khám phá thành phần liên thông này.

      • Quan trọng: Trước khi gọi dfs(G, v), chúng ta có thể hiểu rằng tất cả các đỉnh được tìm thấy bởi lệnh gọi dfs này sẽ thuộc về thành phần liên thông thứ count.

      • Tăng biến đếm: Sau khi hàm dfs(G, v) kết thúc (đã tìm và đánh dấu hết các đỉnh trong thành phần đó), tăng count lên 1 (count++).

  3. Kết thúc: Sau khi duyệt qua hết tất cả các đỉnh v, mảng id[] sẽ chứa ID thành phần liên thông của từng đỉnh, và count sẽ là tổng số thành phần liên thông.

5. Triển khai

Hàm dfs đệ quy cho bài toán này hơi khác so với khi tìm đường đi:

# Bên trong lớp ConnectedComponents
# Giả sử self._marked, self._id, self._count đã được khởi tạo

def _dfs(self, G, v):
    """DFS để gán cùng một ID cho các đỉnh trong cùng một thành phần."""
    self._marked[v] = True  # Đánh dấu đã thăm
    self._id[v] = self._count # Gán ID của thành phần hiện tại cho đỉnh v
    # Duyệt qua các hàng xóm w của v
    for w in G.adj(v):
        if not self._marked[w]: # Nếu w chưa thăm
            self._dfs(G, w)      # Gọi đệ quy để thăm w (w cũng sẽ được gán cùng ID)

# Constructor sẽ chứa vòng lặp for v in range(G.V) và gọi _dfs khi cần
# Nhớ tăng self._count sau mỗi lần gọi _dfs từ vòng lặp chính

6. Demo

  • Bắt đầu vòng lặp, v=0, chưa đánh dấu. count=0. Gọi dfs(G, 0).

    • dfs(0) đánh dấu 0, gán id[0]=0. Gọi dfs(6).

    • dfs(6) đánh dấu 6, gán id[6]=0. Gọi dfs(4).

    • dfs(4) đánh dấu 4, gán id[4]=0. Gọi dfs(5).

    • dfs(5) đánh dấu 5, gán id[5]=0. Gọi dfs(3).

    • dfs(3) đánh dấu 3, gán id[3]=0. Các hàng xóm 5, 4 đã đánh dấu -> quay lui.

    • ... (quay lui tương tự cho 5, 4, 6) ...

    • dfs(0) tiếp tục với hàng xóm 2. dfs(2) đánh dấu 2, gán id[2]=0. ... quay lui.

    • dfs(0) tiếp tục với hàng xóm 1. dfs(1) đánh dấu 1, gán id[1]=0. ... quay lui.

    • dfs(0) tiếp tục với hàng xóm 5 (đã đánh dấu). Hết hàng xóm -> kết thúc dfs(0).

  • Quay lại vòng lặp chính. Kết thúc DFS từ 0. Tăng count thành 1.

  • Vòng lặp tiếp tục, v=1, 2, 3, 4, 5, 6 đều đã đánh dấu.

  • v=7, chưa đánh dấu. count hiện là 1. Gọi dfs(G, 7).

    • dfs(7) đánh dấu 7, gán id[7]=1. Gọi dfs(8).

    • dfs(8) đánh dấu 8, gán id[8]=1. Hàng xóm 7 đã đánh dấu -> quay lui.

    • dfs(7) hết hàng xóm -> kết thúc dfs(7).

  • Quay lại vòng lặp chính. Kết thúc DFS từ 7. Tăng count thành 2.

  • Vòng lặp tiếp tục, v=8 đã đánh dấu.

  • v=9, chưa đánh dấu. count hiện là 2. Gọi dfs(G, 9).

    • ... (tương tự, gán id=2 cho 9, 11, 12, 10) ...

  • Quay lại vòng lặp chính. Kết thúc DFS từ 9. Tăng count thành 3.

  • Vòng lặp tiếp tục, v=10, 11, 12 đã đánh dấu. Hết vòng lặp.

Kết quả: Mảng id chứa ID (0, 1, hoặc 2) cho mỗi đỉnh. count = 3.

7. Trả lời truy vấn và Độ phức tạp

  • Trả lời truy vấn connected(v, w): Chỉ cần kiểm tra id[v] == id[w]. Thao tác này mất O(1) thời gian.

  • Trả lời count(): Trả về giá trị count. Mất O(1) thời gian.

  • Trả lời id(v): Trả về id[v]. Mất O(1) thời gian.

  • Độ phức tạp xử lý trước: Thuật toán duyệt qua mỗi đỉnh và mỗi cạnh đúng một lần trong toàn bộ quá trình (tổng cộng các lần gọi DFS). Do đó, thời gian xử lý trước là O(V + E), rất hiệu quả!

8. Ứng dụng thực tế

  • Mạng lưới xã hội/ Sinh học: Phân tích các cụm, nhóm có liên kết với nhau (như ví dụ về mạng lưới lây truyền bệnh STD hoặc mạng lưới protein).

  • Xử lý ảnh: Xác định các vùng ảnh liên thông có cùng tính chất (như ví dụ xác định các hạt trắng trong ảnh thí nghiệm khoa học - tương tự flood fill). Các "blob" trắng chính là các thành phần liên thông trong đồ thị lưới (grid graph) được tạo ra từ ảnh.

Kết luận:

Thuật toán tìm thành phần liên thông sử dụng DFS là một kỹ thuật mạnh mẽ, hiệu quả và khá tinh tế. Nó cho phép chúng ta "hiểu" được cấu trúc kết nối của đồ thị và chuẩn bị sẵn sàng để trả lời các câu hỏi về tính liên thông giữa hai đỉnh bất kỳ chỉ trong thời gian không đổi. Đây là một ví dụ tuyệt vời về việc áp dụng DFS để giải quyết một bài toán xử lý đồ thị quan trọng khác ngoài việc tìm đường đi.

VI. Các bài toán về Đồ thị

Bây giờ, hãy cùng quay lại bức tranh lớn hơn một chút. Như đã đề cập ở đầu, có rất nhiều bài toán khác nhau liên quan đến đồ thị. Dựa trên những gì đã học, chúng ta thử "cảm nhận" xem những bài toán nào là dễ, bài toán nào là khó nhé? Việc này không có câu trả lời tuyệt đối, nhưng nó giúp chúng ta hình thành trực giác và biết trân trọng những thuật toán hay khi gặp chúng.

Thử thách: Đánh giá độ khó của các bài toán đồ thị

Hãy tưởng tượng chúng ta phân loại độ khó của một bài toán đồ thị theo các mức sau:

  1. "Dễ như ăn kẹo": Bất kỳ lập trình viên nào cũng có thể làm được (với kiến thức cơ bản).

  2. "Sinh viên chăm chỉ": Cần một chút nỗ lực, suy nghĩ, áp dụng kiến thức đã học (như các bạn đang học khóa này là làm được).

  3. "Thuê chuyên gia": Có thuật toán hiệu quả tồn tại, nhưng nó khá phức tạp, đòi hỏi kiến thức sâu hoặc kỹ năng cài đặt cao.

  4. "Khó trị" (Intractable / NP-complete): Hiện tại, không ai biết thuật toán nào hiệu quả để giải quyết bài toán này cho đồ thị lớn. Có thể nói là chuyên gia cũng bó tay (về mặt hiệu quả).

  5. "Chưa biết": Ngay cả các nhà khoa học hàng đầu cũng chưa phân loại được độ khó của bài toán này. Nó có thể dễ, có thể khó, hoặc nằm đâu đó ở giữa.

  6. "Bất khả thi": Chứng minh được rằng không thể giải quyết bài toán này bằng thuật toán (ít gặp hơn trong các bài toán này).

Bây giờ, chúng ta hãy xem xét một vài bài toán cụ thể:

1. Kiểm tra tính Lưỡng phân (Bipartite Check)

  • Bài toán: Liệu có thể chia các đỉnh của đồ thị thành 2 tập hợp (ví dụ: tô màu Đỏ và Trắng) sao cho mọi cạnh đều nối một đỉnh Đỏ với một đỉnh Trắng không?

  • Ví dụ: Đồ thị diễn viên - phim (diễn viên là một tập, phim là tập kia). Đồ thị mối quan hệ hẹn hò nam-nữ (nam một tập, nữ một tập - nếu chỉ xét quan hệ khác giới).

  • Độ khó (theo bài giảng): Sinh viên chăm chỉ. Bạn hoàn toàn có thể sử dụng DFS (hoặc BFS) để giải bài này. Ý tưởng là thử tô màu các đỉnh: bắt đầu tô đỉnh s màu Đỏ, tất cả hàng xóm của s màu Trắng, tất cả hàng xóm của hàng xóm màu Đỏ,... Nếu trong quá trình tô, bạn phát hiện một cạnh nối hai đỉnh cùng màu, thì đồ thị không lưỡng phân. Đây là một bài tập rất hay để bạn thử sức sau buổi học này!

2. Phát hiện Chu trình (Cycle Detection)

  • Bài toán: Đồ thị có chứa ít nhất một chu trình (vòng) hay không?

  • Độ khó (theo bài giảng): "Dễ như ăn kẹo" (hoặc Sinh viên chăm chỉ). Có thể làm rất đơn giản bằng DFS. Trong quá trình DFS, nếu bạn gặp một đỉnh kề w đã được thăm nhưng w không phải là đỉnh ngay trước đó đã gọi đệ quy đến bạn, thì bạn đã tìm thấy một chu trình.

3. Tìm Chu trình Euler (Eulerian Cycle)

  • Bài toán: Có tồn tại một chu trình đi qua mỗi cạnh đúng một lần hay không? Nếu có, hãy tìm ra nó.

  • Nguồn gốc: Bài toán "7 cây cầu ở Königsberg" của nhà toán học Euler thế kỷ 18.

  • Điều kiện tồn tại (Euler đã chứng minh): Một đồ thị liên thông có chu trình Euler khi và chỉ khi mọi đỉnh đều có bậc chẵn (số cạnh nối vào nó là số chẵn). Kiểm tra điều kiện này rất dễ.

  • Tìm chu trình (nếu tồn tại):

    • Độ khó (theo bài giảng): Sinh viên chăm chỉ. Thuật toán tìm chu trình Euler không quá phức tạp về mặt ý tưởng (ví dụ: thuật toán Hierholzer), nhưng cài đặt nó cho đúng có thể hơi thử thách một chút, cần sự cẩn thận.

4. Tìm Chu trình Hamilton (Hamiltonian Cycle)

  • Bài toán: Có tồn tại một chu trình đi qua mỗi đỉnh đúng một lần hay không?

  • Ví dụ: Bài toán người giao hàng muốn đi qua tất cả các thành phố, mỗi thành phố đúng một lần rồi quay về điểm xuất phát.

  • Độ khó (theo bài giảng): "Khó trị" (Intractable / NP-đầy đủ). Đây là một bài toán kinh điển thuộc lớp NP-đầy đủ. Điều này có nghĩa là không ai biết thuật toán nào hiệu quả (chạy trong thời gian đa thức) để giải nó cho các đồ thị lớn. Thuê chuyên gia cũng không giải quyết được (một cách hiệu quả). Đây là một sự khác biệt rất lớn so với chu trình Euler!

5. Kiểm tra Đẳng cấu Đồ thị (Graph Isomorphism)

  • Bài toán: Cho hai đồ thị G1 và G2. Liệu chúng có cùng cấu trúc kết nối hay không, chỉ khác nhau ở cách đặt tên/vẽ các đỉnh?

  • Ví dụ: Hai mạng xã hội có cùng cấu trúc quan hệ bạn bè không, dù tên người dùng khác nhau?

  • Độ khó (theo bài giảng): "Chưa biết". Đây là một bài toán làm đau đầu các nhà toán học và khoa học máy tính trong nhiều thập kỷ. Người ta không biết liệu nó có dễ như các bài toán giải được trong thời gian đa thức, hay khó như các bài toán NP-đầy đủ. Hiện tại, nó nằm ở một "vùng xám". Thử tất cả các cách đổi tên đỉnh (V!) là quá chậm.

6. Kiểm tra tính Phẳng (Planarity Testing)

  • Bài toán: Liệu có thể vẽ đồ thị lên một mặt phẳng (như tờ giấy) mà không có hai cạnh nào cắt nhau (ngoại trừ tại các đỉnh) hay không?

  • Độ khó (theo bài giảng): "Thuê chuyên gia". Có thuật toán chạy trong thời gian tuyến tính O(V+E) để giải bài toán này (dựa trên DFS, do Tarjan phát hiện vào những năm 1970). Điều này có nghĩa là về mặt lý thuyết, nó rất hiệu quả. Tuy nhiên, bản thân thuật toán đó lại cực kỳ phức tạp và rất khó để hiểu và cài đặt đúng. Ngay cả giáo sư hay sinh viên giỏi cũng sẽ gặp nhiều khó khăn.

Bài học rút ra:

Thế giới các bài toán xử lý đồ thị thật đa dạng và đầy thách thức!

  • Có những bài toán khá cơ bản, giải được bằng các kỹ thuật nền tảng như DFS, BFS mà chúng ta đã học.

  • Có những bài toán đòi hỏi thuật toán thông minh hơn một chút, nhưng vẫn nằm trong tầm tay nếu bạn chăm chỉ tìm hiểu.

  • Có những bài toán nổi tiếng là cực khó, gần như không thể giải quyết hiệu quả cho dữ liệu lớn trong thực tế.

  • Và thậm chí có những bài toán mà giới hạn khả năng giải quyết của chúng ta vẫn còn là một bí ẩn.

0
Subscribe to my newsletter

Read articles from Ha Ngoc Hieu directly inside your inbox. Subscribe to the newsletter, and don't miss out.

BFSDFSGraphalgorithms

Written by

Ha Ngoc Hieu
Ha Ngoc Hieu