tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Ngô Công Thắng

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 5: Đồ thị" cung cấp cho người học các kiến thức: Các khái niệm, biểu diễn đồ thị, phép duyệt đồ thị, bài toán tìm đường đi ngắn nhất,. . | Chương 5: Đồ thị 1. Các khái niệm . Định nghĩa đồ thị Đồ thị G(V,E) bao gồm một tập hữu hạn V các đỉnh (hay nút) và một tập hữu hạn E các cặp đỉnh mà ta gọi là cung ( hay cạnh). Ví dụ 1: Một mạng gồm các máy tính và các kênh điện thoại nối các máy tính này là một đồ thị. Ví dụ 2: Một mạng gồm các thành phố, thị xã và các đường bộ nối các thành phố, thị xã là một đồ thị. . Định nghĩa đồ thị vô hướng Đồ thị vô hướng G=(V,E) bao gồm V là tập các đỉnh và E là tập các cặp đỉnh không có thứ tự gọi là các cung. * Nếu (v1, v2) là một cung trong tập E(G) thì v1 và v2 gọi là lân cận của nhau. Ví dụ trên 1,2 là lân cân, 1,3 là lân cận. * Một đường đi từ đỉnh u đến đỉnh v trong đồ thị là một dãy các đỉnh u=x0, x1, ., xn-1, xn=v mà dãy các cạnh (x0, x1), (x1, x2), ., (xn-1, xn) là các cung thuộc E(G) . * Số lượng cung trên đường đi gọi là độ dài của đường đi. Ví dụ đường đi từ 1 đến 4 có độ dài là 2. * Đường đi đơn: Là đường đi mà mọi đỉnh trên đó, trừ đỉnh đầu và đỉnh cuối đều khác nhau. * Một chu trình là một đường đi đơn mà đỉnh đầu và đỉnh cuối trùng nhau. Ví dụ: 1→ 3 → 5→ 4→1 3. Phép duyệt đồ thị * Xét đồ thị vô hướng G(V,E) và một đỉnh v∈V. Ta cần thăm tất cả các đỉnh của G mà có thể “ với tới” từ đỉnh v ( nghĩa là đồ thị liên thông). Có 2 cách duyệt đồ thị: - Phép tìm kiếm theo chiều sâu ( Depth first search ) - Phép tìm kiếm theo chiều rộng (Breadth first search ) . Phép tìm kiếm theo chiều sâu ( Depth first search ) Xét đồ thị vô hướng. Phép tìm kiếm theo chiều sâu thể hiện như sau: - Đỉnh xuất phát v được thăm. - Tiếp theo đó ta thăm đỉnh w là đỉnh chưa được thăm và là lân cận của v. Phép tìm kiếm theo chiều sâu xuất phát từ w lại được thực hiện. Trong trường hợp đỉnh u đã được thăm mà mọi đỉnh lân cận của nó đã được thăm rồi thì ta quay lại đỉnh cuối cùng vừa được thăm ( mà đỉnh này còn đỉnh w là lân cận của nó chưa được thăm) và phép tìm kiếm theo chiều sâu xuất phát từ w lại được thực hiện. Phép duyệt theo chiều sâu đi theo trình tự sau: v1 → v2