Hi, I am

Ngô Tôn

I am a programmer.

Home / HCMUS / Graph Theory / Duyệt đồ thị & Xác định thành phần liên thông

Duyệt đồ thị & Xác định thành phần liên thông

1.1.    Tính liên thông

Một đồ thị vô hướng được gọi là liên thông nếu có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị. Ngược lại, đồ thị này được gọi là không liên thông.

Một đồ thị không liên thông sẽ bao gồm nhiều đồ thị con liên thông, các đồ thị con này được gọi là các thành phần liên thông.

Đồ thị có hướng gọi là liên thông mạnh nếu có đường đi từ a tới b và từ b tới a với mọi cặp đỉnh a và b của đồ thị. Đồ thị có hướng gọi là liên thông yếu nếu có đường đi giữa 2 đỉnh bất kỳ của đồ thị vô hướng nền. Đồ thị có hướng được gọi là liên thông một phần nếu với mọi cặp đỉnh a, b bất kỳ, có ít nhất một đỉnh đến được đỉnh còn lại.

1.2.    Duyệt đồ thị

Để duyệt đồ thị người ta thường sử dụng hai phương pháp: duyệt theo chiều sâu (DFS) và duyệt theo chiều rộng (BFS).

  • DFS

Từ đỉnh bắt đầu, ta tiến hành “khám phá” đồ thị sao cho chúng ta có thể đi càng xa so với đỉnh bắt đầu càng tốt. Khi nào không thể đi được nữa, thuật toán quay trở lại điểm phân nhánh gần nhất, rẽ sang các hướng khác và tiếp tục thực hiện thuật toán DFS tại đỉnh này.

Ngoài cách cài đặt trên, người ta có thể khử đệ quy bằng cách dùng cơ chế của ngăn xếp (stack).

  • BFS

Thuật toán BFS bắt đầu từ đỉnh gốc và lần lượt thăm các đỉnh kề với đỉnh gốc. Sau đó, với mỗi đỉnh trong số đó, thuật toán lại lần lượt thăm các đỉnh kề với nó mà chưa được thăm trước đó và lặp lại. Đối với thuật toán này, ta dùng cấu trúc hang đợi (queue) để cài đặt.

1.3.    Xác định thành phần liên thông

Thuật toán DFS có thể được sử dụng để xác định các thành phần liên thông. Với mỗi thành phần liên thông được gán một nhãn (label) xác định:

  • 0 đại diện cho chưa có nhãn hay chưa được viếng thăm.
  • 1, 2, 3, … là nhãn tương ứng của mỗi thành phần liên thông.

Nhận xét: dựa trên nhãn lớn nhất, ta có thể xác định được số thành phần liên thông của đồ thị.

Source code (C++)

1.1.    Tính liên thông Một đồ thị vô hướng được gọi là liên thông nếu có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị. Ngược lại, đồ thị này được gọi là không liên thông. Một đồ thị không liên thông sẽ bao gồm nhiều đồ thị con liên thông, các đồ thị con này được gọi là các thành phần liên thông. Đồ thị có hướng gọi là liên thông mạnh nếu có đường đi từ a tới b và từ b tới a với mọi cặp đỉnh a và b của đồ thị. Đồ thị có…

User Rating: 5 ( 1 votes)

About ngoton

Ngô Tôn is a programmer with passion for tailored software solutions. Comes with 6+ years of IT experience, to execute beautiful front-end experiences with secure and robust back-end solutions.

Check Also

Biểu diễn và thao tác trên đồ thị

1.     Tóm tắt một số khái niệm Đồ thị là một thể hiện bao gồm …

Leave a Reply

Your email address will not be published. Required fields are marked *