Bài giảng Cấu trúc dữ liệu và giải thuật: Đồ thị - Phan Mạnh Hiển (2020)

Bài giảng "Cấu trúc dữ liệu và giải thuật: Đồ thị" cung cấp cho người học các kiến thức: Đồ thị và biểu diễn đồ thị, duyệt đồ thị, sắp xếp topo, tìm đường đi ngắn nhất. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Đồ thị - Phan Mạnh Hiển (2020)Đồ thị(Graphs)Nguyễn Mạnh Hiểnhiennm@tlu.edu.vnNội dung• Đồ thị và biểu diễn đồ thị• Duyệt đồ thị• Sắp xếp topo• Tìm đường đi ngắn nhấtĐồ thị và biểu diễn đồ thịĐồ thị v1 v2 v3• Đồ thị G = (V, E) bao gồm một tập đỉnh V và một tập cạnh E• Mỗi cạnh là một cặp (v, w) v4 v5 v6 trong đó v, w  V• Đồ thị không có hướng: v7 − Các cạnh không có thứ tự v8 − Cạnh (v, w) giống như cạnh (w, v)• Đồ thị không có hướng được vẽ bằng các nút cho các đỉnh và các đoạn thẳng cho các cạnhĐồ thị có hướng v1 v2 v3• Trong đồ thị có hướng, E là một tập các cặp có thứ tự, nhưng không nhất thiết là v4 v5 v6 tập đối xứng, tức là nếu cạnh (v, w) có mặt thì cạnh (w, v) v7 có thể vắng mặt v8• Đồ thị có hướng được vẽ bằng các nút cho các đỉnh và các mũi tên cho các cạnhĐường đi và trọng số• Đường đi là một dãy đỉnh w1, w2, …, v2 v3 v1 wn, trong đó có một cạnh giữa hai -2 3 5 2 đỉnh liên tiếp wi và wi+1• Chiều dài của đường đi có n đỉnh v4 v5 v6 bằng n – 1 (số cạnh) -1• Đường đi là đơn giản nếu tất cả các v7 1 4 đỉnh trên đường đi khác nhau (ngoại trừ đỉnh đầu và đỉnh cuối có thể trùng v8 nhau)• Các cạnh có thể có trọng số (hay chi phí) kèm theo• Chi phí của đường đi bằng tổng trọng số của các cạnh trên đường đi đóChu trình v2 v3 v1 v2 v3 v1 v4 v4 v5 v6 v5 v6 v7 v7 v8 v8• Chu trình là đường đi w1, w2, …, wn = w1, trong đó đỉnh đầu và đỉnh cuối trùng nhau − Chu trình đơn giản nếu đường đi đó đơn giản• Trong hình vẽ bên trên: v2, v8, v6, v3, v5, v2 là một chu trình (đơn giản) trong đồ thị không có hướng, nhưng không phải như vậy trong đồ thị có hướngĐồ thị liên thông v1 v2 v3• Đồ thị không có hướng là liên thông nếu tồn tại đường đi giữa v4 v5 v6 mọi cặp đỉnh trong đồ thị đó• Đồ thị có hướng thỏa mãn điều v7 liên thông kiện trên được gọi là liên thông v8 yếu mạnh• Nếu một đồ thị có hướng không v1 v2 v3 liên thông mạnh, nhưng đồ thị không có hướng tương ứng liên v4 v5 v6 thông, thì được gọi là liên thông yếu v7 liên thông v8 mạnhBiểu diễn đồ thị• Đánh số các đỉnh trong đồ thị từ 0 đến n-1• Có thể dùng mảng hai chiều A có kích thước n x n (ma trận vuông cỡ n) để lưu trữ đồ thị có hướng − Với đồ thị không có trọng số, A[v][w] bằng true hoặc false tùy theo cạnh (v, w) có mặt trong đồ thị hay không − Với đồ thị có trọng số, A[v][w] bằng trọng số của cạnh (v, w) nếu cạnh đó có mặt, hoặc bằng một giá trị đặc biệt (như ) nếu cạnh đó vắng mặt• Với đồ thị không có hướng, cách biểu diễn trên (được gọi là biểu diễn ma trận kề) lưu trữ mỗi cạnh hai lần• Biểu diễn ma trận kề yêu cầu không gian O(n2)Ví dụ biểu diễn ma trận kề 0 1 2 3 4 5 6 7 v2 v3 0 F F F F F F T Fv1 1 F F F F T F F F 2 T F F F F F F F v4 v5 v6 3 F F F F F T T Fv7 4 F F F F F F F F v0 5 F F T F F F F F 6 F F F F F F F F 7 T F F F F F F FBiểu diễn danh sách kề• Biểu diễn ma trận kề lãng phí không gian khi đồ thị thưa (có rất ít cạnh) − VD: Mỗi nút giao thông thường chỉ có 3-4 con đường giao nhau  số cạnh = O(n)• Danh sách kề là cách tiếp cận hiệu quả để lưu trữ đồ thị thưa − Đỉnh w kề với đỉnh v nếu (v, w)  E − Mỗi đỉnh giữ một danh sách các đỉnh kề với nó (các cạnh đi ra). Nếu các cạnh có trọng số thì cũng lưu trữ các trọng số vào danh sách kề này. − Yêu cầu không gian O(|V|+|E|) − Có thể dùng vector hoặc danh sách liên kết để lưu trữ danh sách đỉnh kềVí dụ biểu diễn danh sách kề ...