Bài giảng Cấu trúc dữ liệu và giải thuật (Data structures and Algorithms) - Chương 2 trang bị cho người học những kiến thức cơ bản về đồ thị. Những nội dung chính được trình bày trong chương này gồm có: Định nghĩa đồ thị, biểu diễn đồ thị, phép duyệt đồ thị, cây khung và cây khung với giá trị cực tiểu. Mời các bạn cùng tham khảo. | Chương 2 Đồ 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. Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 02 Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 02 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 Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 02 Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 02 Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 02 Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 02 Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 02 Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 02 Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 02 Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 02 Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 02 Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 02 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 .
