Biểu diễn đồ thị bằng danh sách kề c++
Show Viblo Algorithm @viblo.algorithm Đã đăng vào thg 2 7, 7:41 SA 5 phút đọc
Giả sử G=(V,E)G=(V, E)G=(V,E) là một đa đồ thị có số đỉnh là NNN. Coi rằng các đỉnh được đánh số từ 111 tới NNN. Khi đó, ta có thể biểu diễn đồ thị bằng một ma trận vuông adjadjadj kích thước N×NN\times NN×N, trong đó:
Cài đặt: Việc cài đặt cạnh sẽ thay đổi tùy vào đồ thị là có hướng hay vô hướng. Dưới đây sẽ trình bày cài đặt cho đồ thị vô hướng: void enter_adjacency_matrix() { cin >> N >> M; for (int i = 1; i <= M; ++i) { int u, v; cin >> u >> v; adj[u][v]++; adj[v][u]++; } }Ví dụ: Đồ thị G(V,E)G(V, E)G(V,E) dưới đây có 555 đỉnh, 666 cạnh: Ma trận kề của nó sẽ có dạng như sau: Ưu điểm của ma trận kề:
Nhược điểm của ma trận kề:
Phù hợp khi nào: Trong các bài toán đồ thị có số lượng đỉnh ít (thường là không vượt quá 300300300). II. Danh sách cạnh (Edge List)Trong trường hợp biết trước đồ thị có NNN đỉnh, MMM cạnh, ta có thể biểu diễn đồ thị dưới dạng một danh sách lưu các cạnh (u,v)(u, v)(u,v) của đồ thị đó (nếu là đồ thị có hướng thì mỗi cặp (u,v)(u, v)(u,v) ứng với một cung u→vu \rightarrow vu→v). Vector hoặc mảng là một kiểu dữ liệu rất phù hợp để lưu trữ danh sách cạnh. Cài đặt: vector < pair < int, int > > edge_list; void enter_edge_list() { cin >> N >> M; for (int i = 1; i <= M; ++i) { int u, v; cin >> u >> v; edge_list.push_back({u, v}); } }Ví dụ: Đồ thị G(V,E)G(V, E)G(V,E) dưới đây 555 đỉnh, 666 cạnh theo thứ tự là: (1,3),(1,4),(3,4),(3,2),(5,3),(2,5)(1, 3), (1, 4), (3, 4), (3, 2), (5, 3), (2, 5)(1,3),(1,4),(3,4),(3,2),(5,3),(2,5): Danh sách cạnh của nó được biểu diễn bằng một vector \text{edge_list} như sau: Ưu điểm của danh sách cạnh:
Nhược điểm của danh sách cạnh: Trong trường hợp cần duyệt các đỉnh kề với một đỉnh uuu, bắt buộc phải duyệt qua mọi cạnh, lọc ra các cạnh có chứa đỉnh uuu và xét đỉnh còn lại. Điều này sẽ tốn thời gian nếu đồ thị có nhiều cạnh. Phù hợp khi nào: Trong các bài toán cần duyệt toàn bộ cạnh, tiêu biểu như trong giải thuật Kruskal. III. Danh sách kề (Adjacency List)Để khắc phục nhược điểm của ma trận kề và danh sách cạnh, người ta sử dụng danh sách kề (cũng là cách thường xuyên sử dụng nhất trong các bài toán đồ thị). Trong cách biểu diễn này, với mỗi đỉnh u của đồ thị, ta sẽ tạo ra một dánh sách adjuadj_uadju là các đỉnh kề với nó. Việc cài đặt adjuadj_uadju có thể thực hiện dễ dàng với vector. Cài đặt: Ví dụ: Đồ thị G(V,E)G(V, E)G(V,E) dưới đây gồm 555 đỉnh, 444 cạnh: Danh sách kề của nó có thể biểu diễn bằng một mảng adj[6]\text{adj}[6]adj[6] gồm các vector (kích thước mảng là 666 do không có đỉnh số 000), mỗi vector adj[u]\text{adj}[u]adj[u] lưu danh sách kề của đỉnh uuu: Ưu điểm của danh sách kề:
Nhược điểm của danh sách kề: Khi cần kiểm tra (u,v)(u, v)(u,v) có phải là một cạnh của đồ thị hay không thì bắt buộc phải duyệt toàn bộ danh sách kề của uuu hoặc của vvv. Phù hợp khi nào: Hầu hết trong mọi bài toán đồ thị đều nên sử dụng, chỉ trừ các bài toán cần duyệt toàn bộ cạnh của đồ thị. IV. Tài liệu tham khảoAll rights reserved |