Programming, Network, Office, Hardware, Software, Design, Photography.. I am just a GEEK
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.
|
1 2 3 4 5 |
DFS(GRAPH g, Vertex u): Đánh dấu đỉnh u là đã được viếng thăm Với mỗi cạnh e từ u đến v: Nếu v chưa được viếng thăm DFS(GRAPH g, Vertex v) |
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 2 3 4 5 6 7 8 9 |
BFS(GRAPH g, Vertex u): Đánh dấu đỉnh u là chưa viếng thăm Đẩy u vào hàng đợi Trong khi hàng đợi không rỗng Gọi v là đỉnh được lấy ra khỏi hàng đợi Đánh dấu v là đã được viếng thăm Với mỗi cạnh từ v đến các đỉnh chưa được viếng thăm t Đánh dấu t là chưa viếng thăm Đẩy t vào hàng đợi |
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ị.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
Giả sử đồ thị G = (X, E) gồm n đỉnh. X là tập hợp các đỉnh và E là tập hợp các cạnh của đồ thị. Bước 1: Khởi tạo biến label=0 và gán nhãn 0 cho tất cả các đỉnh Bước 2: Lặp i = 1, 2, …, n lần Nếu đỉnh i có nhãn 0 thì label = label + 1 Gọi hàm Visit(đỉnh i, nhãn label) Cuối Nếu Cuối Lặp Hàm Visit (đỉnh i, nhãn label) Gán nhãn label cho đỉnh i Với mọi đỉnh j có cạnh nối với i và nhãn là 0, gọi: Visit(đỉnh j, nhãn label) |
Buy me a coffee
Leave a Reply