Các khái niệm cơ bản của đồ thị
Một đồ thị là một cấu trúc rời rạc gồm tập hợp các đỉnh và các cạnh nối giữa các đỉnh đó.
Có thể mô tả đồ thị theo cách hình thức như sau:
G=(V,E)
tức là đồ thị G có tập các đỉnh là V, tập các cạnh là E. Có thể hiểu E là tập hợp các cặp (u, v) với u và v là hai đỉnh thuộc V.
- G được gọi là đơn đồ thị nếu như giữa hai đỉnh (u, v) của V có nhiều nhất một cạnh trong E nối từ u tới v.
- G được gọi là đa đồ thị nếu như giữa hai đỉnh (u,v) của V có thể có nhiều hơn 1 cạnh nối trong E nối từ u tới v. Đơn đồ thị là trường hợp đặc biệt của đa đồ thị
- G được gọi là đồ thị vô hướng nếu các cạnh là cạnh 2 chiều, có thể đi từ u -> v và v -> u trên 1 cạnh
- G được gọi là đồ thị có hướng nếu các cạnh có định hướng một chiều, ví dụ cạnh (u,v) chỉ có thể đi từ u -> v
- Hai đỉnh trong đồ thị vô hướng được gọi là đỉnh kề nếu giữa chúng có cạnh nối với nhau. Cạnh này được gọi là cạnh liên thuộc
- Nếu một cạnh nối một đỉnh với chính nó, ta gọi đó là khuyên
- Bậc là số lượng cạnh liên thuộc của một đỉnh
Graph trong cuộc sống
- Trong các ứng dụng bản đồ như Google Map. Với các điểm đến là một nút, ta có nhiều bài toán Đường đi ngắn nhất, hay tìm đường để đi từ điểm A -> B
Biểu diễn đồ thị
Ma trận kề
Với mỗi cạnh giữa 2 đỉnh u và v, ta có thể biểu diễn dưới dạng ma trận, với nếu matran[x][y] là số lượng cạnh nối giữa đỉnh x và đỉnh y
Ưu điểm của ma trận kề:
- Đơn giản, dễ cài đặt.
- Kiểm tra cạnh giữa 2 đỉnh trong O(1)
Nhược điểm của ma trận kề:
- Tốn N^2 (số đỉnh) để triển khai bộ nhớ
- Để tìm tất cả các đỉnh kề của đỉnh x, ta cần duyệt qua toàn bộ hàng/cột của đỉnh x O(n)
Danh sách kề
Ta sẽ có một mảng hoặc vector 2 chiều, và lưu mỗi đỉnh các đỉnh kề của chúng.
Ưu điểm của danh sách kề:
- Tìm các đỉnh kề của một đỉnh rất nhanh
- Tiết kiệm không gian lưu trữ
Nhược điểm của danh sách kề:
- Kiểm tra 2 đỉnh có kề nhau hay không cần duyệt qua danh sách kề của u hoặc v tốn O(m) thời gian
Danh sách cạnh
Ta lưu lại tất cả các cạnh của đồ thị dưới dạng pair (u,v) chứ không lưu đỉnh
Ưu điểm của danh sách cạnh:
- Tốn không gian lưu trữ tùy thuộc vào số cạnh
- Phù hợp trường hợp cần duyệt toàn bộ cạnh thì
Nhược điểm của danh sách cạnh:
- Tốn thời gian nếu cần duyệt các đỉnh kề vì cần duyệt qua toàn bộ cạnh và tìm đỉnh cần tìm trong đó
Các thuật toán tìm kiếm trên đồ thị
- Ta gọi một đường đi từ u->v có độ dài k là tập hợp k đỉnh mà khi đi qua các đỉnh này ta đi được từ u->v
- Một chu trình là một đường đi sau khi đi xong sẽ về điểm xuất phát.
- Đường đi đơn là đường đi mà tập hợp k đỉnh phân biệt
- Chu trình đơn là chu trình mà tập hợp đỉnh trên chu trình phân biệt
Thuật toán DFS (Tìm kiếm theo chiều sâu)
Tư tưởng thuật toán:
Thuật toán tìm kiếm theo chiều sâu (DFS) là bắt đầu từ
một đỉnh bất kì v nào đó + đánh dấu đỉnh v đã được duyệt,
chọn một đỉnh u bất kỳ kề với v và lấy nó làm đỉnh duyệt
tiếp theo.
DFS Từ điểm bắt đầu u , ta tìm đỉnh đầu tiên trong các đỉnh kề của u, tiếp tục DFS trên đó và lặp lại. Nếu không còn đỉnh để đi nữa, ta sẽ quay trở lại ngã rẽ gần nhất.
Cài đặt theo đệ quy
Cài đặt theo Stack (Không đệ quy)
Thuật toán BFS (Tìm kiếm theo chiều rộng)
Tư tưởng thuật toán:
- Dựa trên tư tưởng lập ra một thứ tự duyệt các đỉnh, sao cho các đỉnh gần s hơn sẽ luôn luôn được duyệt xong trước các đỉnh xa s hơn.
- Ví dụ, từ đỉnh s ta thăm các đỉnh kề với nó là x1,x2,x3 Khi thăm tới x1, sẽ phát sinh việc thăm các đỉnh kề với x1a, x1b. Dĩ nhiên các đỉnh này đều xa s hơn so với x2,x3 cho nên chúng sẽ chỉ được thăm sau khi toàn bộ các đỉnh x2,x3 đã được thăm hết.
- Thuật toán loang (thuật toán vết dầu loang) là một kĩ thuật sử dụng BFS để tìm tất cả các điểm có thể đi tới. Điểm khác biệt giữa Loang so với đa số những bài BFS là ta không phải tìm chi phí nhỏ nhất.
- Thuật toán loang được dùng khá nhiều trong tin học, điển hình là thuật toán loang trên ma trận được ứng dụng để đếm số thành phần liên thông trên ma trận.
Cài đặt theo Queue
Độ phức tạp tính toán của DFS và BFS
Tùy vào cách cài đặt đồ thị mà ta sẽ thu được các giải thuật với độ phức tạp khác nhau:
- Nếu đồ thị biểu diễn bằng danh sách kề, cả hai giải thuật BFS/DFS đều có độ phức tạp là O(n + m) ~ O(n) Cách cài đặt này là tốt nhất.
- Nếu đồ thị biểu diễn bằng ma trận kề, độ phức tạp tính toán sẽ là O(n^2)
- Nếu đồ thị biểu diễn bằng danh sách cạnh, thao tác duyệt mọi đỉnh kề với đỉnh u sẽ buộc phải duyệt qua toàn bộ danh sách cạnh, dẫn đến độ phức tạp tính toán là O(n*m). Đây là cách cài đặt tệ nhất.
Tính liên thông của đồ thị
- Đồ thị vô hướng được coi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.
- Trong trường hợp đồ thị G không liên thông, ta có thể phân ra G thành một số đồ thị con liên thông mà chúng đôi một không có đỉnh chung. Mỗi đồ thị con như vậy là một thành phần liên thông của G. Như vậy, đồ thị liên thông khi và chỉ khi số thành phần liên thông của nó là 1.
- Đối với đồ thị vô hướng, đường đi từ đỉnh u đến đỉnh v cũng giống như đỉnh đường đi từ đỉnh v đến đỉnh u. Chính vì vậy, nếu tồn tại u sao cho u có đường đi đến tất cả các đỉnh còn lại của đồ thị thì ta kết luận được đồ thị là liên thông.
- Đỉnh khớp (cut vertex/ articulation point): của một đồ thị vô hướng là đỉnh mà nếu xóa đỉnh này khỏi đồ thị và các cạnh nối đến nó thì số thành phần liên thông của đồ thị sẽ tăng thêm hoặc biến đồ thị từ liên thông thành không liên thông
Ví dụ: Xóa 0 và 3 thì đồ thị đang có thể đi lại giữa các đỉnh (Đồ thị liên thông) tạo thành 2 thành phần liên thông (1,2) và (4) không đi lại được với nhau
- Cạnh cầu (bridge): của một đồ thị vô hướng là cạnh mà nếu xóa đi khỏi đồ thị thì số thành phần liên thông của đồ thị sẽ tăng thêm
- Liên thông mạnh (strongly connected): Đồ 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ị.
Giữa 2 đỉnh bất kì trong đồ thị con (0,1,2) và đồ thị con (3,4) đều có cạnh nối với nhau
- Liên thông yếu (weakly connected): Đồ 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 tương ứng với đồ thị đã cho. Tức là hủy bỏ các hướng của các cạnh trong đồ thị.
Đếm số thành phần liên thông bằng DFS và BFS
