TAILIEUCHUNG - Bài giảng Toán rời rạc 2 - Tìm kiếm trên đồ thị

Bài giảng Toán rời rạc 2 - Tìm kiếm trên đồ thị cung cấp cho người học các kiến thức: Thuật toán tìm kiếm theo chiều sâu trên đồ thị, thuật toán tìm kiếm theo chiều rộng trên đồ thị, ứng dụng của thuật toán tìm kiếm theo chiều sâu, ứng dụng của thuật toán tìm kiếm theo chiều rộng. Mời các bạn cùng tham khảo. | Bài giảng Toán rời rạc 2 - Tìm kiếm trên đồ thị TÌM KIẾM TRÊN ĐỒ THỊ Toán rời rạc 2 Nội dung Thuật toán tìm kiếm theo chiều sâu trên đồ thị. Thuật toán tìm kiếm theo chiều rộng trên đồ thị. Ứng dụng của thuật toán tìm kiếm theo chiều sâu. Ứng dụng của thuật toán tìm kiếm theo chiều rộng. 2 Thuật toán tìm kiếm theo chiều sâu Depth First Search DFS Tư tưởng Trong quá trình tìm kiếm ưu tiên chiều sâu hơn chiều rộng Đi xuống sâu nhất có thể trước khi quay lại Bắt đầu tại một đỉnh v0 nào đó chọn một đỉnh u bất kỳ kề với v0 và lấy nó làm đỉnh duyệt tiếp theo. Cách duyệt tiếp theo được thực hiện tương tự như đối với đỉnh v0 với đỉnh bắt đầu là u. Để kiểm tra việc duyệt mỗi đỉnh đúng một lần chúng ta sử dụng một mảng chuaxet gồm n phần tử tương ứng với n đỉnh Nếu đỉnh thứ u đã được duyệt phần tử tương ứng trong mảng chuaxet u có giá trị FALSE. Ngược lại nếu đỉnh chưa được duyệt phần tử tương ứng trong mảng có giá trị TRUE. 4 Biểu diễn thuật toán DFS DFS u có thể được mô tả bằng thủ tục đệ qui như sau Thuật toán DFS u u là đỉnh bắt đầu duyệt Begin Duyệt đỉnh u chuaxet u FALSE Xác nhận đỉnh u đã duyệt for each v Ke u do Lấy mỗi đỉnh v Ke u . If chuaxet v then Nếu đỉnh v chưa duyệt DFS v Duyệt theo chiều sâu bắt từ đỉnh v EndIf EndFor End. 5 Thuật toán DFS u dùng ngăn xếp khử đệ qui 6 Độ phức tạp thuật toán DFS Độ phức tạp thuật toán DFS u phụ thuộc vào phương pháp biểu diễn đồ thị Độ phức tạp thuật toán là O n2 trong trường hợp đồ thị biểu diễn dưới dạng ma trận kề với n là số đỉnh của đồ thị. Độ phức tạp thuật toán là O trong trường hợp đồ thị biểu diễn dưới dạng danh sách cạnh với n là số đỉnh của đồ thị m là số cạnh của đồ thị. Độ phức tạp thuật toán là O max n m trong trường hợp đồ thị biểu diễn dưới dạng danh sách kề với n là số đỉnh của đồ thị m là số cạnh của đồ thị. 7 Kiểm nghiệm thuật toán DFS 1 3 Ví dụ 1 Cho đồ thị gồm 13 đỉnh như hình vẽ. Hãy kiểm nghiệm thuật toán DFS 1 . 8 Kiểm nghiệm thuật toán DFS 2 3 9 Kiểm nghiệm thuật toán DFS 3 3 10 Ví dụ 2 Cho đồ .

• Toán học
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Tìm kiếm trên đồ thị
• Thuật toán tìm kiếm
• Ứng dụng của thuật toán tìm kiếm
• Bài giảng toán rời rạc
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• bài tập toán rời rạc
• lý thuyết toán rời rạc
• đề cương Toán rời rạc
• tìm hiểu Toán rời rạc
• Thuật toán Dijkstra
• Thuật toán Bellman Ford
• Bài toán tìm đường đi ngắn nhất
• Toán học rời rạc
• Cấu trúc rời rạc
• Phương pháp đếm dùng hàm sinh
• Hệ số hàm sinh
• Hàm sinh mũ
• Bài giảng Toán học rời rạc
• Công nghệ thông tin
• Giới thiệu môn học
• Trí tuệ nhân tạo
• Khái niệm về đồ thị
• Đđồ thị vô hướng
• Đồ thị có hướng
• Dạng đồ thị đặc biệt
• Biểu diễn đồ thị trên máy tính
• Biểu diễn đồ thị
• Biểu diễn đồ thị bằng danh sách kề
• Ma trận liên thuộc
• Đồ thị Euler
• Đồ thị Hamilton
• Chứng minh đồ thị là nửa Euler
• Toán rời rạc ứng dụng trong tin học
• Bài toán về đường đi
• Đường đi Euler
• Đường đi Hamilton
• Cây khung của đồ thị
• Hàm đơn ánh
• Độ tăng của hàm
• Thuật toán
• Thuật toán sắp xếp nổi bọt
• Hàm và thuật toán
• Độ phức tạp của thuật toán
• Nguyên lý bù trừ
• Hoán vị lặp
• Tổ hợp lặp
• Giải tích tổ hợp
• Hệ thức đệ qui
• Lý thuyết tập hợp
• Phép toán tập hợp
• Tích Descartes
• cơ sở dữ liệu
• hệ thống dữ liệu
• Bài giảng Hàm Bool
• Phép toán trên hàm Bool
• Dạng nối rời chính tắc của Hàm Bool
• Phương pháp biểu đồ Karnaugh
• Đồ thị vô hướng
• Biểu diễn đồ thị bằng ma trận kề
• Thuật toán tìm kiếm theo chiều sâu
• Bài giảng Quan hệ
• Quan hệ 2 ngôi
• Tính chất quan hệ 2 ngôi
• Tập hợp thương
• Bài giảng Toán rời rạc 1
• Toán rời rạc 1
• Bài toán liệt kê
• Thuật toán quay lui
• Thuật toán nhánh
• Nguyên lý Dirichlet
• Duyệt đồ thị
• Bài toán đường đi ngắn nhất
• Lý thuyết đồ thị
• Bài toán luồng cực đại